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