基于链路预测的复杂网络瓦解建模与分析.pdf

1、随着科学技术的高速发展，21世纪的人类社会常被冠以“网络时代”的头衔。可以说，我们的生活离不开网络。但是，人类在享受信息化生活带来的便利的同时也面临着一系列严峻的问题。近十年来，从SARS、埃博拉到熊猫烧香、灰鸽子，计算机及生物病毒的爆发和传播越发频繁且难以控制；9.11事件后，各种恐怖组织网络的破坏活动更加猖獗。对于病毒传播网络、恐怖组织网络这类有害的网络，我们希望通过免疫、扰动、瓦解等手段摧毁其网络结构，使其网络功能不能正常发挥。因

2、此，网络科学问题中复杂网络瓦解策略研究的越来越具有重大理论意义和应用价值。从最初基于零信息、完全信息的研究，到近来基于不确定或不完全信息条件下瓦解策略的研究，关于复杂网络瓦解策略的研究更加贴近现实世界实际情况，成为极其重要而且富有挑战性的前沿课题。
　　本文针对目前不完全信息条件下复杂网络瓦解策略研究中存在的不足，以复杂网络和链路预测相关理论知识为指导，在复杂网络瓦解建模中引入链路预测用以恢复部分缺失信息，围绕瓦解信息的刻画、瓦解

3、模式的定义以及瓦解效果的评估三个问题，综合运用统计物理中传统图论知识，以及矩阵论、线性代数、军事运筹学、博弈论、概率论与数理统计、控制仿真等多学科领域知识，深入系统的研究了复杂网络瓦解问题的建模、分析以及链路预测的作用。论文主要研究工作及创新点如下：
　　（1）将链路预测引入复杂网络瓦解建模问题。从复杂网络的角度研究和分析链路预测，在不完全信息条件下，将具有数据挖掘、恢测以及网络演化重构作用的链路预测技术引入到网络瓦解建模中。基于

4、已知信息，通过链路预测算法刻画网络结构相似性，有效地还原了部分缺失的网络结构信息。分析了在网络瓦解层面多种链路预测的作用。研究发现，相对于随机加边，链路预测算法预测精度和效率的提高在10倍以上。然后，链路预测的作用远大于其此，从网络瓦解的角度出发，其衡量标准并不关心是否准确的恢复出缺失连边，而是是否找到重要节点，链路预测对某些边的“张冠李戴”，是将网络理想化的趋势，导致的自身精度下降，却并不影响我们找到网络结构层面上的重要节点和网络瓦解

5、效果的提升。
　　（2）建立了基于链路预测的复杂网络瓦解模型。通过瓦解信息、瓦解模式、瓦解效果以及链路预测的定量描述，构建了基于链路预测的网络瓦解模型，并在无标度网络和ER随机模型网络上进行了仿真分析。研究发现，在无标度网络中，相对于现有的在不完全信息条件下，基于已知信息进行网络瓦解和随机攻击，模型中的瓦解方法显著提高了的复杂网络瓦解效果；而由于ER网络节点间连边是一个概率事件，本身具有随机性，其相似性难以刻画，我们很难通过链路预

6、测找到重要节点实施重点打击，故对瓦解效果提高不明显；进一步，我们分析了10种预测算法在模型中的表现，发现这些算法普遍表现较好；最后，我们针对不同的信息缺失比例，仿真分析了其了最优的链路预测强度，为攻击者提供了建议和指导。
　　（3）揭示了链路预测的漫画效应。研究发现，在信息丢失比例不大的情况下，通过链路预测，虽然不能完整地恢复网络结构的所有信息，却可以使网络的结构特征更加突出，使得网络瓦解效果优于完全信息下的瓦解效果。这是因为，在

7、网络瓦解层面，其关注的不是每一个节点每一条边的真实性，而是在网络瓦解层面从结构上如何捕捉那些对网络结构功能影响很大的重要节点，即网络的特征。我们可以认为，链路预测作为一种工具，在恢复和重构网络时，通过计算网络结构相似性，能够在加边时夸张和加强这种效果。链路预测如同具有锐化功能的画图工具一样，同一张人物肖像照，通过链路预测展现出来就像一幅漫画，虽没有原来的照片真实清晰，却更好的反映了所刻画人物的外貌特征，使人过目不忘，印象更深。我们称链路