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

Abstract

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 already found successful applications on disparate fields. In this research domain, an intuitive consensus is that two nodes sharing common neighbors are very likely to have a link, while some recent evidences argue 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 128 real networks. Our results indicate that the 3-hop-based indices perform slightly better with a winning rate about 55.88%, but which index is the best one still depends on the target network. Overall speaking, the class of Cannistraci-Hebb indices performs the best among all considered candidates.

arXiv comment4 figures

References in corpus (20)

• Community structure in social and biological networks
• Assortative mixing in networks
• Link Prediction in Complex Networks: A Survey
• Hierarchical structure and the prediction of missing links in networks
• Hierarchical Organization in Complex Networks
• Predicting Missing Links via Local Information
• Recommender Systems
• Missing and spurious interactions and the reconstruction of complex networks
• Effective and Efficient Similarity Index for Link Prediction of Complex Networks
• Simplicial Closure and higher-order link prediction
• Pseudofractal Scale-free Web
• Power-law Strength-Degree Correlation From a Resource-Allocation Dynamics on Weighted Networks
• Predicting missing links and their weights via reliable-route-based method
• Link Prediction via Matrix Completion
• Link prediction via linear optimization
• Ultra accurate personalized recommendation via eliminating redundant correlations
• Reconstruction methods for networks: the case of economic and financial systems
• Evaluating Network Models: A Likelihood Analysis
• Playing the role of weak clique property in link prediction: A friend recommendation model
• Local-ring network automata and the impact of hyperbolic geometry in complex network link-prediction

Cited by in corpus (9)

• Progresses and Challenges in Link Prediction
• Discriminating abilities of threshold-free evaluation metrics in link prediction
• The maximum capability of a topological feature in link prediction
• A Network Science perspective of Graph Convolutional Networks: A survey
• Collaborative Filtering Approach to Link Prediction
• Understanding the network formation pattern for better link prediction
• Synthetic graphs for link prediction benchmarking
• A Fast Parallel Approach for Neighborhood-based Link Prediction by Disregarding Large Hubs
• Domain matters: Towards domain-informed evaluation for link prediction