Link prediction via linear optimization

Abstract

Link prediction is an elemental challenge in network science, which has already found applications in guiding laboratorial experiments, digging out drug targets, recommending friends in social networks, probing mechanisms in network evolution, and so on. With a simple assumption that the likelihood of the existence of a link between two nodes can be unfolded by a linear summation of neighboring nodes' contributions, we obtain the analytical solution of the optimal likelihood matrix, which shows remarkably better performance in predicting missing links than the state-of-the-art algorithms for not only simple networks, but also weighted and directed networks. To our surprise, even some degenerated local similarity indices from the solution outperform well-known local indices, which largely refines our knowledge, for example, the direct count of the number of 3-hop paths between two nodes more accurately predicts missing links than the number of 2-hop paths (i.e., the number of common neighbors), while in the previous studies, as indicated by the local path index and Katz index, the statistics on longer paths are always considered to be complementary to but less important than those on shorter paths.

arXiv comment29 pages, 3 figures and 5 tables

References in corpus (26)

• Emergence of scaling in random networks
• Community structure in social and biological networks
• Assortative mixing in networks
• The architecture of complex weighted networks
• Robust Recovery of Subspace Structures by Low-Rank Representation
• Link Prediction in Complex Networks: A Survey
• Analysis of weighted networks
• Hierarchical structure and the prediction of missing links in networks
• Predicting Missing Links via Local Information
• A Review of Relational Machine Learning for Knowledge Graphs
• Vital nodes identification in complex networks
• Recommender Systems
• Clustering in Complex Directed Networks
• Missing and spurious interactions and the reconstruction of complex networks
• Effective and Efficient Similarity Index for Link Prediction of Complex Networks
• Power-law Strength-Degree Correlation From a Resource-Allocation Dynamics on Weighted Networks
• Predicting Positive and Negative Links in Online Social Networks
• Korean university life in a network perspective: Dynamics of a large affiliation network
• Potential Theory for Directed Networks
• Supervised Random Walks: Predicting and Recommending Links in Social Networks
• Predicting missing links and their weights via reliable-route-based method
• Link Prediction via Matrix Completion
• Ultra accurate personalized recommendation via eliminating redundant correlations
• Evaluating Network Models: A Likelihood Analysis
• Governance in Social Media: A case study of the Wikipedia promotion process
• Predicting link directions via a recursive subgraph-based ranking

Cited by in corpus (11)

• Progresses and Challenges in Link Prediction
• Predicting the Future of AI with AI: High-quality link prediction in an exponentially growing knowledge network
• Experimental analyses on 2-hop-based and 3-hop-based link prediction algorithms
• Collaborative Filtering Approach to Link Prediction
• Understanding the network formation pattern for better link prediction
• SSNE: Effective Node Representation for Link Prediction in Sparse Networks
• Missing links as a source of seemingly variable constants in complex reaction networks
• Link Prediction via controlling the leading eigenvector
• Network Reconstruction and Controlling Based on Structural Regularity Analysis
• Domain matters: Towards domain-informed evaluation for link prediction
• A Preference Random Walk Algorithm for Link Prediction through Mutual Influence Nodes in Complex Networks