基于PageRank和传播概率的重要节点识别方法研究

摘要

复杂网络分析理论的进步提供了崭新的视角和丰富的工具。大量现实系统都可以表示为网络结构，通过抽象为统一的模型后定量研究并解决现实问题，内容跨越了社科人文、应用数学、物理科学、金融领域等多学科领域。重要节点识别作为复杂网络研究的重要分支，具备深刻的理论意义也拥有广泛的应用前景，吸引了越来越多科研者的关注。重要节点识别是发现部分对网络的拓扑结构和功能有重要作用的少量特殊性的节点，对网络的抗毁性、演化、控制、同步等有重要影响。　　根据目前主流的传染病传播模型及相应评价方法，为提高节点重要性识别中的准确性和分辨率，通过分析不同传播率下不同中心性方法的优劣性，以及中心性排序后的顶级节点的传播重叠等问题，本文的研究内容如下：　　第一，介绍复杂网络的基本概念，对目前节点排序方法与节点影响力评估方法进行系统深入的归纳与总结；第二，通过实验发现不同传播率下多种排序算法的优劣，以及不同倾向性下PageRank算法的变化，提出结合传播概率修改概率转移矩阵的PageRank改进算法DHP。通过在SIR传播模型上进行实验评估，该算法在多个网络数据实验中能够取得好的精确度及分辨率，且对传播率变化具有更好的适应性。第三，提出一种新的重要节点识别方法，该方法基于社团检测使用DHP算法在社团内选取种子节点，通过影响力传播模型，与直接用DHP算法在全网上选取种子相比能够避免影响力的重叠，取得更好的传播范围。第四，总结了目前重要节点识别问题存在的挑战与待解决难题。

目录

声明

第一章 绪论

1.1 研究背景和意义

1.2 重要节点排序的研究现状

1.2.1基于节点邻近的中心性算法

1.2.2基于传播路径的中心性算法

1.2.3基于特征值迭代的中心性算法

1.2.4结合多种节点排序算法

1.2.5 基于节点操作的节点排序算法

1.2.6基于其他概念的排序算法

1.3 影响力最大化研究现状

1.3.1基于贪婪策略的影响力最大化

1.3.2基于拓扑特征的影响力最大化

1.4 论文的主要工作内容

1.5 论文的组织安排

第二章 复杂网络分析的理论基础

2.1 网络分析研究动机

2.2网络基础理论概念

2.2.1 术语规约及网络概念

2.2.2 连通性、网络直径、平均路径和效率

2.2.3 聚集系数

2.2.4 度分布与度异质性

2.2.5 社团结构与模块度

2.3 网络模型的拓扑结构性质

2.3.1 规则网络

2.3.2 随机生成网络

2.3.3 小世界网络

2.3.4 无标度网络

2.4 本章小结

第三章 基于传播概率的PageRank 改进算法DHP

3.1 重要性识别算法及改进动机

3.1.1 原始PageRank算法

3.1.2 H-index算法

3.2传播病模型模拟节点影响力大小

3.2.1 SIS疫情传播模型

3.2.2 SIR疫情传播模型

3.3 实验验证方法与数据集

3.3.1 肯德尔系数

3.3.2 网络数据集

3.3.3在不同传播率p下节点的传播能力变化

3.3.4在不同传播率下，H-index与Degree 衡量能力的差别

3.4 基于传播概率混合度和H-index的DHP算法

3.5 算法性能评估

3.5.1 对算法中α参数的设置

3.5.2 小型网络上DHP算法的举例

3.5.3 中心性对比方法

3.5.4 精确度结果及分析

3.5.5 分辨率结果及分析

3.6 本章小结

第四章 基于社团检测改进DHP的重要节点识别方法

4.1 在社团发现算法下的影响力评估方法

4.2 实验与方法

4.2.1 随机游走社团算法划分节点

4.2.2 传播模型介绍

4.3 实验结果分析

4.3.1 网络数据集

4.3.2 独立级联模型实验结果与分析

4.3.3 线性阈值模型结果及分析

4.4 本章小结

第五章 总结与展望

5.1 本文总结

5.2 展望

参考文献

致谢