Sun et. al., ICDM 2005

This a Paper discussed in Social Media Analysis 10-802 in Spring 2010.

Citation

Measuring user influence in twitter: The million follower fallacy, Cha, M. and Haddadi, H. and Benevenuto, F. and Gummadi, K.P., ICWSM 2010

Online version

[http://snap.stanford.edu/class/cs224w-readings/cha10influence.pdf Measuring User Influence in Twitter: The Million Follower Fallacy ]

Summary

This paper characterize influence of a user in social media. A more influential user causes others who are connected with him to act in a certain way. We can use information about influence in some practical applications such as viral marketing.

Three different measures for influence are defined in the paper.

Twitter data collected for 54M users is used for experiment. Total number of follow links present in the dataset is 1,963,263,821. Dataset has 1,755,925,520 number of tweets.

Three different measures of influence used are:

1. Indegree: Total number of followers. Essentially it computes how many people at most read tweets of a particular twitter.

2. Mention: Number of mentions for a twitter. This reflects how many people has listened to a tweeter and mentioned him/her in their tweets.

3. Retweets: Number of retweets for a specific user.

Authors also investigate in the paper whether the influence of a user hold across all topics or it is topic specific?

Findings

Influence computed using above measures is then compared using Spearman’s rank correlation[1]

Correlation between measures is as following:

Indegree vs retweets: .549

Indegree vs mentions: .638

Retweets vs mentions: .580

This shows that there is stronger correlation between Indegree and mentions.

To compute influence for a particular topic, they choose tweets related to three topics. These topics are the Iranian presidential election, the outbreak of the H1N1 influenza, and the death of Michael Jackson. Among the users who tweeted about these topics, there were 13,219 users who tweeted about all three topics.

They found that Mentions show an stronger correlation across topics than retweets.

Discussion

This paper poses two important social problems related to bipartite social graphs and explained how those problems can be solved efficiently using random walks.

They also claim that the neighborhoods over nodes can represent personalized clusters depending on different perspectives.

During presentation one of the audiences raised question about is anomaly detection in this paper similar to betweenness of edges defined in Kleinber's text as discussed in Class Meeting for 10-802 01/26/2010. I think they are similar. In the texbook they propose, detecting edges with high betweenness and using them to partition the graph. In this paper they first try to create neighbourhood partitions based on random walk prbabilities and which as a by product gives us nodes and edges with high betweenness value.

Related papers

There has been a lot of work on anomaly detection in graphs.

• The paper by Moonesinghe and Tan ICTAI06 finds the clusters of outlier objects by doing random walk on the weighted graph.
• The paper by Aggarwal SIGMOD 2001 proposes techniques for projecting high dimensional data on lower dimensions to detect outliers.

Study plan

• Article:Bipartite graph:[2]
• Article:Anomaly detection:[3]
• Paper:Topic sensitive pagerank:[4]
  • Paper:The PageRank Citation Ranking: Bringing Order to the Web:[5]
• Paper:Multilevel k-way Partitioning Scheme for Irregular Graphs:[6]