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

来源 :南京大学 | 被引量 : 0次 | 上传用户:lxp3754
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
近年来,随着计算机网络的快速发展,社交网站如微博、人人等新兴的网络应用开始逐渐流行,基于此类社会网络的信息传播也成指数级增长。因此,基于社会网络的课题研究越来越流行,比如:社会网络中的信息如何传播,网络中的社团如何划分,社会网络中影响力问题的研究,如何进行有用信息的推荐等等。本文的主要研究工作是由Kempe等定义的社会网络中的影响力最大化问题。影响力最大化问题(influence maximization problem)即寻找网络中最具有影响力的节点集合,根据某种给定的信息传播模型,使得信息可以由该初始节点集合尽可能多的扩散到整个网络中。影响力最大化问题从理论上被证明是NP-Hard问题,Kempe等提出了贪心算法的解决方案。本文从启发式算法的角度出发,提出了基于禁忌搜索和模拟退火的算法框架,并且对提出的算法在大规模现实数据上进行了相关实验,以证明算法的可行性。此外,已有的算法中都没有考虑到初始节点集大小的问题,即都是在算法运行之前就直接指定了初始节点集的大小。在本文中,我们提出了通过分析节点的影响力及影响力的增加值去决定初始节点集合的大小,同时提出了初始节点集的稳定性指标。本文的主要贡献总结如下:1.综述了社会网络中的影响力最大化问题解决方案。总结了社会网络信息传播和影响最大化问题的相关研究背景;介绍了社会网络中信息传播的几种基本模型;综述了已有的影响力最大化问题的算法,并且详细介绍了各类算法的优缺点及适用模型等。2.提出基于禁忌搜索的模拟退火算法。模拟退火算法可以优化NP-hard问题的解决方案,而基于禁忌搜索的模拟退火策略,可以在选择节点时避免重复计算初始节点集合的影响力,同时可以有效的降低陷入局部最优解的概率。基于禁忌搜索和模拟退火算法,提出了解决影响力最大化问题的算法框架。3.提出参数分析指标。对影响力最大化问题中的相关参数进行分析。通过定义节点的影响力值及节点的影响力增加值来给出算法的终止条件。同时,对于选定初始节点集合的稳定性进行研究。给出了稳定性的定义并对现实网络进行实验计算其稳定性值。
其他文献
随着计算机、网络和多媒体技术的不断发展与普及,数字视频数据成倍增长。网络上的视频常常会在没有任何监督的情况下被任意编辑、复制和转载,成为很多不同的拷贝版本,这给版
随着网络技术的发展,带宽的提高,互联网应用发生了巨大的变化。存储在互联网上的数据越来越丰富,用户访问量也越来越大。这使得传统单一服务器提供存储的模式不再适应当前的
口令是一种常用的认证机制,为了提高安全性,人们基于口令设计了大量的认证机制,但现有的基于口令的认证机制大都存在猜测攻击的隐患。本文旨在Diffie-Hellman 密钥交换协议的基
本文对门限群签名做了研究,首先介绍了文章中用到的基本概念和工具, 然后总结了门限群签名应该具有的八条性质,以这些性质为标准仔细分析了现 有的 DF、L