The link prediction problem for social networks

By David Liben-Nowell, Jon M. Kleinberg. 2003

2,936 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics, Graph Learning, Network Science & Complex Systems

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

In Graph Learning

In Network Science & Complex Systems

Citations in the corpus

Representation Learning on Graphs: Methods and Applications (2017, methodology): “To extract structural information from graphs, traditional machine approaches often rely on summary graph statistics ( e.g. , degrees or clustering coefﬁcients) [6], kernel functions [57], or carefully engineered features to measure local neighborhood structures [39].”
Graphite: Iterative Generative Modeling of Graphs (2018, background): “Graphs arise in a wide variety of domains in physical sciences, information sciences, and social sciences, and consequently algorithms for unsupervised representation learning of such data have several downstream applications, including node classification, link prediction, and community detection [”
PTE: Predictive Text Embedding through Large-scale Heterogeneous Text Networks (2015, background): “Therefore, the word representations learned by embedding the heterogeneous text network are not only more robust but also optimized for that task.”
Community detection in graphs (2009, background): “This is a very important problem (Liben-Nowell and Kleinberg, 2003): edges of real graphs are the result of observations/experiments, that may fail to discover some relationships between the units of the system.”
A Review of Relational Machine Learning for Knowledge Graphs (2015, background): “Second, it allows the f p¨q function to be any function, not just a probability (but we do assume that larger f values mean the triple is more likely to be correct).”
Supervised random walks: predicting and recommending links in social networks (2010, methodology): “The unsupervised methods for link prediction were extensively evaluated by Liben-Nowell and Kleinberg [21] who found that the Adamic-Adar measure of node similarity [1] performed best.”
Graph Embedding Techniques, Applications, and Performance: A Survey (2017, methodology): “Graph analytic tasks can be broadly abstracted into the following four categories: (a) node classification [6], (b) link prediction [5], (c) clustering [7], and (d) visualization [8].”
Link prediction in social networks: the state-of-the-art (2014, methodology): “Liben-Nowell and Kleinberg [102] provide useful information and insights for link prediction problem, with special reference to some classical prediction measures based on topological information of networks.”
Semantic Matching in Search (2014, background): “These include collaborative filtering [101, 1, 2, 102, 45, 149, 9, 44], image annotation [83, 76, 159], paraphrasing and textual entailment [62, 54, 139, 203, 55, 85, 165, 35], question answering [37, 126, 21, 205, 178, 130], cross-language information retrieval [64, 141, 140], short text conversati”
Network-Based Marketing: Identifying Likely Adopters Via Consumer Networks (2006, background): “Therefore, they cannot address whether wordof-mouth actually affects individual sales.”
New perspectives and methods in link prediction (2010, methodology): “The state-of-the-art in these methods is aggregated and compared in [11], and in Section 3.1 we oﬀer a brief explanation of the particular methods that we study.”
Modelling Chemical Reasoning to Predict Reactions (2016, background): “32 A path in a graph is a sequence of nodes p Li = ( n 0 , n 1 ,..., n L ) of length L , in which each two subsequent nodes n i and n i + 1 are connected by an edge.”
Like like alike — Joint Friendship and Interest Propagation in Social Networks Shuang (2011, methodology): “Some of them employ random walk methods [14] [22] or spectral graph algorithms [19] [20].”