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

The Link-Prediction Problem for Social Networks

This is not a final version, under construction!

== 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]], Jaccard's coefficient, Adamic/Adar, Preferential Attachment
|-
| Methods Based on the Ensemble of All Paths || Katz, Hitting Time, rooted PageRank
|-
| Others || graph distance, 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.

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.

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.

The widely cited [[RelatedPaper::Pang et al EMNLP 2002]] paper was influenced by this paper - but considers supervised learning techniques.  The choice of movie reviews as the domain was suggested by the (relatively) poor performance of Turney's method on movies.

An interesting follow-up paper is [[RelatedPaper::Turney and Littman, TOIS 2003]] which focuses on evaluation of the technique of using PMI for predicting the [[semantic orientation of words]].

== Study Plan ==