ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2017, Vol. 54 ›› Issue (2): 361-368.doi: 10.7544/issn1000-1239.2017.20150819

Previous Articles     Next Articles

tsk-shell: An Algorithm for Finding Topic-Sensitive Influential Spreaders

Gou Chengcheng1,2, Du Pan1, He Min1,2,3, Liu Yue1, Cheng Xueqi1   

  1. 1(CAS Key Laboratory of Network Data Science and Technology (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190);2(University of Chinese Academy of Sciences, Beijing 100049);3(National Computer Network and Information Security Management Center, Beijing 100029)
  • Online:2017-02-01

Abstract: Discovering influential spreaders is a valuable task in social networks, especially for the popularity prediction and analysis of online contents on microblogs, such as Twitter and Weibo. The k-shell decomposition (k-core), which identifies influential spreaders located in the core of a network, attracts more attention due to its simpleness and effectiveness compared with various related methods, such as indegree, betweenness centrality and PageRank. However, k-shell method only considers the factor of the network position of nodes and ignores the impacts of the content itself in information diffusion. The content itself plays an important role in the process of diffusion. For example, ones just retweet their interested tweets in microblogs. The spread ability of users depends not only on topology structures but also on the published contents, and therefore a unified model considering the two aspects simultaneously is proposed to model users' influence. Specifically, the topics hidden in user generated contents (UGC) are exploited to model the users' propagation probability and a topic-sensitive k-shell (tsk-shell) decomposition algorithm is proposed. Experimental studies on a real Twitter dataset show that the tsk-shell outperforms traditional k-shell by 40% on average in the task of finding top k influential users, which proves the effectiveness of the tsk-shell algorithm.

Key words: influential spreader, k-shell decomposition, social network, information diffusion, propagation probability, microblogs

CLC Number: