View source for Liben-Nowell Kleinberg J. Am.Soc.Inf.Sci.2007

The Link-Prediction Problem for Social Networks

== Citation ==

Liben-Nowell, D. and Kleinberg, J. (2007), The link-prediction problem for social networks. J. Am. Soc. Inf. Sci., 58: 1019–1031. doi: 10.1002/asi.20591

== Online version ==

[http://dm.kaist.ac.kr/kse625/resources/Liben-Nowell_2007.pdf PDF]

== Summary ==

This paper extensively evaluates many unsupervised methods using topological features of the network for link prediction and compares their performances over different data sets. The result shows that Adamic-Adar, which measures the node similarity, has the best performance.

== Problem Setup ==
Given a social network <math>G = <V, E></math> in which each edge represents an interaction at a particular time <math>t(e)</math>. For two times <math>t < t^'</math>, <math>G[t, t^']</math> denote the sub-graph of <math>G</math> consisting of all edges representing the interactions happening between <math>t</math> and <math>t^'</math>. A link-prediction problem can be formalized as given four time <math>t_0 < t^'_0 < t_1 < t^'_1</math> and the network <math>G[t_0, t^'_0]</math>, to output or predict a list of edges not present in <math>G[t_0, t^'_0]</math> but appear in the network <math>G[t_1, t^'_1]</math>.

== A List of Methods for Link Prediction ==
All the following methods assign a connection weight <math>\textrm{score}(x,y)</math> to node pair <math><x,y></math>. We can group them in a less strict way and you can check the definition of each method in its own page.

{| class="wikitable" border="1"
|-
| Methods Based on Node Neighborhoods || [[Methods::Common neighbors]], [[Methods::Jaccard's Coefficient]], [[Methods::Adamic/Adar]], [[Methods::Preferential Attachment]]
|-
| Methods Based on the Ensemble of All Paths || [[Methods::Katz]], [[Methods::Hitting time]]
|-
| Others || graph distance, [[Methods::SimRank]]
|}

== Data sets and Experiments ==
The paper works with five co-authorship networks, obtained from the author lists of articles contained in five sections of the physics e-Print arXiv. The training interval is defined to be the 3 years from 1994 through 1996 and test interval to be the 3 years from 1997 through 1999.

Each link predictor outputs a ranked list of pairs and the paper takes the first <math>n</math>, which is the number of new links from the test set, and count how many of edges from these <math>n</math> are in the test set.

== Result ==
The performance is compared with a random predictor.

[[File:LN_K_2007_Result.jpg]]

We can see that Adamic/Adar outperforms other methods and for more detailed results please refer to the paper.

== Related papers ==
Most link prediction solutions can fall to two directories, one is to use topological features and the other is to use node or edge information.

[[RelatedPaper::Link propagation: A fast semi-supervised learning algorithm for link prediction]] suggests a semi-supervised framework which need a node similarity matrix as input. Many applications like protein-protein interactions and social networks are able to provide this information.

[[RelatedPaper::Supervised Random Walks: Predicting and Recommending Links in Social Networks]] adopts a random walk framework and use edge and node information as features to train a transition rate over each edge to maximize the probability of random walk stopping time on positive nodes.

== Study Plan ==
* About Adamic/Adar score
**[[Paper::Adamic, L.A., & Adar, E. (2003). Friends and neighbors on the Web. Social Networks, 25(3), 211–230]]
* To understand which graph information these features represent
**[[Paper::Davidsen, J., Ebel, H., & Bornholdt, S. (2002). Emergence of a small world from local interactions: Modeling acquaintance networks. Physical Review Letters, 88(128701)]]