复杂网络重要节点识别及传播源定位方法的研究

摘要

现实世界中的大多数传播现象都可以抽象为复杂网络上的动力学传播过程，对该领域的研究将有助于更好地理解传播现象，进而对网络上的传播过程进行控制。中国《国家网络空间安全战略》已经将网络上的传播控制列为战略任务之一，亟需有效的解决方案。　　重要节点识别和传播源定位是控制网络传播过程的重要途径。重要节点识别方法的主要研究方向包括节点重要性排序和影响力最大化。目前，提高识别结果的准确性和计算效率是重要节点识别方法亟待解决的问题。传播源定位方法主要分为单源定位方法和多源定位方法。提高定位精确性、计算效率以及处理稀松观测现象的能力是传播源定位方法目前亟待解决的问题。本文的研究工作围绕复杂网络重要节点识别及传播源定位方法展开，对当前的研究现状进行了全面的综述，并重点针对重要节点识别方法中的节点重要性排序和传播源定位方法中的单源定位进行了深入研究。　　在节点重要性排序方面，本文首次提出“扩展局部K-Shell和”(Extended Local K-Shell Sum,ELKSS)中心性。首先，在对网络进行K-Shell分解的基础上，对某个节点两跳以内邻居的K-Shell(KS)值相加，定义了局部K-Shell和；其次，对该节点的邻节点的局部K-Shell和进行扩展，从而得到ELKSS，其时间复杂度为O（m+n〈k〉2）。将ELKSS与另外6种经典的节点排序方法在8个规模不等的现实网络上，通过分辨率、准确性和相关性三种不同的评估指标进行了对比。同时，还定义了一种新的分辨率评估指标，能够反映出节点排序方法对节点影响力的区分能力和排序结果的内部均匀程度。实验结果表明，ELKSS在三种性能评估指标上均优于另外6种经典方法。　　在传播源定位方面，本文以Susceptible-Infected(SI)模型作为传播机制，首次从网络快照观测合理性的角度出发，利用不同状态节点形成的层次关系和观测特点研究单源定位方法。目前，还没有出现从网络快照观测合理性的角度研究传播源定位的工作。首先，在固定根节点的树图上，利用不同状态节点形成的层次关系和观测特点，定义了一种合理性观测值，用于量化树图的观测合理性；其次，对于一般树图，以图中每个感染节点作为根节点，构建生成树并计算其合理性观测值，从中选出合理性观测值最大的生成树后，将其根节点作为传播源；最后，对于任意网络图，假设网络上的传播是沿着广度优先的方式进行漫延，并以网络中每个感染节点作为根节点生成广度优先生成树，计算所有生成树的合理性观测值，从中选出最大值对应的生成树，将其根节点作为传播源。进而，提出传播中心性(Propagation Centrality,PC)算法用于定位传播源，其时间复杂度为O(n3)。证明了PC算法在无限线图上能够实现精确的传播源定位。在一系列人工合成网和现实网上，将PC算法与另外5种经典传播源定位方法进行了对比。实验结果表明，PC算法的定位精确性优于另外5种经典方法。更重要的是，PC算法对网络快照中普遍存在的稀松观测现象不敏感，这使得PC算法的实际应用性更强。

目录

声明

第一章 绪论

1.1 研究背景与研究意义

1.2 研究现状

1.3 论文的主要研究内容及创新

1.4 论文的组织结构

第二章 相关理论基础

2.1 复杂网络基本拓扑性质

2.2 复杂网络的基本模型

2.3 经典传播模型

2.4 本章小结

第三章 节点重要性排序：“扩展局部K-Shell和”中心性

3.1 引言

3.2 相关工作

3.3 “扩展局部K-Shell和”中心性

3.4 节点重要性排序方法的性能评估指标

3.5 实验及结果分析

3.6 本章小结

第四章 传播源定位：传播中心性算法

4.1 引言

4.2 相关工作

4.3 网络快照(Snapshot)

4.4 传播中心性算法

4.5 实验结果及分析

4.6 本章小结

第五章 总结与展望

5.1 论文工作总结

5.2 未来工作展望

参考文献

在学期间的研究成果

致谢