经典论文难度：入门

复杂网络对随机故障与蓄意攻击的耐受性

Error and attack tolerance of complex networks

Albert R, Jeong H, Barabási A-L · Nature 2000 · DOI: 10.1038/35019019

鲁棒性随机故障蓄意攻击无标度网络网络碎裂渗流

一句话

比较随机图与无标度网络在随机删点和按度删点下的直径与碎裂过程，发现无标度网络“耐随机故障、怕蓄意攻击”。

相关专题：网络可控性与稳定性、小世界与无标度网络模型

VIDEO讲解视频

复杂网络对随机故障与蓄意攻击的耐受性4 分 32 秒

文字稿

大家好，这一期我们精读 Albert 等人2000年发表在Nature上的论文。它的结论可以概括成一句话，无标度网络耐随机故障，却怕蓄意攻击。

互联网的路由器经常出故障，却很少出现全局断网；细胞面对药物或环境干扰也能存活。传统解释是冗余布线，作者问，冗余足以解释这种鲁棒性吗？鲁棒性和网络的度分布又有什么关系？如果有人有针对性地破坏网络，结果又会怎样？

作者比较两类网络，一类是以 ER 随机图为代表的指数型网络，另一类是 BA 无标度网络。两类网络节点数和边数相同，主要模拟是一万个节点、两万条边，平均度为4。随机故障是随机选点删除，蓄意攻击则先删度最大的节点，再按度从大到小依次删除。观测量有三个，网络直径、最大连通分支所占比例，以及孤立小分支的平均大小。这里的直径指所有节点对最短路径的平均长度。小分支平均大小的峰值可以识别临界点，因为临界点附近主分支正好碎成许多小块。

画面左边是一个无标度网络，我们按度从大到小移除节点。右边蓝线是随机故障，红线是蓄意攻击，纵轴是最大连通分支所占比例。随机故障删掉的几乎都是度很小的节点，主分支只是一点一点地漏气，原文没有观察到明显阈值。蓄意攻击先删掉的是枢纽，主分支很快瓦解，原文中这个临界比例约为0.18。作为对照，随机图在约0.28处发生类似渗流相变的碎裂，比无标度网络受攻击时更晚。

随机图的直径随删除比例单调增大，随机故障和蓄意攻击的表现差不多，因为所有节点都差不多重要。无标度网络在随机故障下直径几乎不变，即使百分之五的节点失效，其余节点照常通信。但在蓄意攻击下，删除百分之五的节点就能让直径翻倍。

作者在自治系统层面的互联网拓扑上做了同样分析，它有6209个节点、12200条边。随机删除多达百分之二点五的节点，直径不受影响。同样比例的攻击却使直径增大到原来的三倍以上，攻击下的临界比例约为0.03。在32万多个节点的万维网样本上，随机故障下主分支长期完整，攻击下在约0.067处突然瓦解。作者总结，容错性的代价是易受攻击。

本文结论主要来自模拟，同年 Cohen 和 Callaway 等人用渗流理论给出了解析结果。对指数在2到3之间的无限大无标度网络，随机删除的临界比例趋近于1。这就把模拟中看到的耐随机故障，变成了一个理论结论。

按度攻击需要知道每个节点的度，后续研究还比较了按介数攻击和只用局部信息的策略。本文只看拓扑，真实系统中节点失效后负载会重新分配，可能引发级联失效。2005年 Doyle 等人指出，互联网的高度路由器多处于网络边缘，而不是模型设想的核心。这提醒我们，度分布相同的网络，其他结构可能完全不同。

作者指出，这一点对通信网络是坏消息，对药物设计却可能是机会，可以寻找击垮病原体网络的靶点。2001年 Jeong 等人在酵母蛋白质相互作用网络中，检验了删除枢纽更致命的推论。但人体自身的网络也是重尾的，攻击枢纽对药物毒副作用意味着什么，值得认真思考。

总结一下，无标度网络对随机故障很耐受，对蓄意攻击却很脆弱。原因是网络的连通性主要靠少数枢纽维持。互联网和万维网的数据也呈现出同样的模式。但负载、相互依赖和网络的其他结构，都可能改变这个结论。建议先看原文图1的小网络，再细读图2和图3这两张核心图。

一句话看懂

无标度网络的连通性主要靠少数枢纽维持：随机删除节点几乎只删到度很小的节点，网络照常工作；一旦按度从大到小删除，很少的比例就足以使网络直径急剧增大并碎裂成小块。随机图则两种情况下表现差不多。

研究背景与问题

许多复杂系统在部件频繁失效时仍能正常运转：互联网的路由器经常出故障，却很少出现全局断网；细胞面对药物或环境干扰也能存活。传统解释是“冗余布线”。作者的问题是：冗余是否足以解释鲁棒性？鲁棒性与网络的度分布有什么关系？如果有人有针对性地破坏网络，结果又会怎样？

核心思想与方法

作者比较两类网络：

指数型网络：以 ER 随机图为代表，度分布为泊松分布，所有节点的度都接近平均度；
无标度网络：用 BA 模型生成， $P(k)\sim k^{-3}$ 。

两类网络的节点数和边数相同（主要模拟为 $N=10\,000$ 、20 000 条边， $\langle k\rangle=4$ ），然后以两种方式删除比例为 $f$ 的节点：

随机故障（error / failure）：随机选择节点删除。

蓄意攻击（attack）：先删度最大的节点，再按度从大到小依次删除。

观测量：网络直径 $d$ （文中定义为所有节点对最短路径的平均长度）；最大连通分支占全体的比例 $S$ ；孤立小分支的平均大小 $\langle s\rangle$ 。

$\langle s\rangle$ 的峰值是识别临界点的好办法：在临界点附近主分支破碎成许多小块，小分支平均大小达到最大，此后继续删点又把这些小块拆成单个节点。作者还在两个真实系统上做了同样的分析：自治系统层面的互联网拓扑（6209 个节点、12 200 条边）和一个 325 729 个节点的万维网样本。

主要发现

随机故障下，随机图的直径随 $f$ 单调增大；无标度网络的直径几乎不变，即使 5% 的节点失效，其余节点之间的通信也不受影响。
蓄意攻击下，随机图的表现与随机故障差不多（因为所有节点都差不多重要）；无标度网络的直径迅速增大，删除 5% 的节点即可使直径翻倍。
碎裂过程：随机图在 $f_c\approx0.28$ 处发生类似渗流相变的碎裂。无标度网络在随机故障下没有观察到明显阈值，主分支一个节点一个节点地“漏气”；在攻击下则在 $f_c\approx0.18$ 处碎裂，比随机图更早。
互联网：随机删除多达 2.5% 的节点直径不受影响；同样比例的攻击使直径增大到原来的三倍以上，攻击下的临界点约为 $f_c\approx0.03$ 。
万维网样本：随机故障下主分支长期保持完整，攻击下在 $f_c\approx0.067$ 处突然瓦解。
作者总结：容错性的代价是易受攻击；这一点对通信网络是坏消息，对药物设计（寻找能“击垮”病原体网络的靶点）则可能是机会。

怎样读这篇论文

先看图 1：两个各有 130 个节点、215 条边的小网络，红色标出度最大的 5 个节点，绿色标出其邻居——直观感受“枢纽覆盖了大部分网络”。然后看图 2（直径随 $f$ 的变化，四条曲线分别是两类网络各两种删除方式）和图 3（ $S$ 与 $\langle s\rangle$ 随 $f$ 的变化），这两张图承载了全文的结论。互联网与万维网部分可以对照图 2b–c、图 3c–d 快速读过。

局限与后续工作

理论化：本文结论主要来自数值模拟。同年 Cohen 等和 Callaway 等用渗流理论给出了解析结果：对于 $2<\gamma<3$ 的无限大无标度网络，随机删除的临界比例趋近于 1，判据可以写成 Molloy–Reed 形式 $\langle k^2\rangle/\langle k\rangle>2$ （推导见网络可控性与稳定性专题的数学推导与算法）。
攻击策略依赖全局信息：按度攻击需要知道每个节点的度；后续研究比较了按介数、按重新计算的度等策略，也研究了只知道局部信息时的攻击和免疫。
“度”不等于“重要性”：本文只看拓扑。真实系统中，节点失效后负载会重新分配，可能引发级联失效；节点之间也可能存在相互依赖（多层网络中的相互依赖渗流）。
对互联网模型的质疑：Doyle 等（2005，PNAS）指出，互联网的高度路由器多处于网络边缘，与 BA 模型所设想的“高度核心”不同，因此“攻击几个枢纽就能瘫痪互联网”的结论需要谨慎看待。这提醒我们：度分布相同的网络，其他结构可能完全不同。
生物学延伸：Jeong 等（2001）随后在酵母蛋白质相互作用网络中检验了“删除枢纽更致命”的推论。

关联知识

结构鲁棒性以本文为出发点介绍随机失效与蓄意攻击，数学推导与算法给出了 Molloy–Reed 判据与 $f_c$ 的推导；网络可控性与稳定性中的交互演示可以重现图 3 中巨分支随删除比例变化的两条曲线。
Barabási–Albert 优先连接模型中的枢纽概念在本文中第一次被赋予了功能意义。
致死性与中心性：枢纽蛋白假说及其争议中的讨论把本文的结论搬到了细胞网络上。

延伸思考

本文的“攻击”每次按初始度排序删除。如果每删除一个节点就重新计算度再选最大者，你预期 $f_c$ 会变大还是变小？为什么？
在药物设计中，“攻击病原体网络的枢纽”是有吸引力的思路。但人体自身的网络也是重尾的，这对药物的毒副作用意味着什么？
文中直径 $d$ 定义为平均最短路径长度。网络碎裂后，不连通节点对的距离应如何处理？这个技术细节会怎样影响图 2 的曲线？