许多复杂的系统都表现出惊人的错误容忍度。例如，相对简单的生物体尽管有激烈的药物或环境干预，仍能生长、持续存在和繁殖，这种容错性归因于基础代谢网络的稳健性 [1]。复杂的通信网络 [2] 显示出惊人的鲁棒性：虽然关键组件经常发生故障，但局部故障很少导致网络全局信息承载能力的丧失。这些和其他复杂系统的稳定性通常归因于系统组件定义的功能网络的冗余布线。在本文中，我们证明了容错性并非由所有冗余系统共享，而是仅由一类非均匀有线网络（称为无标度网络）显示。我们发现描述许多系统的无标度网络，如万维网 (www) [3-5]、互联网 [6]、社交网络 [7] 或细胞 [8]，显示出意想不到的程度鲁棒性，他们的节点的通信能力不受甚至不切实际的高故障率的影响。然而，容错的代价很高：这些网络极易受到攻击，即选择和删除在确保网络连接性方面发挥最重要作用的少数节点。这种容错性和攻击脆弱性是通信网络（例如 Internet 或 www）的一般属性，对确保信息准备就绪具有复杂的影响。
在数据采集计算机化的帮助下，大型网络上拓扑数据的可用性不断提高，这使我们对网络结构和发展的一般方面的理解有了重大进展 [9-16]。现有的经验和理论结果表明，复杂网络可以根据其连通性分布 P (k) 分为两大类，给出网络中一个节点与 k 个其他节点连接的概率。第一类网络的特点是 P (k) 在平均 hki 处达到峰值，并在 k 较大时呈指数衰减。这种指数网络研究最多的例子是 Erd˝ os 和 R´ enyi [9,10] 的随机图模型以及 Watts 和 Strogatz [11] 的小世界模型，两者都导致相当均匀的网络，其中每个节点具有大致相同的链接数，k ≃ hki。相比之下，万维网 (www) [3-5]、互联网 [6] 和其他大型网络 [17-19] 上的结果表明，许多系统属于一类非均匀网络，称为无标度网络网络，其中 P (k) 作为幂律衰减，即 P (k) ∼ k−γ，没有特征尺度。虽然节点具有大量连接 (k >> hki) 的概率在指数网络中实际上是被禁止的，但高度连接的节点在无标度网络中具有统计显着性（见图 1）。
我们首先研究两个基本网络模型的稳健性，即生成具有指数尾的网络的 Erd˝osRényi (ER) 模型 [9,10]，以及具有幂律尾的无标度模型 [17] .在 ER 模型中，我们首先定义 N 个节点，然后以概率 p 连接每对节点。该算法生成一个均匀网络（图 1），其连通性遵循泊松分布，在 hki 处达到峰值，并在 k >> hki 时呈指数衰减。
许多真实网络的不均匀连通性分布由无标度模型 [17,18] 再现，该模型包含真实网络共有的两个要素：增长和优先依恋。该模型从 m0 个节点开始。在每个时间步 t 引入一个新节点，该节点连接到已存在节点中的 m 个。新节点连接到节点 i 的概率 Πi 取决于该节点 2 的连通性 ki，因此 Πi = ki/ P j kj。对于大 t，连通性分布是遵循 P (k) = 2m2/k3 的幂律。
网络的互连性由其直径 d 描述，定义为网络中任意两个节点之间的最短路径的平均长度。直径表征了两个节点相互通信的能力：d 越小，它们之间的预期路径越短。具有大量节点的网络可以具有相当小的直径；例如，拥有超过 8 亿个节点 [20] 的 www 的直径约为 19 [3]，而据信拥有超过 60 亿个人的社交网络的直径约为 6 [21]。为了正确比较这两个网络模型，我们生成了具有相同数量节点和链接的网络，使得 P (k) 服从指数分布的泊松分布和无标度网络的幂律分布。
容错——为了解决网络的容错问题，我们研究了当一小部分节点 f 被移除时直径的变化。一个节点的故障（缺失）通常会增加其余节点之间的距离，因为它可以消除一些有助于系统互连的路径。 实际上，对于指数网络，直径随 f 单调增加（图 2a），因此，尽管有冗余布线（图 1），但其余节点之间的通信越来越困难。这种行为植根于网络的同质性：由于所有节点都具有大致相同数量的链接，因此它们对网络直径的贡献相同，因此删除每个节点都会造成相同程度的损坏。 相比之下，我们观察到无标度网络的一种截然不同且令人惊讶的行为（图 2a）：在不断增加的误差水平下，直径保持不变。因此，即使高达 5% 的节点出现故障，网络中其余节点之间的通信也不会受到影响。无标度网络的这种鲁棒性植根于它们极不均匀的连通性分布：由于幂律分布意味着大多数节点只有少数链接，因此将以更高的概率选择连通性较小的节点，并且移除这些“小”节点不会改变其余节点的路径结构，因此对整个网络拓扑结构没有影响。
攻击生存能力——一个试图故意破坏网络的知情代理，例如设计一种药物来杀死细菌，不会随机消除节点，而是会瞄准连接最紧密的节点。为了模拟攻击，我们首先删除连接最多的节点，然后继续按照连接 k 的递减顺序选择和删除节点。测量受到攻击的指数网络的直径，我们发现，由于网络的同质性，无论节点是随机选择还是按连通性降序选择，都没有实质性差异（图 2a）。另一方面，对于无标度网络，观察到截然不同的行为：当连接最多的节点被消除时，无标度网络的直径迅速增加，如果 5% 的节点被删除，其直径将翻倍。这种易受攻击的根源在于连接分布的不均匀性：连接由几个高度连接的节点确保（图 1b），这些节点的移除会极大地改变网络的拓扑结构，并降低其余节点与每个节点通信的能力其他。
网络碎片化–当节点从网络中被移除时，节点的集群，其与系统的链接消失，会从主集群中被切断。为了更好地了解故障和攻击对网络结构的影响，我们接下来研究这个碎片化过程。我们测量最大集群的大小，S，显示为总系统大小的一部分，当一部分节点被随机或在攻击模式下被移除时。我们发现，对于指数网络，当我们增加f时，S显示出类似阈值的行为，例如，对于f>fc≃0.28，我们有S≃0。当我们监测孤立集群（即除最大集群外的所有集群）的平均尺寸hsi时，也观察到类似的行为，发现hsi迅速增加，直到fc时hsi≃2，之后它减少到hsi=1。这些结果表明了以下的崩溃情况（图4）。对于小的f，只有单个节点破裂，hsi ≃ 1，但随着f的增加，从主簇上脱落的碎片的大小增加，在fc处显示出一种单一的行为。在fc处，系统实际上已经分崩离析，主集群被分成小块，导致S≃0，碎片的大小hsi达到峰值。随着我们继续删除节点（f>fc），我们将这些孤立的集群分割开来，导致hsi不断减少。由于ER模型等同于无限维的渗滤[22]，观察到的阈值行为在质量上类似于渗滤的临界点。
然而，无标度网络对攻击和故障的响应却大不相同（图 3b）。对于随机故障，没有观察到碎片的阈值，而是最大集群的大小缓慢减小。大多数 f 的 hsi ≃ 1 这一事实表明网络因节点一个接一个地断开而缩小，错误级别的增加导致仅单个节点的隔离，而不是节点集群。因此，与 fc 处指数网络的灾难性碎片形成对比的是，无标度网络在 f 值非常高时作为一个大集群保持在一起，为这些网络在随机故障下的拓扑稳定性提供了额外的证据。这种行为与极度延迟的临界点（图 3）的存在是一致的，网络仅在主集群完全收缩后才分崩离析。另一方面，无标度网络对攻击的响应与指数网络对攻击和故障的响应相似（但更快）（图 3b）：在临界阈值 f sfc ≃ 0.18 时，小于对于指数网络观察到的值 f ec ≃ 0.28，系统分裂，形成许多孤立的簇（图 4）。
虽然正在努力为通信系统设计容错和低产量组件，但人们对错误和攻击对网络大规模连接的影响知之甚少。为了展示我们基于模型的研究对这些系统的影响，接下来我们研究了两个具有日益增长的经济和战略重要性的网络的错误和攻击容忍度：Internet 和 www。
最近Faloutsos等人[6]调查了互联网在路由器和域间层面的拓扑特性，发现连接性分布遵循幂律，P（k）∼k-2.48。因此，我们期望它应该显示出我们的研究所预测的容错性和攻击的脆弱性。为了检验这一点，我们使用了互联网拓扑结构的最新调查，给出了域间（自治系统）层面的网络。事实上，我们发现，互联网的直径不受高达2.5%的节点随机移除的影响（比互联网路由器的故障率（0.33%）大一个数量级[23]），而如果相同比例的连接最多的节点被消除（攻击），d会增加两倍以上（图2b）。同样，对于高比率的随机节点移除，大的连接集群持续存在，但如果在攻击模式下移除节点，断裂的碎片的大小迅速增加，临界点出现在f Ic ≃ 0.03（图3b）。
www形成了一个巨大的有向图，其节点是文件，边是指从一个文件指向另一个文件的URL超链接，其拓扑结构决定了搜索引擎定位其信息的能力。www也是一个无标度网络：一个文档有k个传出和传入链接的概率Pout(k)和Pin(k)遵循几个数量级的幂律，即P(k)∼k-γ，γin＝2.1，γout＝2.45[3,4,24]。由于没有完整的www拓扑图，我们的研究仅限于包含325，729个节点和1，469，680个链接（hki=4.59）的网络子集[3]。尽管链接具有定向性，但系统的反应与我们先前调查的无定向网络相似：在最初的轻微增加后，d在随机故障的情况下保持不变，而在攻击时则增加（见图2c）。在高故障率的情况下，网络作为一个大集群存活下来，但hsi的行为表明，在攻击下，系统在f wc=0.067时突然瓦解（图3c）。
综上所述，我们发现无标度网络对随机故障显示出惊人的高容忍度，这是指数型网络所不具备的特性。这种稳健性可能是许多复杂系统的容错性的基础，从细胞[8]到分布式通信系统。这也解释了为什么尽管路由器问题频发[23]，我们很少经历全球网络中断，或者尽管许多网页暂时无法使用，我们在网上冲浪和查找信息的能力却没有受到影响。然而，容错性是以牺牲攻击生存能力为代价的：这些网络的直径迅速增加，当连接最多的节点成为攻击目标时，它们会断成许多孤立的碎片。这种攻击生存能力的下降对于药物设计是有用的[8]，但对于通信系统，如互联网或www，就不那么令人鼓舞了。虽然一般的智慧是，对具有分布式资源管理的网络的攻击不太成功，但我们的结果表明，目前通信网络的拓扑结构的弱点，根植于其不均匀的连接分布，对其攻击生存能力有严重影响，这可能被那些试图破坏这些系统的人所利用。
转载：https://blog.csdn.net/miracleoa/article/details/128052793