社会网络中影响力最大化问题的研究

论文摘要

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

论文目录

• 摘要
• Abstract
• 第一章 引言
• 1.1 社会网络中的信息传播
• 1.2 本文的主要工作
• 1.3 本文的组织结构
• 第二章 社会网络中的信息传播及影响力最大化问题算法总结
• 2.1 社会网络的基本概念和特征
• 2.2 社会网络中信息传播模型
• 2.3 社会网络中影响力最大化问题的定义
• 2.4 影响力最大化问题定义及符号表示
• 2.4.1 符号表示
• 2.4.2 影响力最大化问题定义
• 2.5 现有算法的分类总结
• 2.5.1 启发式算法
• 2.5.2 贪心算法及其改进
• 2.5.3 其他算法
• 第三章 基于禁忌搜索和模拟退火的解决方案
• 3.1 基于模拟退火的解决方案
• 3.2 基于禁忌搜索和模拟退火的解决方案
• 3.3 实验
• 第四章 参数分析指标
• 4.1 节点集规模
• 4.2 节点集稳定性
• 4.3 实验和分析
• 4.3.1 实验设置
• 4.3.2 实验分析
• 第五章 总结与展望
• 5.1 总结
• 5.2 展望
• 致谢
• 参考文献
• 附录 攻读硕士学位期间发表论文及参与项目情况