Nat. Rev. Phys.速递：复杂网络的鲁棒性和韧性

关键词：复杂网络，网络鲁棒性，网络韧性，级联扩散，渗流相变

论文题目：Robustness and resilience of complex networks论文期刊：Nature Reviews Physics论文地址：https://www.nature.com/articles/s42254-023-00676-y斑图地址：https://pattern.swarma.org/paper/0022c4f0-ae7a-11ee-bc79-0242ac17000e

复杂网络广泛存在于我们的世界中，从细胞到人类大脑，从社会群体到互联网，都是由许多互相连接的部分组成的复杂系统。这些系统的宏观特性无法从微观成分中简单推导出来。正是这种网络的互连性，使得它们在面对内部故障和外部干扰时可能会出现严重的退化甚至出现系统性崩溃。例如，电力系统中最初局部过载导致的级联故障，以及推动生态系统走向灭绝的临界慢化现象。
这篇综述介绍复杂网络鲁棒性和韧性的理论和计算方法，讨论了最新用于减轻扰动影响的方法，包括设计鲁棒性、识别预警信号和调整响应。在应用方面，作者还比较了最前沿的网络拆解方法的性能，从而得出这些算法在实际问题中的最佳适用范围，并提供了一个代码库，作为一个评估网络韧性的工具集。

1. 复杂网络的特点与网络鲁棒性的数学框架

复杂网络的特点在于其单位之间的相互作用，这些相互作用形成了各种各样的结构模式，如异质性、模块化和层次结构。网络的这种互联性质意味着即使是微小的干扰也可能被放大，影响整个系统。因此，理解它们对外部干扰和内部故障的鲁棒性至关重要。
在探索网络鲁棒性的过程中，研究者们采用了多种理论和计算方法。其中一种静态方法是渗流理论，它通过移除网络中的节点或链接来模拟网络的退化过程，从而理解网络在受到干扰时的行为（见图1）。渗流是一种直接且直观的框架，用于研究如何通过预定规则移除节点或链接来拆除网络，并计算残余网络的不同统计和几何属性。这种方法使我们能够跟踪系统组件因某些原因（如故障、维护、攻击等）失效时的结构响应。
此外，在动态信息流方面，如故障传播，关注的是故障如何在网络中扩散，以及这种扩散如何影响网络的整体结构和功能（见图3）。最优渗流旨在找到能够阻止信息传播的最小“超级阻断者”集合。另一个问题是找到能够最大化信息传播的超级传播者。这两个问题通常不是等价的，然而在具有特定阈值模型下，最优渗流等同于影响力最大化问题。这种方法使得最优渗流可以应用于诸多社会问题，如识别社交媒体中的影响力传播者、大流行病中的超级传播者、基因网络中可能导致疾病的关键基因突变、脑中的关键整合区域、生态系统崩溃临界点的关键物种，以及金融机构的“太大而不能倒闭”问题。

2. 网络瓦解的技术与方法

为了更有效地瓦解或保护网络，研究者们开发了一系列针对目标攻击的算法，这些算法的目的是找到网络中哪些节点的移除会最大程度地破坏网络的连通性，从而揭示网络的脆弱点。论文总结了部分主要算法，包括集体影响力（CI），基于信息传播的置信传播消减（BPD, Belief propagation-guided decimation）算法、最小和（Min-Sum）算法，基于谱划分的广义网络拆除（GND）、集合GND（EGND）算法，基于度的CoreHD算法，基于渗流的爆炸性免疫（EI）和基于有监督学习的图形拆除（GDM）（见图2）和基于强化学习的FINDER等。其中，基于机器学习的算法使用几何深度学习，特别是图神经网络来学习在小型合成网络上的攻击策略从而瓦解大型真实网络，它们显示了不同方法在特定应用中的效果和适用范围。
表1 针对目标攻击的主要算法的总结
表2 不同算法拆解真实世界的网络的效果对比基于机器学习的算法相关学习资源推荐：GDM：如何以最小代价破坏系统结构？一套基于机器学习的方法FINDER：论文一作解读，利用强化学习寻找复杂系统的关键节点人工智能前沿：组合优化问题的机器学习求解

3. 应对网络崩溃发方法

在实际应用中，如何设计鲁棒的网络、识别网络崩溃的早期预警信号以及制定适应性响应策略变得至关重要。这包括了如何通过网络设计来防范潜在的故障，以及一旦故障发生后如何有效地应对来减轻其影响（见图4）。设计鲁棒性的目标是通过理论和计算方法增加网络对故障和攻击的抵抗力。这包括优化网络结构，使其能够更好地承受故障和干扰。例如，通过增加关键节点的冗余连接或调整网络的连接模式来提高网络的整体稳定性。识别早期预警信号涉及到监测和分析网络的动态行为，以便于早期发现可能导致网络崩溃的迹象。通过对网络的实时监控和数据分析，可以在问题变得不可控之前识别出潜在的风险点。这需要对网络的各个方面进行详细的观察，包括节点活动、连接模式变化以及流量异常等。适应性响应则是当网络面临崩溃或已经出现故障时，采取适应性措施以最小化损害并恢复网络功能是关键。这可能包括动态调整网络配置，隔离受损区域，或部署备用系统以维持关键服务。此外，基于机器学习和人工智能的方法可以用于快速识别问题并自动应对，从而提高韧性和效率。
总之，复杂网络的研究不仅对理解自然界和人类社会中的众多系统至关重要，而且对于预防和应对可能的系统性风险提供了宝贵的见解。未来的研究将继续探索这些网络的深层结构和动态特性，为我们提供更强大的工具来理解和管理这些复杂的系统。

图1：渗流作为评估网络鲁棒性的静态方法，展示了具有同质性和异质性连接模式的网络如何对故障和针对性攻击做出反应。圆圈代表孤立的分量，其半径取决于节点数。

图2：最先进的网络拆解方法比较，展示了不同算法如何驱使一个系统（巴西腐败网络，共309个节点）向着解体方向发展，这是通过最大连通分量的相对大小来衡量的。不同曲线显示了各种算法的解体路径。节点颜色代表攻击顺序（灰色节点未被移除），节点大小代表其介数值。攻击后剩余节点的轮廓颜色代表它们所属的群集。

图3：美国—南加拿大电网的状态的故障演化，展示了在美国—南加拿大电网中，级联扩散模拟后电力线的状态。绿色代表未经历停电的线路，灰色代表受影响的电力线。

图4：展示了复杂网络在面临崩溃时的预防和应对策略。这包括了早期警告信号的识别、动态网络标记（DNM）的应用来监测临界相变，以及网络行为的模拟分析。论文通过这些示例，展示了在不同类型的网络（如电力网、生物分子网络、金融市场）中，如何有效地监测和应对网络状态的变化。此外，它还探讨了最优修复策略，以及在网络出现问题时如何进行有效的重组和恢复。这些内容反映了论文在理解和管理复杂网络鲁棒性与韧性方面的综合方法。

编译｜刘志航、余孟君

网络科学集智课堂第三期：

从数学建模到多学科应用

详情请点击：从数学建模到多学科应用——网络科学·集智课堂全新升级

‍推荐阅读1. Nature 历年网络科学文集：社区与韧性2. Physics Reports重磅综述：网络韧性及核心研究主题3. 网络隔离器：改善网络结构以提升韧性4. 张江：第三代人工智能技术基础——从可微分编程到因果推理 | 集智学园全新课程5. 加入集智学园VIP，一次性获取集智平台所有内容资源6. 加入集智，一起复杂！

点击“阅读原文”，报名课程