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.

Dataset

The dataset consists of Singapore-based twitter users in the year 2009. The friends and followers network of top-1000 Singapore users is crawled along with their tweets. The dataset consists of number of tweets |T| = 1,021,039 and number of users |S| = 6748.

Methodology

• Homophily

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

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

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

To answer the above questions, topics are extracted from the tweets of the user. 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 Model 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 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.

Study Plan

Some terminology used extensively in the paper

• Homophily
• Hypothesis testing

• Latent Dirichlet Model

• Jensen's Distance

• Pagerank

• Kendall's correlation

Related Papers

Tunk Rank is similar to Twitter Rank, but does not consider the interaction between the users based on the content.

Haveliwala et al describes the topic-sensitive pagerank algorithm (TSPR).