社会网络影响力模型及其算法研究

论文摘要

营销领域的“口碑效应”现象和“病毒式营销”推广方式提出了如何在人群中寻找影响力最大的用户的问题。该问题与社会网络影响力模型及其算法领域的研究内容有着很高的契合度。影响力最大化问题被引入社会网络研究领域后,成为近年来学术界的一大研究热点。研究者根据现实网络中影响力传播规律,结合理论分析,建立了各种传播模型,并将影响力最大化问题转化为传播模型上的算法的问题。本文首先重点研究了独立级联模型和线性阈值模型这两种基本的影响力传播模型,定义了传播模型上影响力的传播机制。同时,本文还阐述了影响力最大化问题的相关性质、研究思路和典型算法。通过总结和对比典型算法的特点,在分析其优点和不足的基础上,提出了将有向图的强连通分量分解思想应用于影响力最大化问题的新算法,并将该新算法与两种典型算法进行了性能对比和分析。分析结果显示,新算法的时间复杂度要低于两种典型算法。本文的研究以本实验室与中国移动通信研究院合作项目“用户行为分析系统”为实验平台,建立传播模型和传播机制,实现新算法以及典型算法,并使用摘取自斯坦福大学以及密歇根大学网站的多个真实社会网络数据集进行了一系列实验。实验结果表明,在影响力最大化问题的规模较大的情况下,与典型算法相比,本文提出的新算法能够用更少的时间、更高的效率解决问题。这一结论与理论分析结果相符。

论文目录

• 致谢
• 摘要
• ABSTRACT
• 1 引言
• 1.1 课题意义
• 1.2 研究背景
• 1.3 国内外研究现状
• 1.4 研究内容和结构安排
• 2 相关理论知识
• 2.1 社会网络
• 2.2 影响力传播模型
• 2.2.1 独立级联模型
• 2.2.2 线性阈值模型
• 2.2.3 其它传播模型
• 2.3 影响力最大化问题
• 2.3.1 子模函数
• 2.3.2 问题难度
• 2.3.3 典型的TIAN算法
• 3 SCC-TIAN算法
• 3.1 SCC分解算法
• 3.2 SCC-TIAN算法
• 3.2.1 算法思想
• 3.2.2 算法步骤
• 3.2.3 性能分析
• 4 实验平台及算法实现
• 4.1 平台架构
• 4.2 影响力计算模块
• 4.2.1 设计目标
• 4.2.2 架构设计
• 4.3 可视化模块
• 4.4 算法实现
• 5 实验结果与分析
• 5.1 实验数据
• 5.2 实验方法
• 5.3 实验结果
• 5.3.1 算法横向对比
• 5.3.2 算法纵向对比
• 5.3.3 结果分析
• 6 结论
• 6.1 论文工作总结
• 6.2 下一步工作
• 参考文献
• 学位论文数据集