基于双曲映射的复杂网络生存性指标研究

摘要

在网络时代，网络安全形势日益严峻，但传统网络安全技术面对复杂多变的网络环境愈加乏力，网络生存技术研究刻不容缓。基于网络拓扑的复杂网络理论为网络生存技术研究提供了有力手段，而复杂网络的双曲几何研究更为发掘网络拓扑的结构特征提供了全新的视角。进一步，以复杂网络双曲几何为手段研究了不同节点和链路对网络生存能力的影响程度。首先提出三种精度和效率各有取舍的网络双曲映射模型，用于将实际网络映射至双曲空间，进而分别提出基于双曲空间的指标，度量节点和边对网络生存性的重要程度。
　　现有映射方法都是基于极大似然估计的逐点映射，无法有效利用所有节点信息，导致映射精度和效率不足。为此，提出基于社团信息的双曲映射模型社团双曲映射法（CHM）。首先，本文提出一个指标（CI）度量社团间关系，并给出基于CI的社团排序算法。CHM基于社团-扇形假设，即一个社团内大部分节点在二维双曲空间（即庞加莱圆盘）中聚集于同一扇区内，把社团有序映入双曲空间，并初始化各扇区内节点的角度坐标，这使得节点初始化角度与其真实角度十分接近。因此，CHM利用所有节点信息，通过极大似然估计（MLE）优化各节点角度，提高了算法精度。然后，本文改进MLE，提出基于局部路径信息的局部社团双曲映射法（LCHM），算法时间复杂度因而下降到O(n2)。为进一步提升映射速度，本文利用社团的层次结构，对网络社团逐层初始化来缩小节点的角度估计范围，并提出了相应的双曲映射模型层次社团双曲映射法（HCHM）。HCHM完全舍弃极大似然估计，而仅通过操作不同层次的网络社团来提升映射精度，使算法时间复杂度在稀疏网络中接近线性。实验证明了CHM和LCHM具有比现有方法更好的性能。而HCHM虽然精度略低，但其映射速度远高于已有方法，实用潜力巨大。
　　继而利用双曲空间中的网络信息，分别研究了节点和边对网络生存性的重要程度问题。传统的节点重要性度量指标大多从某一角度出发，存在片面性。因此，利用节点坐标分析了节点间的相互关系，并综合考虑节点在网络中的位置和节点的连接程度，提出了双曲中心性指标来度量节点的重要性。进一步，针对边重要性研究较少，且指标较为片面的问题，基于链路预测理论的异常链路研究，并结合节点关系分析，提出了双曲异常性指标来度量边的重要性。分别实验表明了双曲中心性和双曲异常性对节点和边重要性的度量能力。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1 研究背景和研究意义

1.2 国内外研究现状

1.3 本文主要内容及框架

2 复杂网络相关概念与理论

2.1 复杂网络生存性相关指标

2.2 双曲映射相关概念

2.3 链路预测相关概念

3 基于社团和局部信息的复杂网络双曲映射

3.1 社团-扇区假设

3.2 双曲映射模型

3.3 实验验证

3.4 双曲映射模型的缺失边预测能力

3.5 结果分析

3.6 本章小结

4 双曲空间下网络生存性指标研究

4.1 节点重要性度量指标研究

4.2 边重要性度量指标研究

4.3 本章小结

5 总结与展望

5.1 总结

5.2 展望

致谢

参考文献

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