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

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 $G=<V,E>$ in which each edge represents an interaction at a particular time $t(e)$. For two times $t<t^{'}$, $G[t,t^{'}]$ denote the sub-graph of $G$ consisting of all edges representing the interactions happening between $t$ and $t^{'}$. A link-prediction problem can be formalized as given four time $t_{0}<t_{0}^{'}<t_{1}<t_{1}^{'}$ and the network $G[t_{0},t_{0}^{'}]$, to output or predict a list of edges not present in $G[t_{0},t_{0}^{'}]$ but appear in the network $G[t_{1},t_{1}^{'}]$.

A List of Methods for Link Prediction

All the following methods assign a connection weight ${\textrm {score}}(x,y)$ to node pair $<x,y>$. 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
Example	Example
Example	Example

Brief description of the method

The algorithm takes a written review as an input. First it assigns a POS tag to each word in the review to identify adjective or adverb phrases in the input review. They have used PMI-IR algorithm to estimate the semantic orientation of a phrase. The Pointwise Mutual Information (PMI) between two words $w_{1}$ and $w_{2}$ is defined as follow:

$PMI(w_{1},w_{2})=log_{2}(p(w_{1}\ and\ w_{2})/p(w_{1})p(w_{2}))$

where $p(w_{1},w_{2})$ is the probability that $w_{1}$ and $w_{2}$ co-occur. They have defined the semantic orientation of a phrase as follow:

$SO(phrase)=PMI(phrase,'excellent')-PMI(phrase,'poor')$

We can modify the above definition to obtain the following formula:

$SO(phrase)=log_{2}({\frac {hits(phrase\ NEAR\ 'excellent')hits('excellent')}{hits(phrase\ NEAR\ 'poor')hits('poor')}})$

where operator NEAR means that the two phrases should be appeared close to each other in the corpus. Using the above formula they have calculated the average semantic orientation for a review. They have shown that the value of average semantic orientation for phrases in the items that are tagged as "recommended" by the users are usually positive and those that are tagged as "not recommended" are usually negative.

Experimental Result

This approach was fairly successful on a range of review-classification tasks: it achieved accuracy of between 65% and 85% in predicting an author-assigned "recommended" flag for Epinions ratings for eight diverse products, ranging from cars to movies. Many later writers used several key ideas from the paper, including: treating polarity prediction as a document-classification problem; classifying documents based on likely-to-be-informative phrases; and using unsupervised or semi-supervised learning methods.

Related papers

The widely cited 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 Turney and Littman, TOIS 2003 which focuses on evaluation of the technique of using PMI for predicting the semantic orientation of words.