Experimental analyses on 2-hop-based and 3-hop-based link prediction algorithms

Link prediction is a significant and challenging task in network science. The majority of known methods are similarity-based, which assign similarity indices for node pairs and assume that two nodes of larger similarity have higher probability to be connected by a link. Due to their simplicity, interpretability and high efficiency, similarity-based methods, in particular those based only on local information, have found successful applications on disparate fields. An intuitive consensus is that two nodes sharing common neighbors are likely to have a link, while some recent evidences indicate that the number of 3-hop paths more accurately predicts missing links than the number of common neighbors. In this paper, we implement extensive experimental comparisons between 2-hop-based and 3-hop-based similarity indices on 137 real networks. Overall speaking, the class of Cannistraci–Hebb indices performs the best among all considered candidates. In addition, 3-hop-based indices outperform 2-hop-based indices on ROC-AUC, and 3-hop-based indices and 2-hop-based indices are competitive on precision. Further statistical results show that 3-hop-based indices are more suitable for disassortative networks with lower densities and lower average clustering coefficients.