Link Prediction in Complex Networks: A Survey

By Linyuan Lu, Tao Zhou. arXiv.org, 2010

2,843 citations recorded by the source corpus.

Link prediction in complex networks has attracted increasing attention from both physical and computer science communities. The algorithms can be used to extract missing information, identify spurious interactions, evaluate network evolving mechanisms, and so on. This article summaries recent progress about link prediction algorithms, emphasizing on the contributions from physical perspectives and approaches, such as the random-walk-based methods and the maximum likelihood methods. We also introduce three typical applications: reconstruction of networks, evaluation of network evolving mechanism and classification of partially labeled networks. Finally, we introduce some applications and outline future challenges of link prediction algorithms.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/8cd9aa720a3a2f9dcb52ad9eb1bf258a80ce0648

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

Citations in the corpus

Predicting potential drug-drug interactions by integrating chemical, biological, phenotypic and network data (2017, methodology): “The missing link prediction is an important topic of theoretical interest and practical significance in the complex network [33].”
Link Prediction Based on Graph Neural Networks (2018, background): “It is shown that high-order heuristics often perform better than first-order and second-order heuristics [6].”
User Profile Preserving Social Network Embedding (2017, background): “These approaches have been shown to be effective in a variety of network analytic tasks, ranging from node classification [Sen et al., 2008], anomaly detection [Bhuyan et al., 2014], community detection [Yang et al., 2013], to link prediction [Lü and Zhou, 2011].”
A Survey on Network Embedding (2017, background): “Link prediction, as one of the most fundamental problems on network analysis, has received a considerable amount of attention (Liben-Nowell and Kleinberg 2007; Lü and Zhou 2011).”
A Survey of Link Prediction in Complex Networks (2016, result): “Different reviews about this topic have been previously published and have influenced this work [Liben-Nowell and Kleinberg 2007; Al Hasan and Zaki 2011; Lü and Zhou 2011; Wang et al. 2015].”
Toward link predictability of complex networks (2015, background): “The link prediction problem has been a long-standing challenge in modern information science (13, 49).”
From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networks (2013, background): “A myriad of complicated techniques for topological link-prediction with two or more parameters to tune have been proposed 7,9,10 , even inspired by concepts that originate from statistical mechanics and theory of disordered systems.”
Network-based prediction of protein interactions (2018, background): “[12] Lü L & Zhou T, Link prediction in complex networks: A survey, Physica A 390 1150-1170 (2011).”
Weisfeiler-Lehman Neural Machine for Link Prediction (2017, background): “Empirical comparisons of these heuristics on different networks can be found in [10, 17].”
Identifying Influential Nodes in Large-Scale Directed Networks: The Role of Clustering (2013, background): “Studying the effects of clustering coefficient on the network evolving can provide insights into the understanding of growing mechanism and further help us to design better link prediction algorithms [35–37] and to explain the observation on information spreading through online social networks [30].”
Network Representation Learning: A Survey (2017, background): “theway for awide range of network analytic tasks to be easily and efficiently tackled in the new vector space, such as node classification [10], [11], link prediction [12], [13], clustering [2], recommendation [14], [15], similarity search [16], and visualization [17].”
WikiLinkGraphs: A complete, longitudinal and multi-language dataset of the Wikipedia link networks (2019, background): “The problem of predicting the appearance of links in time-evolving networks has received signiﬁcant attention (L ¨ u and Zhou 2011); the problem of predicting their disappearance, on the other hand, is less studied.”
Learning Discrete Structures for Graph Neural Networks (2019, background): “Several survey papers cover the large body of work ranging from link prediction in social networks to knowledge base completion (L¨u & Zhou, 2011; Nickel et al., 2016).”
Cross View Link Prediction by Learning Noise-resilient Representation Consensus (2017, methodology): “Various scoring methods have been proposed based on the topology of graphs: 1) Common Neighbor based methods: Adamic/Adar [1] assigns weight to each common neighbor based on the degree of the neighbors; 2) Path based methods such as Katz [9] and Local Path and Random Walk with Restart [14].”