• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

J4 ›› 2014, Vol. 36 ›› Issue (12): 2346-2354.

• 论文 • Previous Articles     Next Articles

A fast and accurate node influence sorting
algorithm in online social networks          

ZOU Qing1,ZHANG Yingying2,CHEN  Yifan1,ZHANG Shigeng1,DUAN Guihua1   

  1. (1.School of Information Science and Engineering,Center South University,Changsha 410083;
    2.Department of Electronic Engineering,Zaozhuang Vocational College of Scienc & Technology,Tengzhou 277500,China)
  • Received:2014-09-04 Revised:2014-11-07 Online:2014-12-25 Published:2014-12-25

Abstract:

In large Online Social Networks (OSNs), sorting nodes according to their influence is an important research issue. The most influential (set of) nodes can be found by sorting nodes, which is essential to the control of information dissemination, public opinion control and analyses, and onpurpose advertising. Existing influence sorting algorithms either need global topology information of the network to calculate the influence of individual nodes (e.g., the betweennessbased algorithms), which are usually time consuming and thus are not applicable to large scale networks, or use the traditional sorting algorithms designed for web page ranking (e.g., PageRank), which cannot well handle the properties of OSNs like the existence of end nodes and different relationship between different nodes. The traditional PageRank algorithm is enhanced from two aspects to make it applicable to node sorting in large scale OSNs. Firstly, different residual weights are assigned to nodes according to the weights of links in the weight collection phase of PageRank, which effectively mitigates the negative influence of end nodes on the sorting accuracy. Secondly, in the voting process, the diversity among different nodes is considered and a neighborhood based algorithm is proposed to assign weights to different nodes, which effectively improve the sorting accuracy. The performance of the proposed algorithm is evaluated on a sample network constructed with 15,000 real users sampled from Sina Weibo. It is shown that the enhanced algorithm can find more than 40% of the 1000 most influential nodes in the sample network, while the traditional PageRank algorithm counterpart can find only 11%. Meanwhile, compared with the betweennessbased algorithms, the proposed algorithm achieves similar or even better sorting accuracy with much less time cost.

Key words: online social networks;influence node sorting;influence evaluation;PageRank improvement