Title: 《Leaders in Social Networks, the Delicious Case》

Author:  Linyuan Lü, Yi-Cheng Zhang, Chi Ho Yeung, Tao Zhou

Download: http://www.plosone.org/article/info%3Adoi%2F10.1371%2Fjournal.pone.0021202

With the development of web techniques, the online social webs become more and more strong and provide better service. Such as delicious, a bookmarking service web where you can discover and store interesting URLs and share them with your friends. Also three of the world famous social webs, twitter, facebook and linkedin where you can make friends easily and all over the world.

And recently, more and more people have realized that, today, these social webs are not only a platform for making friends, they are now becoming a more efficient way to get the information. People can discover interesting news articles, get recommendations for movies and browse funny videos via their social streams. The social webs are evolving to be new gateways to the Internet. For me, the news form my own social networks better match my tastes than from Google.

Building on these social webs, an interesting problem is “Who are the influential users or say leadership of these social networks.” For this, more and more people have realized its great values.

For information security, it can help the government to supervise the public opinions and control the rumor spread (舆情控制). In addition, it also creates great commercial value from advertisement delivery and news spreading which are extremely interested by advertisers and marketers as they try to identify “influencers” who can broadly spread their messages (网络营销) . For example, on Sina Blog, the China’s version of twitter, there is a company, running for only 4 months, has created many big accounts with fans more than 2 million in total. For an account with "twenty thousand” fans, the price for sending one message is 200-300RMB.

(http://tech.sina.com.cn/i/2011-02-14/13495174556.shtml)

Here we need to point out that more fans does not mean high influence, since there are many spam users, in Chinese we call them 僵尸粉 or 水军 all over the social webs. They are worthless fans. In a word, how to well utilize the network structure to identify the influencers is still challenging.

A good ranking algorithm is expected to meet the following three points:

1) Effectiveness:

Whether the top-ranked users are really influencers?

2) Robustness against noisy data

Since the social network data may be unreliable and with some spurious and missing links, the algorithm should be tolerant of such noisy data.

3) Resilience to spammers

Sybil attack, spammers create many fake accounts to obtain high rank or score, the algorithm should be robust to such attack.

Motivated by this, we design an adaptive and parameter-free algorithm called “LeaderRank” (I prefer “FreeRank”) which is also a random-walk-based method akin to PageRank, but with much difference. Extensive analyses show that our LeaderRank wins PageRank on all above three points.