基于社团结构的影响力最大化问题综述张碧野兰州大学220150926071计算机系统结构摘要:随着互联网技术的不断发展和社会网络的流行，越来越多研究者被社会网络所吸引，其中影响力最大化问题成为了研究者们持续关注的重点。影响力最大化问题的目标是挖掘社会网络中最有影响力的传播节点，即从社会网络中选取k个初始传播节点，从这些节点开始对整个社会网络进行影响为传播，直到影响节点数量达到最大。影响力最大化问题在市场营销，商品推荐，谣言控制等领域引起了大量研究者的重视，并且具有广泛的应用前景。而基于社团结构的影响力最大化问题是最近几年的一个热点，不同于传统的仅仅使用贪婪策略来直接实现影响力最大化方法，一方面，它可以通过先对社会网络进行社团划分，然后取每个社团的一部分重要的节点来放在一起作为候选节点，再使用贪婪策略，从而达到降低网络规模，运行时间的效果。另一方面，它可以通过对社团划分过程中节点重要性的体现，利用网络拓扑结构来直接获取影响力最大的节点。基于社团结构影响力最大化问题可以描述为：在有明显社团结构的网络中，利用社团结构特点来直接（通过节点在社团中的特点直接找到社团中最重要的节点）或间接（通过贪婪算法）获取k(或最少)个影响力最大化的节点。关键词:复杂网络；影响力最大化；社团划分引言：社会网络是由许多节点构成的一种社会结构，节点通常是指个人或组织，社会网络代表各种社会关系，经由这些社会关系，把人们或组织串连起来。社会关系包括朋友关系、同学关系、生意伙伴关系、种族信仰关系等[18]。在过去十年中，由于社会网络的广泛应用，社会网络的研究越来越受到关注，近来以Facebook,Twitter,微博，人人网等为代表的社会网络平台发展迅猛，为社会网络提供了海量的数据信息。社交网络中的影响力最大化问题的研究有着十分重要的现实意义，它在市场营销、广告发布、舆情预警以及社会安定等方面有十分重要的应用。比如，一个公司想要推广一个新研发出的产品，但是由于预算有限，只能将少量的新产品提供给用户体验使用。但是公司又希望这些体验用户能够影响到用户的朋友来购买使用这个产品，还希望用户的朋友能影响到他们的朋友，这样，通过“口碑传播”，公司就能够获得一大批用户来购买新产品。这个问题被定义为影响力最大化问题[19]。影响力最大化问题可概括为：给定一个社会网络图和一种特定的影响力传播模型，在社会网络中找出k个节点进行传播，使最终被这k个节点影响的节点数目...
