Link Prediction via controlling the leading eigenvector

Abstract

Link prediction is a fundamental challenge in network science. Among various methods, similarity-based algorithms are popular for their simplicity, interpretability, high efficiency and good performance. In this paper, we show that the most elementary local similarity index Common Neighbor (CN) can be linearly decomposed by eigenvectors of the adjacency matrix of the target network, with each eigenvector's contribution being proportional to the square of the corresponding eigenvalue. As in many real networks, there is a huge gap between the largest eigenvalue and the second largest eigenvalue, the CN index is thus dominated by the leading eigenvector and much useful information contained in other eigenvectors may be overlooked. Accordingly, we propose a parameter-free algorithm that ensures the contributions of the leading eigenvector and the secondary eigenvector the same. Extensive experiments on real networks demonstrate that the prediction performance of the proposed algorithm is remarkably better than well-performed local similarity indices in the literature. A further proposed algorithm that can adjust the contribution of leading eigenvector shows the superiority over state-of-the-art algorithms with tunable parameters for its competitive accuracy and lower computational complexity.

arXiv comment22 pages, 4 figures, 4 tables

References in corpus (24)

• Emergence of scaling in random networks
• Assortative mixing in networks
• LINE: Large-scale Information Network Embedding
• Specificity and stability in topology of protein networks
• Link Prediction in Complex Networks: A Survey
• Hierarchical structure and the prediction of missing links in 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
• Spectra of "Real-World" Graphs: Beyond the Semi-Circle Law
• Evaluating Link Prediction Methods
• Power-law Strength-Degree Correlation From a Resource-Allocation Dynamics on Weighted Networks
• Combining complex networks and data mining: why and how
• Stacking Models for Nearly Optimal Link Prediction in Complex Networks
• Progresses and Challenges in Link Prediction
• Link Prediction via Matrix Completion
• Computational Socioeconomics
• Link prediction via linear optimization
• Evaluating Network Models: A Likelihood Analysis
• Robust Classification for Imprecise Environments
• Linguistic data mining with complex networks: a stylometric-oriented approach
• Collaborative Filtering Approach to Link Prediction

Cited by in corpus (1)

• Progresses and Challenges in Link Prediction