考虑代价的无标度网络抗攻击性研究

论文摘要

具有无标度特性的复杂网络即为无标度网络,此种网络的度分布满足幂律分布,即概率上具有自相似性。所谓自相似性,是指函数形态在不同放大倍数上的性状相似;所谓标度不变性,指网络的度分布在任何标度上都是相似的,不能找到一个特征的标度来刻画网络的性质。Barabasi在《Nature》上提出著名的无标度网络在选择性攻击下脆弱的观点,是当前复杂网络抗攻击性研究的主流观点。该观点以为无标度网络在选择性攻击下,少数重要节点或边被移除将使得整个网络快速崩溃。然而,我们发现现实网络与该结论存在不一致之处。Internet是一个现实世界中的无标度网络,该网络的设计目的为抵御核打击等选择性攻击,并在病毒、黑客等的选择性攻击下,从未出现网络整体崩溃的现象,这说明,现实中的Internet在选择性攻击下并不脆弱,这与上述结论不一致。本文为此进行了深入研究,证明在考虑代价的情况下,无标度网络可能并不脆弱,在特定情况下,可能是最鲁棒的网络。主要工作如下:1)对现实的网络进行了分析,得出现实与主流观点不一致的原因在于后者假设了对所有节点的攻击代价相等,而现实中对网络中各个节点的攻击代价不可能相等;2)修正主流观点的假设,本文定义攻击代价为攻击时所删除的节点的度数,定义网络的紧致系数为节点的度与其他所有节点重要性度量的相关程度。3)通过对五个网络的仿真实验证明两个结论:在攻击代价不同的情形下,无标度网络在选择性节点攻击下可能是鲁棒的;进一步,越紧致且平均度越大的无标度网络在选择性节点攻击下越鲁棒,而在同一平均度条件下,结构越紧致的网络越鲁棒。该结论丰富了无标度网络的抗攻击性理论,为复杂网络的结构稳定性研究,进而为复杂系统的稳定性研究提供了重要的依据,也可用于建立鲁棒的社会、生物和技术网络,获得药物靶点、瓦解犯罪集团等。本文的主要创新点为:1)对Barabasi在《Nature》上提出的无标度网络在选择性攻击下脆弱的著名观点进行了挑战,指出主流观点中所有节点的攻击代价相同的前提是错误的,而在攻击代价不同的前提条件下,无标度网络在选择性节点攻击下不脆弱。2)指出在攻击代价不同的前提条件下,影响无标度网络鲁棒性的两个因素为网络的紧致系数和网络的平均度。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景及意义
• 1.2 国内外研究现状
• 1.3 存在的问题
• 1.4 主要研究内容
• 1.5 论文结构安排
• 第2章 复杂网络的理论基础
• 2.1 复杂网络的定义
• 2.2 复杂网络的刻画
• 2.2.1 节点的度与度分布
• 2.2.2 平均最短路径长度
• 2.2.3 最大连通子图
• 2.2.4 聚集系数
• 2.3 复杂网络模型
• 2.3.1 规则网络和随机网络模型
• 2.3.2 小世界网络模型
• 2.3.3 无标度网络模型
• 2.4 本章小结
• 第3章 无标度网络的抗攻击性研究
• 3.1 当前的主流观点及分析
• 3.1.1 主流观点的历史
• 3.1.2 分析
• 3.2 相关定义
• 3.2.1 攻击的定义
• 3.2.2 攻击代价的定义
• 3.2.3 攻击策略的定义
• 3.2.4 攻击效果的定义
• 3.3 代价条件下无标度网络的抗攻击性
• 3.3.1 理论性讨论
• 3.3.2 仿真实验
• 3.4 代价条件下影响无标度网络抗攻击性的两个因素
• 3.4.1 紧致性对无标度网络抗攻击性的影响
• 3.4.2 平均度对无标度网络抗攻击性的影响
• 3.5 本章小结
• 第4章 总结与展望
• 4.1 总结
• 4.2 展望
• 参考文献
• 致谢
• 附录