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

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

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

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 topicsensitive 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 kinfluential users,which proves the effectiveness of the tsk-shell algorithm.