基于抽样的影响力传播成本最小化算法

盛 俊,李 斌,陈 崚

(1.扬州大学 信息工程学院，江苏 扬州 225000； 2.扬州市职业大学 信息工程学院，江苏 扬州 225000)

0 引 言

近年来，随着Twitter、Facebook、谷歌、微博等社交网络的蓬勃发展，网络分析成为社区检测[1]、关系挖掘[2]、度量学习[3]、网络结构分析[4]、链接预测[5]等领域的研究热点。社交网络[6]是由各种实体构成的交流平台，它形成了一个图的结构，图中的顶点为各种实体，连接它们的边反映了它们的相互关系。随着互联网的不断发展，人们使用社交网络也越来越频繁。社交网络中，用户的观点、行为和情感都会受到某些用户影响力的传播作用的影响。而社交网络的流行，也带来了影响力传播的一些新的应用，例如舆情控制[7]、病毒式营销[8]等。因此，如何衡量和预测一个或多个用户对其社交范围内其他用户的影响力是一个关键的问题。影响力最大化[9]就是要在一个社交网络中找出一个影响力的发散源节点，即“种子”集合，使得这些集合中的节点在社交网络中扩散的影响力最大化。影响力最大化在生物信息学[10]、政治选举、病毒营销[11,12]、经济学[13]、推荐[14]、舆情监测[15]等领域得到了广泛的应用。

影响力最大化的问题本质上是一个离散优化问题，常用的传播模型有独立级联模型和线性阈值模型。影响力最大化的问题可以用贪心法来求解。然而，贪心算法的时间复杂度很高，大部分的计算时间用来估计种子集合的影响力范围。因此，随后的很多人对其效率进行了改进。Sun等[16]提出了一种基于有影响力种子接班人的可扩展的影响力最大化方法，算法借助种子顶点接班人的概念，减少了影响力传播的评估次数。……