Weng et al WSDM 10

This a Paper reviewed for Social Media Analysis 10-802 in Fall 2012.

Citation

author    = {Jianshu Weng and
              Ee-Peng Lim and
              Jing Jiang and
              Qi He},
 title     = {TwitterRank: finding topic-sensitive influential twitterers},
 booktitle = {WSDM},
 year      = {2010},
 pages     = {261-270},
 ee        = {http://doi.acm.org/10.1145/1718487.1718520},
 crossref  = {DBLP:conf/wsdm/2010},
 bibsource = {DBLP, http://dblp.uni-trier.de}

Online Version

TwitterRank: finding topic-sensitive influential twitterers

Summary

The paper is based on a sub-topic of social influence. The primary goal of the work is to find influential users on Twitter website. The work proposes TwitterRank, a variation of Pagerank algorithm to measure influence of users in Twitter. TwitterRank takes into consideration the topical similarity between the users along with the link structure to measure influence of followers on users. The motive behind following a user and having mutual followers was studied and the presence of homophily in the network was detected. The experimental results on Twitter dataset shows that TwitterRank yields a significantly better performance than the baseline techniques.

Methodology

Homophily

In order to verify topical similarity in friendships, two question have been explored.

Whether users with "following" relationships are more topically similar than random users.

Whether users with reciprocal "following" relationships are more topically similar than those without it.

To answer the above questions, topics are distilled from the twitter text. The topics are extracted from the user documents, where a user document is considered as the list of all the tweets by a user.Latent Dirichlet Allocation is applied to learn the topics in an unsupervised method. The result of applying LDA is represented as -

1. $DT$, a $D\times T$, where $D$ is the number of twitter users and $T$ is the number of topics.

2. $WT$, a $W\times T$, where $W$ is the number of unique words and $T$ is the number of topics.

3. $Z$ is a $1\times N$ matrix, where $N$ is the total number of words and $Z_{i}$ is the topic assignment for word $w_{ij}$

The topical difference between users $s_{i}$ and $s_{j}$ is calculated as

$dist(i,j)={\sqrt {2\ast D_{js}(i,j)}}$

Hypothesis Testing is used to answer the two questions using the matrix. The positive answers obtained to both the questions justifies the presence of topical similarities between users. This homophily motivates the use of TwitterRank to measure the topic-sensitive influence for users.

TwitterRank - topic-sensitive influence measure

A directed edge is constructed with vertex V as the twitter users, and edge E as the edge from a twitter user to its friend ( whose tweets he follows). A random surfer visits each twitter user with certain probability by following the appropriate edge in $D$. TwitterRank performs a topic-sensitive random walk, the transition probability from one user to another is based on the topical similarity between the two users.

Evaluation

The Twitter Rank algorithm has been compared to the following baselines.

• In-degree (InD) - Measures the influence of Twitter users by the number of followers.
• PageRank (PR) - Measures the influence of Twitter users by making use of only the link structure.
• Topic-sensitive PageRank (TSPR) - Measures the topic-sensitive influence by not considering the topic-sensitive transition probabilities.

• Correlation between the rank lists generated by different algorithms is compared by using Kendall's correlation.

The inference from the table is that TR is most similar to TSPR.

• Performance in recommendation task.

The algorithm for recommendation task is as follows.

The comparison of different algorithms on the recommendation task.

The conclusion is that TR outperform InD and PR by a large margin. TR outperforms TSPR as TSPR propagates a twitter user's influence using same transition probability for different topics.

Observations

• The study detects the presence of homophily in Social networks. The reciprocal relationship between friends suggests that there is a presence of topic similarity between them.
• The paper proposes a simple new methodology to measure the influence of users by considering the topic similarity along with the link structure.
• The paper presents a static structure of the network. A possible and a useful extension, could be the modeling of the dynamics of the twitter network using TwitterRank.
• The other interactions between the user and his friends such as the mentions/reply/retweets could be given more weight than just a mere friendship link.

Study Plan

• Some terminology used extensively in the paper
  • Homophily
  • Jensen's Distance
  • Kendall's correlation
• Haveliwala et al describes the topic-sensitive pagerank algorithm (TSPR)
  • D Rafiei et al(2009) talks about computing web page reputations.
• McPherson et al(2001) Homophily in Social Network.
• Tunk Rank is similar to Twitter Rank, but does not consider the interaction between the users based on the content.

.