时间传播网络中扩散范围预测方法的研究

摘要

信息的传播问题以及由此引发的顶点被影响问题，是多年来一直被广泛研究的问题。信息扩散范围预测即预测发现信息传播后的受影响顶点，是信息传播研究中的一个基本问题。信息通过接触进行传播，而接触随时间改变并存在延迟，因此本文将接触构成的传播网络定义为时间传播网络并研究信息扩散范围预测问题。信息传播具有不确定性，难以直接预测受影响顶点以及顶点受影响时间，因此需要跟踪验证顶点的状态。然而顶点状态验证需耗费大量计算资源，且验证次数往往是有限的，所以扩散范围预测的目标是：在k次验证中尽量多地发现受影响顶点。
　　虽然信息传播已被研究多年，但扩散范围预测的研究较少且现有方法并不能有效解决该问题，因此本文提出了受影响概率启发式算法进行预测。本文工作如下：
　　（1）结合信息传播预测研究和时间图研究，形式化定义了时间传播网络中扩散范围预测问题，并介绍已有方法的优缺点。
　　（2）基于IC模型计算时间传播网络中顶点受影响概率，并将其作为扩散范围预测依据。本文证明了在时间传播网络中计算顶点受影响概率是NP-hard问题，并提出了传播路径长度受限近似方法近似计算顶点受影响概率。
　　（3）针对信息传播的不确定性，本文提出了受影响概率启发式算法预测验证信息扩散范围。该算法将选择受影响概率最大的候选顶点将进行验证，并更新顶点状态验证后的候选集合。此外，针对该方法的不足本文在受影响概率启发式算法的基础上提出了改进算法进行预测。实验证明本文方法确实能够更好的解决扩散范围预测问题。
　　综上所述，本文在时间传播网络中研究了扩散范围预测问题并提出了有更高预测准确率的预测算法。本文研究成果对相关的研究工作具有一定的参考价值。

目录

声明

第一章 绪论

1.1 课题研究背景

1.2 课题研究内容

1.3 课题研究意义

1.4 文章组织结构

第二章 相关概念与研究现状

2.1 相关概念定义

2.2 时间图的研究现状

2.3 信息传播的研究现状

2.4 扩散范围预测的研究现状

2.5 本章小结

第三章 时间传播网络中顶点受影响概率计算

3.1 问题定义

3.2 顶点受影响概率

3.3 PLLA近似算法

3.4 本章小结

第四章 基于受影响概率的启发式算法

4.1 问题定义

4.2 IPH算法

4.3 AIPH算法

4.4 本章小结

第五章 实验评估

5.1 数据集

5.2 实验设置

5.3 实验结果

5.4 本章小结

第六章 总结与展望

6.1 全文总结

6.2 工作展望

参考文献

攻读硕士学位期间发表的论文

致谢