复杂网络关键节点识别

　　网络的“小世界特性”和“无标度特性”的发现，掀起了网络科学持续10多年至今丝毫没有降温的研究热潮。网络科学研究的热点逐渐从早期发现跨越不同网络的宏观上的普适规律转变为着眼于从中观层面（社团结构、群组结构）和微观层面（节点、链路）去解释不同网络所具有的不同特征。其中，节点重要性排序问题作为复杂网络分析领域的一个关键问题，在许多重要场景中有着广泛的应用，如帮助人们防范和控制疾病暴发、制订营销策略、保持通信网络的连通性、促进或抑制信息传播、推广新的产品或行为、避免电力网等基础设施级联失效等意义重大。
　　尽管目前已经有很多种方法可以对节点重要性进行区分，且已取得一定的效果，但在大数据时代，实际网络节点数目庞大，网络结构功能十分复杂，已有算法或多或少仍存在一些问题，如算法复杂度过高在大规模复杂网络中并不适用、对部分节点的重要性识别精度不足等。基于以上原因，设计实用且有效的排序方法用于挖掘网络关键节点仍是充满挑战性的课题。
　　《复杂网络关键节点识别》系统地研究了复杂网络节点重要性排序的相关问题。

第1章 绪论
1．1 研究背景及意义
1．2 复杂网络研究进展与网络重要节点挖掘简介
1．3 节点重要性研究现状
1．3．1 节点重要性排序方法
1．3．2 多信源传播最大化
1．4 本书主要研究思路与内容

第2章 相关理论和技术基础
2．1 网络相关概念和基本静态几何特征
2．1．1 网络图表示
2．1．2 复杂网络拓扑特性
2．1．3 人工网络模型
2．2 网络传播动力学
2．2．1 传染病传播动力学模型
2．2．2 传播爆发阈值的确定
2．3 节点重要性评价标准
2．3．1 传染病传播动力学模型
2．3．2 基于网络的鲁棒性和脆弱性评价排序算法
2．4 节点重要性排序指标
2．4．1 基于节点近邻的排序方法
2．4．2 基于网络全局信息的排序方法
2．4．3 基于节点位置信息的排序方法
2．4．4 基于随机游走的排序方法
2．5 影响最大化问题
2．5．1 影响最大化问题定义
2．5．2 影响最大化算法的度量标准
2．5．3 求解影响力最大化问题的常用算法
2．6 本章小结

第3章 基于领域相似度的复杂网络节点重要度评估算法
3．1 引言
3．2 节点领域相似度定义
3．3 基于领域相似度的节点重要性排序算法
3．4 实验设置
3．4．1 实验环境与网络数据集
3．4．2 评价标准
3．5 实验结果分析
3．5．1 静态攻击效果
3．5．2 动态攻击效果
3．6 本章小结
……

第4章 基于核数与结构洞特征的节点影响力排序算法
第5章 基于信息传播概率的复杂网络影响力评估算法
第6章 基于簇的影响最大化算法
第7章 基于复杂网络关键节点发现的无人机飞行冲突解脱方法

参考文献

　　网络的“小世界特性”和“无标度特性”的发现，掀起了网络科学持续10多年至今丝毫没有降温的研究热潮。网络科学研究的热点逐渐从早期发现跨越不同网络的宏观上的普适规律转变为着眼于从中观层面（社团结构、群组结构）和微观层面（节点、链路）去解释不同网络所具有的不同特征。其中，节点重要性排序问题作为复杂网络分析领域的一个关键问题，在许多重要场景中有着广泛的应用，如帮助人们防范和控制疾病暴发、制订营销策略、保持通信网络的连通性、促进或抑制信息传播、推广新的产品或行为、避免电力网等基础设施级联失效等意义重大。
　　尽管目前已经有很多种方法可以对节点重要性进行区分，且已取得一定的效果，但在大数据时代，实际网络节点数目庞大，网络结构功能十分复杂，已有算法或多或少仍存在一些问题，如算法复杂度过高在大规模复杂网络中并不适用、对部分节点的重要性识别精度不足等。基于以上原因，设计实用且有效的排序方法用于挖掘网络关键节点仍是充满挑战性的课题。本书系统地研究了复杂网络节点重要性排序的相关问题，从以下几个方面开展研究。
　　（1）从网络鲁棒性与脆弱性分析节点对网络的影响。针对大规模实际复杂网络的结构，随着时间的不断变化，获取网络全局信息具有局限性的这一客观现实，通过量化节点局部网络拓扑的重合程度来定义节点间的相似性，提出了一种考虑节点度以及邻居节点拓扑重合度的节点重要性评估算法，从节点移除对于网络瓦解的影响方面，对复杂网络中的节点进行重要性排序，研究重要节点遭受静态攻击与动态攻击下的网络瓦解情况，根据模拟结果制订网络节点保护策略，对重要节点进行重点保护，使其免受蓄意攻击威胁，降低网络因重要节点遭受攻击而级联失效的可能性。基于邻域相似度的节点重要性排序算法，由于只用到节点的局部网络拓扑信息，因而适用于大型复杂网络。
　　（2）从网络信息传播动力学的角度，定义节点的传播影响力为：信息从节点发起，经过传播最终可以影响到网络节点个数。在考虑节点邻居卜壳值的同时，还充分考虑了邻居节点间的连接关系对于节点影响力的影响，设计了基于网络约束系数与k-壳值的节点影响力排序算法及其扩展算法，调整了局部高聚簇节点的重要性排名，提高了算法排序的精确度。
　　（3）当前多数节点影响力排序方法忽略了信息传播的重要因素，即传播率，导致算法排序精度在不同传播率下差异较大、不够稳定这一缺陷，本书提出了一种综合考虑节点与三步内邻居间的有效可达路径以及信息传播率的ASP算法，有效解决了不同评估指标对传播率敏感的问题。在同样只考虑三步内邻居的条件下，ASP指标相比原算法SP，几乎不增加算法复杂度且精度更高。算法设计思想对于理解节点局部聚簇性对于节点传播影响力的影响具有一定意义。
　　（4）研究了多节点共同作用下的传播影响最大化问题。不同于上述单个节点的重要性排序问题，影响力最大化问题需要考虑到多个节点作为信息传播源，发起传播时的影响力重叠问题。注意到k-壳分解方法逐渐剥离网络外围节点的过程会使网络聚集系数不断增大，而在这些网络剩余的高k-壳值节点集组成的簇中，信息可以有效传播，本书第6章设计了一种基于簇的影响最大化算法LCE，该算法以网络中相互链接的高卜壳值节点集为子团核心，将与子团连接紧密的邻居节点加入其中，扩张之后得到内部链接紧密的簇。通过选择这些簇中影响力大的节点组成初始活跃种子节点，保证了种子节点是相对重要且分散的。