论文部分内容阅读
近年来,随着互联网的发展,一些社会网络,例如,国外的Twitter、Facebook、 Flickr以及国内的新浪微博、知乎等,用户量大且活跃度高,信息在网络中传播范围快而广,使得影响力最大化问题成为社会网络中研究的重点。影响力最大化问题的目标在于使得信息在网络传播中影响到最多的人。要研究如何使得信息在网络中影响最多的人,首先要了解信息是如何在网络中传播的。人们为了研究信息在社会网络中的传播方式和特点,提出了多种纯理论的传播模型,其中包括应用最广的独立级联模型。然而,我们并不知道这些理论模型是否真的能对现实中社会网络中信息传播进行正确建模。本文通过对真实社交网络中信息传播的数据分析,证明了独立级联模型并不能准确的对社交网络中信息传播建模。此外,本文提出了一种能更好的模拟现实网络中信息传播的模型—三度级联模型作为理论传播模型来研究影响力最大化问题。首先,我们通过实验证明了所提出的三度级联模型比独立级联模型能更好的模拟社会网络中信息的传播;其次,我们证明了基于三度级联模型的影响力最大化问题是NP-hard问题;最后,我们提出了一个高效率的方法解决基于三度级联模型下的影响力最大化问题。本文的主要工作和贡献是:第一:总结分析当前影响力最大化的研究背景和研究现状,讨论当前影响力最大化存在的问题。第二:总结分析影响力最大化相关的模型和基于相应模型下的算法,重点介绍了基于独立级联模型的影响力最大化问题,并对流行的算法的优缺点进行分析。第三:通过分析真实网络中信息传播,提出三度级联模型,为了解决基于此模型下的影响力最大化问题,我们提出TLLFGreedy算法,并在实际网络上通过实验检验算法的准确性和时间复杂度。通过实验表明:1.三度级联模型对于真实网络中信息传播的建模优于独立级联模型。2.TLLFGreedy算法能高效的解决基于三度级联模型下的影响力最大化问题。