ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2017, Vol. 54 ›› Issue (2): 361-368.doi: 10.7544/issn1000-1239.2017.20150819

• 信息处理 • 上一篇    下一篇

tsk-shell:一种话题敏感的高影响力传播者发现算法

笱程成1,2,杜攀1,贺敏1,2,3,刘悦1,程学旗1   

  1. 1(中国科学院网络数据科学与技术重点实验室(中国科学院计算技术研究所) 北京 100190); 2(中国科学院大学 北京 100049); 3(国家计算机网络与信息安全管理中心 北京 100029) (gouchengcheng@gmail.com)
  • 出版日期: 2017-02-01
  • 基金资助: 
    国家“九七三”重点基础研究发展计划基金项目(2012CB316303, 2014CB340401);国家“八六三”高技术研究发展计划基金项目(2015AA015803,2014AA015204);中国科学院重点部署项目(KGZD-EW-T03-2);国家自然科学基金项目(61232010,61572473,61303156,61502447);国家242信息安全计划基金项目(2015F028);山东省自主创新及成果转化专项(2014CGZH1103);欧盟第七科技框架计划项目(FP7)(PIRSES-GA-2012-318939)

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

摘要: 在社交网络中,挖掘高影响力的信息传播者,对微博服务中内容的流行度分析和预测是非常有价值的任务.与众多相关方法相比,k-shell分解(k-core)方法因其简洁高效、平均性能好的特点吸引了越来越多的研究人员的兴趣.但是,目前k-shell方法着重考虑节点在网络中的位置因素,而忽略了话题在信息传播中的影响.因此,为了利用用户历史数据中蕴含的话题对消息的传播概率进行细粒度的建模,提出了一种话题敏感的k-shell(topic-sensitive k-shell, tsk-shell)分解算法.在真实Twitter数据集上实验表明,在发现top k高影响力传播者任务中,tsk-shell比k-shell的性能平均提高了约40%,证明了tsk-shell算法的有效性.

关键词: 高影响力传播者, k-shell分解, 社交网络, 信息扩散, 传播概率, 微博

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

中图分类号: