Link Prediction via Matrix Completion

Abstract

Inspired by practical importance of social networks, economic networks, biological networks and so on, studies on large and complex networks have attracted a surge of attentions in the recent years. Link prediction is a fundamental issue to understand the mechanisms by which new links are added to the networks. We introduce the method of robust principal component analysis (robust PCA) into link prediction, and estimate the missing entries of the adjacency matrix. On one hand, our algorithm is based on the sparsity and low rank property of the matrix, on the other hand, it also performs very well when the network is dense. This is because a relatively dense real network is also sparse in comparison to the complete graph. According to extensive experiments on real networks from disparate fields, when the target network is connected and sufficiently dense, whatever it is weighted or unweighted, our method is demonstrated to be very effective and with prediction accuracy being considerably improved comparing with many state-of-the-art algorithms.

References in corpus (10)

• Cooperative Game Theory Approaches for Network Partitioning
• Hierarchical structure and the prediction of missing links in networks
• Predicting Missing Links via Local Information
• Community Structure in Jazz
• Missing and spurious interactions and the reconstruction of complex networks
• Effective and Efficient Similarity Index for Link Prediction of Complex Networks
• Link Prediction in Complex Networks: A Mutual Information Perspective
• Predicting the connectivity of primate cortical networks from topological and spatial node properties
• Local degree blocking model for link prediction in complex networks
• Improving personalized link prediction by hybrid diffusion

Cited by in corpus (12)

• Progresses and Challenges in Link Prediction
• Link prediction via linear optimization
• Experimental analyses on 2-hop-based and 3-hop-based link prediction algorithms
• Discriminating abilities of threshold-free evaluation metrics in link prediction
• Predicting hyperlinks via hypernetwork loop structure
• Network Topology Mapping from Partial Virtual Coordinates and Graph Geodesics
• Matrix Completion with Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Sampling
• Collaborative Filtering Approach to Link Prediction
• Link Prediction via controlling the leading eigenvector
• A generalized method toward drug-target interaction prediction via low-rank matrix projection
• Network Reconstruction and Controlling Based on Structural Regularity Analysis
• Binary matrix completion with nonconvex regularizers