Difference between revisions of "Liben-Nowell Kleinberg J. Am.Soc.Inf.Sci.2007"
| (14 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
The Link-Prediction Problem for Social Networks | The Link-Prediction Problem for Social Networks | ||
| − | |||
| − | |||
== Citation == | == Citation == | ||
| Line 18: | Line 16: | ||
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>. | 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. | ||
| − | <math> | + | 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. |
| − | |||
| − | </math> | ||
| − | + | == 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)]] | ||
Latest revision as of 02:10, 27 September 2012
The Link-Prediction Problem for Social Networks
Contents
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
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 in which each edge represents an interaction at a particular time . For two times , denote the sub-graph of consisting of all edges representing the interactions happening between and . A link-prediction problem can be formalized as given four time and the network , to output or predict a list of edges not present in but appear in the network .
![{\displaystyle G[t,t^{'}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/285ad0866a1bbccd8964bbef0d78131b21cdcbf5)
![{\displaystyle G[t_{0},t_{0}^{'}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/272260ba1dbe22a26cfe59aa5a61942aaa1553b5)
![{\displaystyle G[t_{1},t_{1}^{'}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4f7062cae1a9d058d238e9d3a370a7ca7cd233c)
A List of Methods for Link Prediction
All the following methods assign a connection weight to node pair . We can group them in a less strict way and you can check the definition of each method in its own page.
| Methods Based on Node Neighborhoods | Common neighbors, Jaccard's Coefficient, Adamic/Adar, Preferential Attachment |
| Methods Based on the Ensemble of All Paths | Katz, Hitting time |
| 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 , which is the number of new links from the test set, and count how many of edges from these are in the test set.
Result
The performance is compared with a random predictor.
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.
Study Plan
- About Adamic/Adar score
- To understand which graph information these features represent
