论文部分内容阅读
近年来,随着计算机网络的快速发展,社交网站如微博、人人等新兴的网络应用开始逐渐流行,基于此类社会网络的信息传播也成指数级增长。因此,基于社会网络的课题研究越来越流行,比如:社会网络中的信息如何传播,网络中的社团如何划分,社会网络中影响力问题的研究,如何进行有用信息的推荐等等。本文的主要研究工作是由Kempe等定义的社会网络中的影响力最大化问题。影响力最大化问题(influence maximization problem)即寻找网络中最具有影响力的节点集合,根据某种给定的信息传播模型,使得信息可以由该初始节点集合尽可能多的扩散到整个网络中。影响力最大化问题从理论上被证明是NP-Hard问题,Kempe等提出了贪心算法的解决方案。本文从启发式算法的角度出发,提出了基于禁忌搜索和模拟退火的算法框架,并且对提出的算法在大规模现实数据上进行了相关实验,以证明算法的可行性。此外,已有的算法中都没有考虑到初始节点集大小的问题,即都是在算法运行之前就直接指定了初始节点集的大小。在本文中,我们提出了通过分析节点的影响力及影响力的增加值去决定初始节点集合的大小,同时提出了初始节点集的稳定性指标。本文的主要贡献总结如下:1.综述了社会网络中的影响力最大化问题解决方案。总结了社会网络信息传播和影响最大化问题的相关研究背景;介绍了社会网络中信息传播的几种基本模型;综述了已有的影响力最大化问题的算法,并且详细介绍了各类算法的优缺点及适用模型等。2.提出基于禁忌搜索的模拟退火算法。模拟退火算法可以优化NP-hard问题的解决方案,而基于禁忌搜索的模拟退火策略,可以在选择节点时避免重复计算初始节点集合的影响力,同时可以有效的降低陷入局部最优解的概率。基于禁忌搜索和模拟退火算法,提出了解决影响力最大化问题的算法框架。3.提出参数分析指标。对影响力最大化问题中的相关参数进行分析。通过定义节点的影响力值及节点的影响力增加值来给出算法的终止条件。同时,对于选定初始节点集合的稳定性进行研究。给出了稳定性的定义并对现实网络进行实验计算其稳定性值。