多层网络级联失效的预防和恢复策略概述*

蒋文君 刘润然† 范天龙2) 刘霜霜 吕琳媛2)‡

1)(杭州师范大学,阿里巴巴复杂科学研究中心,杭州 311121)

2)(电子科技大学,基础与前沿研究院,成都 611731)

现实生活中,与国计民生密切相关的基础设施网络大多不是独立存在的,而是彼此之间相互联系或依赖的,于是用于研究这些系统的多层网络模型随之产生.多层网络中的节点在失效或者遭受攻击后会因“层内”和“层间”的相互作用而产生级联效应,从而使得失效能够在网络层内和层间反复传播并使得失效规模逐步放大.因此,多层网络比单个网络更加脆弱.多层网络级联失效产生的影响和损失往往是非常巨大的,所以对多层网络级联失效的预防和恢复的研究具有重大意义.就多层网络级联失效的预防而言,主要包含故障检测,保护重要节点,改变网络耦合机制和节点备份等策略.就多层网络发生级联失效后的恢复策略而言,主要包含共同边界节点恢复、空闲连边恢复、加边恢复、重要节点优先恢复、更改拓扑结构、局域攻击修复、自适应边修复等策略.

1 引 言

在复杂网络研究的早期,单个网络上的多个动力学特性均受到了广泛的关注,如疾病传播[1,2]、网络同步[3,4]、级联失效[5]和网络控制[6,7]等.而随着研究的深入,人们发现很多现实网络都不是孤立存在的,比如电力网络和通讯网络之间存在相互依赖关系.这些网络会因与其他网络之间的依赖关系,在面临蓄意攻击或随机故障时比孤立网络更加脆弱[8].现实中存在互相依赖和联系的复杂系统非常多,如黑客或者病毒的攻击会使得因特网出现故障甚至瘫痪,从而导致银行金融系统、电力网络、交通网络和物流信息网络等一系列关键基础设施的数据采集与监视控制系统(supervisory control and data acquisition,SCADA)无法正常工作,进而导致这些系统的瘫痪和崩溃.比如电力网络中的发电站需要铁路网络等为其运送燃料和物资的补给,而铁路网络也需要通过电力网络和通信网络提供支撑和控制.图1[9]总结了电力基础设施网络和其他基础设施之间的依赖关系.这些基础设施中的一个或某几个一旦出现故障或受到攻击,其影响都会快速地扩散到其他相关网络中,引发一系列迭代级联事故,从而将损害扩大到更广范围.发生在2003年意大利停电事故[10]和2005年8月印度尼西亚大停电事故均凸显了这种大规模的耦合网络故障对社会生产生活甚至国家安全带来的巨大风险.Tootaghaj等[11]搜集了全球近年来比较重大的停电事故,如表1所列.为了避免和减少级联失效对基础设施所带来的损害,2016年,我国通过了《网络安全法》,构建起以信息共享为基础,事前预防、事中控制、事后恢复与惩治的关键信息基础设施保护体系[12].美国在这方面也甚为关注,自克林顿政府以来就出台大量的相关法律文件: 第63号总统令和《国土安全法》等,扩展对关键基础设施的保护范围[13].

图1 电力基础设施依赖关系[9]Fig.1.Dependencies among power infrastructures[9].

表1 重大停电事故数据[11]Table 1.Data on major power outages[11].

如何才能避免相互依赖系统级联效应的发生呢? 在这些系统发生级联失效后,如何在系统完全崩溃之前修复并减小级联失效所带来的损失呢[14]?常用策略和方案通常分为两种类型: 1)通过故障检测和保护关键节点等预防措施来减少故障发生的可能性;2)当故障发生时采用合适的恢复策略,对故障进行恢复.

接下来,本文第2节介绍相依网络级联失效的经典模型.第3,4节则分别梳理了预防多层网络级联失效的方法和级联失效发生后的网络恢复策略,而第5节是讨论部分.

2 相依网络级联失效模型

虽然很多人都注意到了网络之间的耦合关系,也认为多个基础设施网络之间往往不是单一存在的,但是这一问题的研究一直未能形成一个清晰的框架.直到 2010年,Buldyrev等[10]在 Nature杂志上提出了由两个一对一相互依赖的网络构成的双层网络级联失效模型,并建立了相关的理论分析方法,发现相依网络在遭受攻击后的破碎形式为一阶不连续相变,这与单层网络的二阶连续相变有着本质的不同.这一结果意味着级联过程对原有的多层网络动力学具有深刻的影响.但Buldyrev等提出的模型较为严格,具有度分布 pA(k)的网络A和度分布 pB(k)的网络B需要有相同的节点数N,并且两个网络中的所有节点之间要建立一对一的完全依赖关系,也就是说,属于网络A中的节点ai唯一依赖网络B中的节点bj,而网络B中的bj也必定唯一依赖网络A中的ai,并且当网络A中的节点失效后,网络B中与之对应的节点也会立刻失效,反之亦然.其级联失效的过程如下: 从网络A中随机删除一定比例的节点后,网络A中新产生的孤立节点会失效,随后网络B中与网络A中的所有失效节点有依赖关系的节点也会失效,而网络B中失效的节点又会反馈到网络A中,如此反复迭代,直到不再有新的节点失效,网络达到稳态,级联失效过程结束.图2展示了两个网络的级联失效过程.

图2 级联失效迭代过程的建模[10](a)网络在初始状态下遭到攻击;(b),(c)和(d)网络在遭受攻击后网络级联失效的不同阶段,并最终达到了稳态,级联过程结束Fig.2.Modeling of cascading failure iterative processes[10]:(a)The network is attacked in the initial state;(b),(c),and(d)are the cascading failure processes of the network due to the dependencies between dependent networks after the attack,respectively.Eventually reached a steady state.

经典相依网络级联失效模型的提出引发了更多学者开展对多层网络的动力学研究.在两层网络的基础上,Gao等[15,16]进一步提出了多个网络存在相互依赖的“网络的网络(network of network,NON)”模型.随着对相依网络级联失效模型研究的推进,关于网络鲁棒性的研究[17]以及多层网络之间的动力学研究也吸引了愈来愈多的学者并取得丰硕成果.Baxter等[18]阐明了一阶相变的本质其实是混合相变,当临界节点形成的临界簇发散的时候,一旦其中的“基石”节点(keystone vertex)失效,整个临界簇就会发生雪崩现象,导致多层网络互连巨分量出现不连续的跳跃.多层网络的结构特性也对网络的鲁棒性有着重要的影响,如簇结构和度关联等.Faqeeh等[19]在具有模块的网络中发现了不止一个渗流簇(coexist percolation cluster,CPC),对理解网络的鲁棒性以及传染病模型中的疾病爆发具有重要意义.在网络的同配性研究方面[20,21],文献[20]比较了同配性对单层网络和多层网络上动力学过程的不同影响,发现在多层网络上,增加层间同配程度可以提高信息扩散效率;而增加层间异配程度则可以分散链路通信负载,增强网络鲁棒性.此外还有一些学者研究了空间地理效应[22,23]和有向网络[24-27]等因素对网络的鲁棒性所产生的影响.通过考虑多层网络层内节点的不同耦合方式,一些文献也研究了多层网络上的扩展渗流模型,例如k-core渗流[28]、 靴攀渗流(bootstrap percolation)[29,30]和弱渗流[31]等,极大地丰富了相依网络级联失效方面的研究.

3 预防策略

预防策略是指在多层网络发生故障前采取的预防应对措施,主要包括故障检测、预先保护重要节点、节点备份以及改变耦合机制等.通过采取恰当的预防策略可以减少网络关键节点发生失效的概率并有效防御恶意攻击,从而极大降低由于故障和攻击所带来的社会经济损失.例如,安装杀毒软件可以大概率防止电脑被计算机病毒感染和损坏.相比事后的修复和采取应对措施,恰当的预防策略相对成本低且效用大.

3.1 故障检测

故障检测是指定期查找设备或系统是否出现故障并对这些故障进行修复的过程.很多时候这些故障可能不会立即产生可以觉察的危害和损失,但如果不加以排除,则会在关键时刻或者随着时间积累对系统产生严重损害,所以应该定期加以排查.这里将各种基础设施抽象成了网络,但在现实生活中不同的系统根据其自身特点有不同侧重点和相应的检测方法,不能一概而论.比如,对于电力网络来说需要检测的可能会发生的故障包括发电机组故障、母线故障、输电线路故障和变电所故障等,而对于计算机网络来说其故障检测则包括硬件故障、软件故障、人为故障和病毒故障等.通过故障检测可以提前排查系统中存在的问题,减少其对系统造成的危害.故障检测是事前采取针对性措施,减少和防范故障发生的策略.

3.2 预先保护重要节点

重要节点一般是指少量对网络结构或功能非常重要,且其影响可以快速地波及到网络中大部分节点的节点[32],关于重要节点的衡量方法有很多[33,34].通过保护重要节点,可以大大提高复杂网络的鲁棒性[35-37].

文献[38]研究在相互依赖的网络上,分别以其中一个网络中的大度节点或者小度节点为攻击目标时网络鲁棒性的变化,他们发现即使是在较低的攻击概率下,在相互依赖的无标度(scale-free)网络[39]上采取保护大度节点的策略后,网络仍是十分脆弱的.Du等[40]发现具有较大数量的相连边(同一层网络节点之间的连边)和相依边(不同层网络具有相互依赖关系节点之间的连边)的节点很重要,所以不仅要保护层内或层间连接程度较高的节点,而且要保护层内和层间连边数量之和较大的节点,以此来增加系统的鲁棒性.

另一方面,应该优先对那些能够使得网络快速瓦解的节点进行保护.Osat等[41]将单层网络的最优渗流推广到多层网络上,并通过最优渗流找到那些被删除后网络不会再出现 N1/2规模的簇的最小节点集.最优渗流问题的解决方案在网络鲁棒性研究中具有直接的适用性,是瓦解网络最简易的方法.Baxter等[18]发现多层网络中存在能够导致网络临界簇雪崩的基石节点,并且发现在网络瓦解过程中巨分支崩溃的方式是不连续的混合相变,这与单个网络中平滑的连续相变存在明显差异.除此之外,文献[42]定义了一种节点的通用性(versatility)属性,来刻画那些在多种不同的动力学过程中都扮演重要角色的节点,并基于此提出了多种中心性指标来识别这类节点,如Eigenvector versatility和PageRank versatility等.如果我们优先对上述文献中的这些重要节点采取保护措施,就可以有效减缓或者抑制网络的破碎.此外,还有一些其他指标也可以作为选取重要节点进行保护的依据,如度中心性[43,44]、介数中心性[45]、k-壳分解[46]、半局部中心性[47]、PageRank[48]、LeaderRank[49]、圈比[34]等.

另有文献[17]将两层网络看成一个整体,将单层网络上一些衡量节点重要性的指标运用在了双层网络(或更多层的网络)上,从而找到在多层网络中需要保护的重要节点,提高了相依网络的鲁棒性,主要包括以下方法.

1)T-度中心性保护策略.将单层网络中的度中心性概念推广到两层网络上,得T-度(twolayer-degree)保护策略.在T-度中心性保护策略中,将不同层中的节点同等看待,计算每个节点在各自层内的度值大小,节点的重要性按它的T-度从大到小依次递减.例如,图3(a)给出了一个由网络A和网络B组成的相依网络.传统的方法是选择网络A中的节点1和节点2(度值分别为5和4),使它们和其依赖节点在故障发生时能够正常工作.而实验表明,在保护节点比例不变的情况下,保护网络A中的节点1和网络B中的节点1(度值分别为5和5)效果更好,这正是因为它们的T-度最大.

图3 基于相依网络的保护节点模型[17]Fig.3.Nodes protection model based on interdependent networks[17].

2)T-介数中心性保护策略.给定两层网络G=(C,(LA,LB,LAB)),其中LA表示包含 nA个节点的网络A中的边,LB表示包含 nB个节点的网络B的边,LAB则表示网络A和网络B之间的相依边.将整个相依网络看成一个由(nA+nB)个节点构成的网络,LA,LB和LAB全都同等视为网络C中的正常连边.如图3(b)中的深色节点,它具有三条连边.对整个网络C计算所有节点的介数中心性 C(i),即

其中 δjq为从节点j到q的所有最短路径的数目,δjq(i)表 示从节点j到节点q的 δjq条最短路径中经过节点i的数目.选择介数中心性最高的部分节点进行保护,称为T-介数(two-layer-betweenness)保护策略.这些既包含相连边又包含相依边的交叉路径在信息传递和故障传播中发挥着重要作用,但在传统的研究中却被忽视.

3)T-社团(two-layer-comm)保护策略[50].① 同上,将两个相依的网络A和网络B看作一个网络C,初始时假设每个节点本身就是一个社团,当出现最大的模块度增量[51]后,合并相应的社团i和j.当达到了局部最大模块度时,此步骤停止.② 将此时的每个社区继续当作一个“节点”,重复步骤直到模块度停止变化.节点i的模块度增益 Δ Q 为

3.3 优化层间耦合机制

不同的网络拓扑结构使多层网络的鲁棒性之间存在较大差异.Reis等[52]针对随机连接的相依模型网络鲁棒性低,而自然界中的真实相依网络鲁棒性却相对较高的问题进行研究,发现多层网络的鲁棒性由每一层的内部结构和层间的节点连接模式共同决定.他们指出一个网络的中心节点(hub nodes)与另一个网络中心节点之间存在度同配相关性的相依网络在随机故障中具有更好的鲁棒性.Parshani等[35]提出了部分依赖模型,通过降低相互依赖节点的数量,降低级联失效的危害.Liu等[31]提出的弱依赖模型则降低了相互依赖网络之间的依赖程度,这也使得网络的破碎形式从一阶相变变成二阶相变,增强了网络的鲁棒性.文献[53]则提出多层网络间非对称性的依赖,来控制网络层间的依赖程度,从而增加网络的鲁棒性.Hu等[54]分析了相依网络结构相似性对级联故障带来的影响,他们发现增加结构相似性会减弱级联故障的程度.文献[55]也指出网络间的相似性越高,则发生节点随机失效时系统的鲁棒性也越高.文献[56]提出网络同配性研究可以为提高网络鲁棒性带来新的启发,从而提高关键基础设施的保护水平.Radicchi等[57]将具有相互依赖关系的节点在一个失效后其余节点也会失效这一规则更改为: 当一个节点有至少两个副本节点(多层网络的不同层中具有相互依赖关系的节点)存活时,这个节点就不会失效.在多层(＞ 2)网络中建立冗余的相互依赖关系可以提高整个系统的鲁棒性.除此之外还可以通过减弱网络层间的相关性[58]、设置加强节点[59]等策略抑制系统的级联效应.

3.4 节点备份

节点备份也是一个有效预防级联效应的措施,它是指对多层网络中的少数重要节点预先从结构或功能方面设计并添加它们的备份,万一这些节点日后失效,这些备用节点能够立即启用代替失效的节点,维持网络功能正常运行[60].Valdez等[61]认为对一些节点备份后,即使在缺少其他网络支持的情况下,这些节点仍然能保留功能,从而增加了系统的鲁棒性.Quattrociocchi等[62]通过引入节点的自愈(self-healing)机制,即增加网络固有的冗余度来增强网络的鲁棒性.Schneider等[37]选择最少的自治节点[63,64](通过k-shell,介数中心性等方法进行筛选节点)进行备份,以避免网络在遭受攻击时发生突然瓦解和破碎.

然而节点备份的策略也有一些不足之处.文献[60]提出在自修复网络中通过相互复制进行自我修复是一把“双刃剑”.除此之外,在现实应用中,节点备份策略和网络冗余设计还需要增加网络的设计和维护成本(有些情况下节点的备份还面临技术难题),付出一定的时间和经济代价,造成一定的浪费,因此在实际应用中往往需要考虑这一策略的代价和效果的平衡.

4 恢复策略

恢复策略并不是重新设计或者构建一个网络,而是在正发生级联失效的网络上同步进行补救和修复,使其级联过程减缓甚至停止,并逐步恢复原有功能的办法[65].Schneider等[66]认为对于给定度分布的网络,在抵御恶意攻击中最有效的网络结构仍然是未知的;而对于给定连边数量的网络,鲁棒性最高的结构是所有节点度都相同的网络.他们在欧洲电力系统、互联网以及复杂网络模型上对此进行了仿真,结果表明,网络结构的很小变化(低成本)就可以显著提高不同网络的鲁棒性,并保持其功能不变.该研究结果不仅对提高现有基础设施的鲁棒性有重要意义,而且对设计经济可靠的网络系统也有一定的参考价值.Di Muro等[14]提出的通过寻找共同边界节点的恢复策略(详见4.1节)和La Rocca等[67]在2018年提出的空闲连边策略(详见4.2节),其相同点都是从网络的巨分量入手来对抗级联效应.此外还有一些策略关注到了相依网络中节点的两种不同属性的边(相依边和相连边[68,69]),他们认为对于来自相依网络的节点,它的重要性与其相依边和相连边的数量有关.文献[68]研究了如何在合理分配有限成本的情况下来添加连接边和依赖边.文献[69]则是通过衡量节点的相依边和相连边的数量,来确定优先恢复的节点.对于多层网络,Berezin等[70]发现局部攻击引起的危害比起同等情况下的随机攻击更加严重.文献[71]对于局部攻击产生的故障提出在故障节点存活邻居中选择两个低度值的节点进行加边的修复方法.

4.1 边界节点恢复策略

Muro等[14]提出相依网络恢复策略,旨在对未被级联失效波及的剩余网络进行保护.这一策略使得级联失效过程和恢复过程动态交替进行,其核心是找到两个相依网络中的共同边界节点.共同边界节点是指两个网络中距离各自巨分支距离为1的一对失效的相互依赖节点.图4中节点1和2即为共同边界节点.初始网络A发生了故障,网络B中所对应的节点也会失效,在网络B将故障传递回网络A之前,恢复机制会介入并找出当前的共同边界节点,每轮恢复阶段以概率γ对共同边界节点进行恢复,从而尽可能地遏制级联失效在相依网络上的传播.Muro等发现,最终网络有以下三种情况,第一是系统不被修复也不会崩溃;第二是部分节点在这一过程中失效,但恢复策略避免了系统的崩溃;第三是恢复过程也不能阻断级联失效过程,最终系统崩溃.

图4 故障恢复策略图解[14] 网络A和网络B的巨分支如图所示.情况1: 两个通过相依边连接的失效节点(节点1和节点2)分别距离其巨分支的距离l=1,然后以恢复概率γ进行修复;情况2: 如果两个相互依赖的故障节点(节点3和节点5)中至少有一个与其巨分支的距离大于1,则不符合恢复的条件,所以放弃恢复这一对节点Fig.4.Illustration of failure recovery strategy[14].The giant components of network A and network B are shown in the figure.Case 1: Two failed nodes(nodes 1 and 2)connected by dependent edges are respectively at a distance of l =1 from their maximal cluster,and then repaired with recovery probability γ.Case 2: If at least one of the two interdependent dent failed nodes(nodes 3 and 5)is more than 1 away from its maximal cluster,the recovery condition is not met,so the pair of nodes is abandoned to be restored.

选择共同边界节点进行恢复有以下两个原因:第一,当故障发生时,通常都是优先抢修正常区域周边的基础设施;第二,如果候选恢复目标不是共同边界节点,其对应的相依节点若是脱离巨分支的节点,这个节点就会因其依赖节点的失效而失效,那么对该节点的修复就没有意义.

吴佳键等[69]对此策略进行了一些修改,他们认为用恢复概率γ来随机选择恢复节点不是最优方案.于是提出利用共同边界节点在巨分支内外的连接边数计算和定义边界节点的重要性,也就是基于相连边的择优恢复算法(preferential recovery based on connectivity link,PRCL).实验显示,PRCL算法的恢复策略更好,可以识别出恢复过程中更重要的边界节点.

4.2 空闲连边恢复策略

在Buldyrev提出的相依网络级联失效模型的基础上,La Rocca等[67]2018年提出在两个相依网络中对相较而言恢复代价更低的那个网络进行恢复的策略.这里假设网络B为符合条件的网络,在步骤n=0时,从网络A中移走1-p比例的节点,得到网络A的巨分支.因为网络A与网络B的节点一对一依赖,所以可以得到网络B此时的巨分支.以概率γ同时恢复网络B中某个有限簇(其规模不小于2)中的两个节点与巨分支之间的连边.但如果该有限簇只有单个节点,那么就以相同方式恢复其与巨分支之间的一条连边.需要注意的是所有可能被恢复的有限簇中的节点必须有空闲连边.空闲连边是一种虚拟连边,指的是那些在级联失效过程中断开的连边.当一条连边断开以后,则它两端的节点各自得到一条空闲连边,如图5(a)中的虚线边所示.

图5 网络B中恢复策略的实现示意图[67](a)GC表示网络巨分支,虚线表示空闲连边,带有空闲连边的簇表示可修复的簇,没有空闲连边的簇表示无法进行恢复的簇;(b)网络B完成重连后的巨分支Fig.5.Schematic diagram of the implementation of recovery strategy in network B[67]:(a)GC represents the giant component of the network,the dashed lines indicate idle connected edges,clusters with free connected edges represent repairable clusters,and clusters without free connected edges represent clusters that cannot be recovered;(b)the giant component of network B after reconnection.

之所以选择一个有限簇里面的两个节点与巨分支相连接,是为了减少这个有限簇再次脱离巨分支的概率.增加有限簇与巨分支相连的节点数量虽然可以提高网络的鲁棒性,但是在现实应用中也会增加成本.阶段n=0结束后,以概率1-γ(γ是恢复概率)删掉网络B中没有被恢复的有限簇,如图5(a)中没有空闲连边的深色节点.至此第一轮网络B恢复过程结束.当网络B将这个结果反馈给网络A的时候,与网络B中失效节点相连接的网络A中的节点就会失效,然后又反馈到网络B,与网络A中失效节点相依赖的网络B中的节点失效,对此时的网络B开启新一轮的恢复过程.以此类推,两个网络就这样迭代下去,直至两个网络构成的系统达到稳态.

La Rocca等[67]指出随着γ的增加,临界阈值pc降低,网络破碎的形式也会从一阶相变转变为二阶相变,这就使得两个网络在发生网络崩溃前可以克服更多节点的失效.这也是为什么La Rocca等认为将此恢复策略应用在两个相依网络中较为脆弱的那个网络,会使整个系统的抗毁性提高.根据不同的恢复概率γ和网络的初始保留概率p,就可以知道网络是能被恢复的,还是不能避免它最终的崩溃.

4.3 加边恢复策略

加边恢复策略是以相依网络级联失效模型[15]为基础通过进行一系列的加边,来增加网络鲁棒性的恢复策略[72].过程如下: 在晶格网络A中,对于一个被移除的节点,将其邻居中没有被移除的具有功能性的两个节点以概率w相连.网络B中与网络A中的失效节点具有依赖关系的节点也会失效,因此网络B也需要实施上述的恢复过程,即失效节点的两个未失效且不直连的邻居以概率w进行连接.其实恢复步骤是将每个失效节点的所有邻居对当作候选者以概率w连接,节点失效,找出邻居对连接,再有节点失效···,整个过程待两个相依网络达到动态平衡,即没有连边或者节点再失效后结束.随着时间的推移,修复连接可能会极大地改变拓扑结构,新建立连接的两个节点之间在原始晶格网络上的距离可能越来越大.

4.4 优先恢复重要节点策略

Gong等[73]提出在级联失效后,优先恢复重要节点的策略.通过在三个不同类型的耦合网络(随机网络-随机网络(ER-ER)[74],随机网络-无标度网络(ER-SF)[73],电力网络-无标度网络(power-SF)[73]上分别应用6种不同的重要节点识别指标(随机、度中心性、介数中心性、PageRank、LeaderRank)来确定优先恢复的节点,结果发现只需恢复网络中5%的重要节点就可以显著恢复网络功能,尤其是介数中心性指标效果最优.而基于度中心性指标和PageRank指标的恢复策略的优点在于其较低的计算复杂度,可用于具有数百万节点的大规模相依网络.

相依网络的恢复过程如下(例如按照随机选择): 对于一个已经级联失效的网络,初始时假设图中的节点均为失效节点.如图6(a)所示,假设恢复网络C中的节点1,2,3和4,那么网络D中与网络C相依赖的节点5,6,7和8 被触发而恢复正常(图6(b)).然后,由于网络C中已恢复节点4和它在D网络中的依赖节点8不在各自网络的巨分支中,所以它们会再次失效(图6(c)).同理,网络D中的节点5由于孤立失效,而导致与其依赖的C网络中的节点1也再次失效(图6(d)).此时网络达到稳态,网络中的节点2,3,6和7就是本次恢复过程执行后最终被真正恢复的节点.

图6 恢复模型Fig.6.Schematic diagram of recovery model.

4.5 更改拓扑结构策略

Schneider等[66]提出了一种有效恢复电力网络故障的方法,他们发现在不增加连边数量的情况下,只要对给定网络的拓扑结构进行相对较小的修改,就有可能大大降低恶意攻击的危害.这一结论在两个真实网络,即欧洲电网和互联网中得到了验证.这一发现,一方面可以指导现有网络通过结构的优化来提升鲁棒性,另一方面也可以用来设计未来的基础设施,使其具有更好的鲁棒性.我们通常是用临界阈值来衡量网络的鲁棒性.而这种方法忽略了如果网络受到了攻击但是并没有崩溃的情况.所以他们引进了一个独特的测量鲁棒性的方法,

其中N是网络中的节点数,S(Q)是在删除了Q个节点之后网络巨分量中节点的数目.

4.6 局域攻击修复策略

局域攻击也叫局部攻击,指的是网络位于某个地理空间范围内的节点受到了攻击.在现实生活中,局域攻击比随机攻击更为普遍,如军事打击、自然和人为的灾害等[75].文献[71]提出了优先最小度修复策略(the healing strategy by prioritizing minimum degrees,HPMD),空间相依网络出现局部攻击时可以采用此策略.失效网络的模型依托于文献[76],优先最小度策略是将一个失效节点的两个度值最低的邻居相连进行恢复,对比度中心性、随机选择和局部中心性,此方法更优.

4.7 自适应边恢复策略

Liu等[77]提出在多层网络中添加自适应边的恢复策略.为了增加多层网络的鲁棒性,抵御大规模节点失效而导致的网络崩溃,在多层网络中,网络A定义为控制层网络,而网络B,C,··是非控制层(不能人为干预),当网络A中的节点ai脱离其巨分支时,我们规定节点ai会随机产生M条边连接在网络A中的其他节点上,也就是说产生的M条自适应边中只要有一条连接在了网络A的巨分支上,节点ai就会从失效状态恢复成具有正常功能的状态(在此过程中假设与ai相依赖的其他网络层中的节点均没有失效,都具有正常功能).根据经典的相依网络级联失效模型,我们知道当ai脱离巨分支时,其他网络层中与之相互依赖的节点也要失效,而在节点ai脱离时,产生的M条自适应边会很大程度上保证这个节点被修复,这意味着其他层中与节点ai具有依赖关系的节点会因为这个自适应边的加入而以很大概率避免了脱离其各自网络的巨分支.所以对其中一个网络层的自适应扰动不仅可以增强控制层网络自身的鲁棒性,还可以增强其他互连网络层的鲁棒性.

5 讨 论

多层网络鲁棒性是当前复杂网络和复杂系统研究的核心问题之一.基于渗流理论的研究发现由于网络之间的联系和依赖,多层网络往往是非常脆弱的.这一结果为一些基础设施出现突发大规模级联失效给出了理论解释.但是还有一些基础设施系统却非常稳定,大规模的失效现象很少出现.因此,为了理解基础设施系统的鲁棒性和脆弱性,有关多层网络鲁棒性第一个方面的研究是对具有不同耦合机制、拓扑结构的多层网络进行建模,并研究这些因素对多层网络鲁棒性的影响以及网络在遭受攻击时破碎的机理.第二个方面是如何设计有效的预防措施或节点恢复策略来降低级联失效对多层网络的损害.这两个方面的研究相辅相成,第一个方面的研究为第二方面的研究提供了基础理论和思路.本文所介绍的多层网络级联失效的预防策略大多基于第一个方面的研究成果,由渗流理论可知度值较小的节点很容易因网络中其他节点的删除而失效,而度值较大的节点失效的时候会产生较大的破坏性,因此,当跨网络层的节点随机耦合时多层网络会比较脆弱,这为调整耦合机制提供了重要思路.此外,节点的保护策略也同样基于对多层网络破碎机理的研究,例如理论研究发现多层网络临界簇中的“基石节点”是至关重要的,这为保护多层网络中的重要节点提供了重要思路.

多层网络级联失效的抑制策略研究同样建立在对多层网络破碎机理的理解之上,如边界节点恢复模型、加边恢复策略等.无论是对节点的恢复,还是对网络进行加边,都需要一定的代价.如何达到效用和代价的最优? 为什么需要恢复边界节点?哪些节点需要优先加边恢复? 回答这些问题同样需要理解多层网络的破碎规律和特点.对于不同的多层网络发生级联失效的时候,该采用什么样的决策方法来选用恢复策略呢? 目前来说,回答这一问题尚有比较大的挑战,但可以肯定的是恢复策略的选用需要结合具体的情况,如多层网络拓扑结构特性、耦合机制、网络损害规模和实际需求,以及恢复的代价限制和速度要求等.随着对多层网络级联效应研究的深入,相信对这一问题的研究会不断取得突破,而且会有更多的、更加贴合现实情景的预防和恢复策略被提出.