论文部分内容阅读
社交网络影响力分析已经成为社交网络分析的重要方面,而其中的社交网络影响最大化问题也受到越来越多的关注,特别是Web 2.0时代下在线社交网络平台的兴起为影响最大化问题的研究提供了更加丰富的平台和研究数据。社交网络影响最大化问题是研究如何在社交网络中选择有限个数的影响力节点而使影响力传播达到最大。这个问题的研究对病毒式营销,推荐系统和突发事件检测等领域有重要意义。近年来,越来越多的影响最大化方法被提了出来,这些算法大致可以分为三类:针对贪婪算法的改进算法,基于社交网络社区结构特性的算法,基于社交网络节点特性的启发式方法。其中,针对贪婪算法的改进算法可以提升贪婪算法的效率,但仍不适合用于大规模社交网络中;基于社交网络社区结构特性的算法可以获得较好的效果和效率;基于社交网络节点特性的启发式方法的效率最高,但其得到的影响力节点的效果却不好。Memetic算法是近年来进化计算领域的一个研究热点,它是一种基于群体的全局搜索和基于个体的局部搜索的结合体,可以弥补这两者单方面的不足,获得较快的搜索效率和令人满意的结果。本文利用社区结构和Memetic算法的优点,将其应用于社交网络影响最大化问题中。本文所做的主要工作如下:(1)研究了社交网络中节点之间的结构相似性对社交网络影响最大化问题的影响,提出了基于节点相似性的度中心性方法。在该方法中,我们用节点之间的结构相似性来排除与度大的节点相似的节点,以此来减少影响力节点之间影响力传播的重叠,从而获得较大的影响力传播。(2)研究了Memetic算法在社交网络影响最大化问题上的应用。我们提出了基于Memetic算法的影响最大化问题,将局部搜索策略加入Memetic算法中,改善了传统遗传算法收敛速度慢,容易陷入局部最优的缺点。同时,该算法与社交网络的社区结构特性结合,缩小了影响力节点的搜索空间,改善了网络规模大算法搜索空间大的缺点,加快了算法的收敛。(3)我们针对前面两方面的工作分别在三个不同规模的真实网络上进行实验。针对第一个工作,我们研究了节点相似性对不同网络的影响和基于节点相似性方法对影响最大化问题的有效性。针对第二个工作,我们首先对社区结构和局部搜索策略的有效性进行实验,然后对提出的算法的效果和效率进行实验。