Link prediction based on local random walk

By Weiping Liu, Linyuan Lu. 2010

554 citations recorded by the source corpus.

The problem of missing link prediction in complex networks has attracted much attention recently. Two difficulties in link prediction are the sparsity and huge size of the target networks. Therefore, to design an efficient and effective method is of both theoretical interest and practical significance. In this letter, we proposed a method based on local random walk, which can give competitively good or even better prediction than other random-walk–based methods while having a much lower computational complexity.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/4ea329ed9110dc991216b635545df07aeeba779a

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

Continuous-Time Dynamic Network Embeddings (2018, background): “Random walks are at the heart of many important applications such as ranking [50], community detection [48, 54], recommendation [10], link prediction [39], influence modeling [30], search engines [36], image segmentation [25], routing in wireless sensor networks [62], and timeseries forecasting [23]”
Identifying influential nodes in complex networks (2012, unknown): “[42].”
A Survey of Link Prediction in Complex Networks (2016, methodology): “This Markov chain of randomly selected nodes is known as a random walk on the graph [Liu and L¨u 2010].”
Link Prediction in Complex Networks: A Survey (2010, methodology): “[79] Liu and Lü applied a simple formdetermined by node degree, namely qx = kx M .”
Predicting potential drug-drug interactions by integrating chemical, biological, phenotypic and network data (2017, methodology): “There are a great number of successful applications in the network analysis [35 – 38].”
Recommender Systems (2012, methodology): “In [158] it was suggested to use a simple approach where q is determined by node degree: q x = k x / M .”
A Review of Relational Machine Learning for Knowledge Graphs (2015, methodology): “Quasi-local similarity indices like the Local Katz index [56] or Local Random Walks [103] try to balance predictive accuracy and computational complexity by deriving the similarity of entities from paths and random walks of bounded length.”