基于三度理论的社会网络顶点影响力最大化算法研究

摘要

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

目录

声明

摘要

第一章 绪论

1．1 研究背景

1．2 影响力最大化问题的研究现状

1．3 本文的主要工作内容

第二章 影响力最大化相关概念及技术

2．1 影响力最大化的概念

2．2 传播模型

2．2．1 传染病模型

2．2．2 线性阈值模型

2．2．3 独立级联模型

2．3 经典算法

2．3．1 贪婪算法

2．3．2 SingleDiscount算法

2．3．3 PMIA算法

2．4 优化算法

2．5 本章小结

第三章 基于TSCM的影响力最大化

3．1 三步级联模型

3．2 TSCM的性质

3．3 基于TSCM的影响力最大化

3．3．1 定义与性质

3．3．2 三层近似算法

3．3．3 更高效的算法

3．3．4 时间复杂度

3．4 本章小结

第四章 实验结果与分析

4．1 数据集

4．2 实验结果

4．2．1 ICM和TSCM与真实网络中的信息传播的对比

4．2．2 σTL(S)近似σTSCM(S)的效果

4．2．3 影响力最大化结果和效率

4．3 本章小结

第五章 结论与展望

参考文献

致谢

攻读学位期间发表的学术论文目录

攻读学位期间参加的科研项目情况