基于最大连通子图相对效能的相依网络鲁棒性分析

赵 娜，柴焰明，尹春林，杨 政，王 剑，苏 适

(1. 云南大学软件学院 昆明 650091；2. 云南大学软件学院软件工程重点实验室 昆明 650091；3. 云南电网有限责任公司电力科学研究院 昆明 650217；4. 昆明理工大学信息工程与自动化学院 昆明 650504)

随着社会和科技的发展，现实中各事物的联系越来越多，这些联系都可以用网络系统来描述。随着这些关系变得错综复杂，逐渐产生了两个甚至多个系统之间的联系，形成相互依存网络。为衡量相互依存网络在级联失效过程中的鲁棒性，需要一个能准确衡量鲁棒性的测度指标。目前大部分网络鲁棒性研究都直接采用攻击后最大连通子图比例作为鲁棒性指标，该指标虽能较合理反映网络鲁棒性，但在实际应用时也因适用性和准确性的问题而常被诟病。此外，目前大多数鲁棒性指标都是针对单一网络，专门针对相互依存网络鲁棒性评价指标的探讨却较少。因此，有必要对常用鲁棒性指标进行准确性和适用性的探讨，并对相互依存网络的特点进行分析，提出新的相互依存网络鲁棒性指标。

本文对几个常用的具有代表性的鲁棒性指标进行分析，针对一般相依网络级联失效过程，提出了最大连通子图相对效能比的鲁棒性度量指标。通过相互依存网络级联失效模型的攻击实验表明，相比于现有常用指标，该指标能更准确地衡量相依网络在级联失效过程中的鲁棒性变化，在大规模的网络中具有明显优势，可适用于相依网络中基于仿真的鲁棒性分析。

1 研究现状

复杂网络的鲁棒性研究最初起源于2000年。文献[1]最先提出以最大连通子图和平均最短距离作为鲁棒性指标对复杂网络的鲁棒性进行研究，在国内外引起了广泛关注。目前大部分的文献都采用最大连通子图及其变形来度量网络的鲁棒性(如网络攻击前后最大连通子图规模比例、连通子图个数等)，并且以网络的攻击实验作为研究鲁棒性的主要方式。文献[2]从网络构建的角度，提出用自然连通度作为鲁棒性指标来分析使用不同方式给网络增边后对鲁棒性的影响。文献[3]将自然连通度指标放入网络攻击实验中进行了验证。文献[4]对自然连通度做了优化，提出基于禁忌搜索以及网络效率权衡优化模型的方法优化网络鲁棒性。文献[5]提出了一种提高复杂网络结构鲁棒性方法，使用连通度、失效节点比例、网络效率等多个鲁棒性度量指标，并在车载自组织网络中进行应用分析。文献[6]基于MapReduce框架的网络，给出了连通率和效率比两个鲁棒性指标观测不同攻击策略下网络的鲁棒性。文献[7]从点韧性度的角度设计了一个基于粒子群的网络鲁棒性计算的改进算法。文献[8]从攻击方式的角度提出了介度熵鲁棒性度量方法，验证了介度中心性的攻击方式优于传统攻击方式。文献[9]则以图熵的角度构建介度熵指标，依据冯诺依曼熵提出了子图信息熵和H信息熵的鲁棒性指标。文献[10]就谱图论，采用Kirchhoff指数衡量网络鲁棒性以寻找并获取网络中较为稳定的边界。

相依网络鲁棒性研究最早开始于2010年。文献[11]基于渗流理论构建了级联故障渗流模型，并对相依网络鲁棒性进行了研究。文献[12]使用小世界网络、随机网络和无标度网络，研究了由不同类型网络构成的相依网络在目标攻击和随机攻击下的鲁棒性。文献[13]指出相依网络中网络间的相依方式有同配相依(度数相近)、异配相依(度数相差较大)、随机相依3种，并使用BA-BA相依网络模型研究不同相依方式下耦合强度对网络鲁棒性能的影响。文献[14]就相依网络中出现的级联失效现象，构建了基于负载重分配的级联失效模型，以相依边的负载作为耦合强度来探究耦合强度对网络鲁棒性的影响，发现鲁棒性与耦合强度并非单调性关系。文献[15]改进了传统负载级联失效模型，重新定义了节点失效条件，并使用介数作为网络相依方式的界定因素，进而发现鲁棒性与网络间相依方式、耦合强度和重要节点密切相关，且影响程度不同。文献[16]综合了以上研究结果，在基于负载的相依网络鲁棒性研究中，将相依方式整理为7种，其中包括从度相关和介数相关来构建同配异配相依方式，甚至是度和介数混合相依，同时将节点初始负载定义为在度相关和介数相关之间可线性变换的方式。文献[17]针对异质弱相依的相依网络进行鲁棒性研究，其中考虑到节点失效后其相依节点的所有连接边不会全部失效，而是以一个概率失效，且每个边失效的概率也不同，研究得出网络鲁棒性与网络异质程度正相关。文献[18]研究了多重非对称相依网络的鲁棒性，发现在该网络模型中，具有多重相依关系的层会存在混合相变，而没有多重相依关系的另一层只出现一阶相变。

纵观以上研究可以发现，以上研究所采用的鲁棒性指标几乎都是最大连通子图比例及其变形，且已有的对鲁棒性指标的讨论也都是针对单一网络，而针对相依网络鲁棒性指标的讨论很少。此外，在相依网络研究中，大部分都过于依赖单一网络的思想，导致鲁棒性指标也采用单一网络的指标而没有考虑其在相依网络中的适用性。因此，本文针对一般相依网络级联失效过程，提出了新的鲁棒性度量指标，目的在于使鲁棒性指标更好地适用于相依网络且具有较高准确性。

2 相依网络的级联失效模型

2.1 相依网络的构建

为了使研究更具代表性，同时降低研究的复杂性，本文只考虑由两个网络构成的相依网络，且根据一对一相依关系来构建相依网络模型。

根据复杂网络理论，相依网络一般用基于图论的数学模型来表示[16]。单个网络用图G(V,E)来表示，其中V是图中所有节点的集合，E是图中所有边的集合。对于两层相依网络，其子网络分为网络A和网络B，分别记为GA(VA,EA)和GB(VB,EB)。为了描述相依网络中网络间的相依关系，需额外构建矩阵来表示网络间节点相依边的邻接矩阵。则相依网络可以表示为GAB(GA,GB,EAB,EBA)，其中EAB、EBA是网络A与网络B之间相依关系的邻接矩阵，设两个网络的节点数分别为NA=m,NB=n，则以EAB为 例可表示为规模m×n的矩阵：

式中，ei,j表示网络A中节点i与网络B中节点j的相依关系，若存在相依关系，ei,j=1，否则ei,j=0。

2.2 级联失效模型的构建

级联失效是复杂网络中的一种典型的故障传播模式。网络中，在一个或部分节点因故障失效后，会通过相依关系使相依节点发生失效，进而引发其他节点接连失效，产生级联效应，最终导致网络大面积崩溃甚至完全崩溃。本文采用一般相依网络级联故障模型，根据此模型可以得出节点失效的情况如下：1) 节点受到随机或蓄意的直接攻击影响而失效；2) 一个节点的失效导致与其相依的节点失去了相依关系而失效；3) 随着节点的失效导致网络中一些节点脱离了最大连通子图，失去了与网络大部分节点的联系，导致这些节点即使没有被直接攻击也会失效。

相依网络级联失效过程如下：

1) 攻击相依网络中的一个或一定比例的节点，由于网络的相依性，与该节点相依的节点也会失效(之后任何节点失效时都伴随其相依节点失效)。

2) 检查剩余网络，如果有节点脱离了最大连通子图，该节点也视为失效。

3) 如果在步骤2)中有节点失效，则重复步骤2)，否则级联失效结束。

上述过程如图1所示，其中，相依网络由网络A和网络B构成。假设对节点A5进行攻击，使A5失效，从网络A中移除与A5相连的边，则与其相依的节点B5因失去了相依关系而失效，从网络B中移除与B5相连的连接边，此时网络达到阶段1的状态。随后，随着A5的失效，节点A6脱离了网络A的最大连通分量成为孤立节点，导致其与其他节点失去联系而失效，对应地其相依节点B6失效。同理节点B4成为孤立节点而失效，其相依节点A4失效。经过以上级联失效后最终形成阶段2的稳定状态。

图1 相依网络级联失效过程

3 相互依存网络鲁棒性指标构建

在基于仿真的鲁棒性分析中，网络在受到攻击后，主要关注的是其拓扑结构和连通性的变化。当前研究中最常用的最大连通子图比例和网络效能比指标也是基于这一思想。本文针对相依网络，在最大连通子图比例和网络效能比的基础上，考虑相依网络每个子网络在攻击前后相对于整个网络的连通性，提出了新的基于最大连通子图相对效能比的相互依存网络鲁棒性指标，来衡量相依网络级联失效过程中网络鲁棒性变化状况。

3.1 常用鲁棒性指标定义

定义1 攻击后网络最大连通子图比例F

攻击后网络最大连通子图比例是目前复杂网络鲁棒性研究中最常用的指标，指攻击后网络中最大连通子图的节点数量与整个网络中全部节点数量的比值：

式中，N′表示网络受攻击后最大连通子图中的剩余节点数量；N表示整个网络中全部节点的数量。该指标反映了网络遭受攻击后的拓扑结构的变化。

定义2 网络效能比EM

网络效能是一个量化节点间连通性和通信效率的鲁棒性指标，为网络中任意两个节点间最短路径距离的倒数的平均值。由于节点间最短路径又称为测地线，因此网络效能也可以称为反测地线距离[7]。对网络效能E的定义如下：

式中，Ei和Ec分别为攻击前和攻击后的网络效率。按照性质可知，网络效能比EM越大，则网络鲁棒性越好。

3.2 最大连通子图相对效能比

级联失效过程中，网络中任意节点在失效时，并非将该节点从网络中完全移除，而是使其失去所有连接边，以孤立节点的形式存在于网络中。根据这一点可知，设N表示整个网络中全部节点的数量，N′表示网络受攻击后最大连通子图中的节点数量，则网络在攻击前后N是不变的，而N′逐渐减少，若攻击后网络完全崩溃，则网络中所有节点均为孤立节点，不存在最大连通子图，即N′=0。根据级联失效模型和渗流理论可知，只有当节点在最大连通子图中时，才能够保持正常运作，而节点脱离了最大连通子图时，会因失去与网络大部分节点的联系而失去正常工作的能力导致失效[16]。而网络效能始终以整个网络的角度来衡量网络的连通性，这会将已经失效的孤立节点也一并纳入衡量，无法准确得知最大连通子图在级联失效过程中的变化情况。因此，本文结合级联失效过程中网络全局和最大连通子图的变化情况，给出最大连通子图相对效能LRE (largest-component relative efficiency)的定义，并进一步提出最大连通子图相对效能比LREM(largest-component relative efficiency measurementratio)。

对于一个网络n中的最大连通子图，其网络效能E′表示为：

和网络效能同理，为了对比攻击前后的效果，对LRE进行归一化处理，形成最大连通子图相对效能比LREM指标，按以下公式计算：

式中， LREi和 LREc分别为攻击前和攻击后的LRE值。与EM同理，LREM越大，表示网络鲁棒性就越强。

4 仿真分析

本文在相依网络上进行级联失效模型仿真，通过观察在不同的相依网络上各鲁棒性指标的表现，来验证这些指标在相依网络中的鲁棒性度量是否合理且准确。

4.1 仿真实验设定

为了使实验更具代表性和直观性，本文参照现实中常用的复杂网络结构，设定仿真实验构建的相依网络模型由BA无标度网络模型和WS小世界网络模型两两相互连接构建而成，构成BA-BA、BAWS、WS-WS相依网络模型，其中BA无标度网络模型是参照文献[19]提出的无标度网络演化算法构建的网络模型，WS小世界网络模型则是遵循文献[20]提出的小世界网络演化算法来构建的模型。设定每个子网络规模N=1000，BA网络遵循BA(N,m=2)， WS网 络 遵 循 WS(N,K=4,p=0.5)，则显然对于相依网络，平均度 〈k〉=4。两个网络间的相依方式为按照度数差的大小添加相依边，分为同配相依(AL)、随机相依(RL)和异配相依(DL)3种相依方式。相应地，攻击方式采用全网高度数蓄意攻击方式，从整个网络中攻击度数最高的数量比例为p的节点，并规定一个完全崩溃阈值pc为使网络恰好完全崩溃时的p值。攻击全过程遵循2.2节中所述级联失效模型。所有实验结果均为实验20次后取平均值，进行对比的鲁棒性指标分别为网络最大连通子图比例F、网络效能比EM和最大连通子图相对效能比LREM。

4.2 仿真结果分析

图2为BA-BA相依网络模型下攻击比例为p的节点各鲁棒性指标的变化情况。可以看出，在高度数蓄意攻击下，整个网络会显得非常脆弱。最坏的情况为在相依方式为异配相依，攻击比例p=0.3左右时网络就完全崩溃(F=0)，即pc≈0.3。而同配相依的pc≈0.46时网络才会完全崩溃，随机相依则介于同配相依与异配相依之间。结合F指标可得出，BA-BA相依网络在全网蓄意攻击下，同配相依时鲁棒性最好，异配相依时鲁棒性最差。根据BA无标度网络的网络特性，每个节点更倾向于与度数大的节点相连接，则网络中度数大的节点会凝聚在一起。另外，鲁棒性指标EM和LREM的表现与F相似，随着p的增加，EM和LREM都在逐渐减小，最终网络完全崩溃时，EM=LREM=0。网络破坏程度较小时，相比F，LREM减小最快，EM其次，且它们的值明显比F小，即LREM＜EM＜F，这说明网络中从LREM体现的鲁棒性比F和EM更弱；而在网络接近崩溃时，EM和LREM基本接近于0，此时减小幅度放缓，但存在一个pm值 (pm＜pc)，使得当p∈(pm,pc)时LREM会略微大于EM。这是因为EM是面向相依网络整体进行计算，而LREM是对相依网络中每个子网络的最大连通子图进行计算并取平均值，则在网络节点数较少时，相依网络整体的效能要低于每个子网络的平均效能。因此可以看出，相比F和EM，LREM对网络的鲁棒性的变化更加敏感，并在规模较大的网络中对鲁棒性的衡量具有较大优势。

图2 BA-BA相依网络蓄意攻击下的鲁棒性

图3为BA-WS相依网络模型下攻击比例为p的节点各鲁棒性指标的变化情况。可以看出，3种相依方式体现的鲁棒性在p＜0.1时几乎相同，但在p＞0.1以后发生分歧，和BA-BA网络同样表现为同配相依时鲁棒性最好(pc≈0.6)，异配相依时鲁棒性最差(pc≈0.4)。此外，3个指标的表现与BA-BA网络的基本相同，区别在于EM和LREM的差距较小。WS网络的度分布较为均匀，没有度数明显高的节点，因此在全网高度数蓄意攻击下容易先从BA网络攻击。同理，BA网络在大规模的蓄意攻击下，相依网络会迅速崩溃，但由于WS网络的存在使得网络的崩溃程度不及BA-BA网络。

图3 BA-WS相依网络蓄意攻击下的鲁棒性

图4为WS-WS相依网络模型下攻击比例为p的节点各鲁棒性指标的变化情况。可以看到，无论哪种相依方式都有pc＞0.8，即网络完全崩溃的攻击比例都在0.8以上。由于相依网络中不含有BA无标度网络，所以相较于含有BA网络的相依网络来说，无论什么相依方式都比上述两种类型的相依网络模型抵御蓄意攻击而产生的级联故障的能力要强。这说明了WS-WS相依网络模型具有很强的鲁棒性，同时体现了WS小世界网络抵御蓄意攻击能力较强的特性。从指标来看，在WS-WS网络下，LREM的表现与之前相比发生了变化，在网络破坏程度较小时有LREM的值大于EM的情况出现。再结合图2和图3的结果，可以看出，在较为脆弱的网络中，LREM对鲁棒性的反映比EM更小，在较为健壮的网络中则更大。这并不意味着LREM的敏感性在较为健壮的网络中不如EM，而是说明LREM能更细致地凸显网络鲁棒性的强弱程度，也能看出LREM更加敏感。

图4 WS-WS相依网络蓄意攻击下的鲁棒性

综合以上结果可以得出，在全网蓄意攻击下，含有BA无标度网络的相依网络的抵抗能力会减弱，同时同配相依时鲁棒性较好，异配相依时鲁棒性较差。在指标的表现上，本文提出的最大连通子图相对效能比LREM能够正确反映相依网络在级联失效过程中的鲁棒性变化情况，且任何情况下随着网络的逐渐破坏，LREM的值始终小于最大连通子图比例F，即鲁棒性的减少程度明显大于F。对于网络效能比EM，网络破坏程度较小时，在较为脆弱的网络中(如BA-BA网络)LREM小于EM，在较为健壮的网络中(如WS-WS网络)则大于EM；在网络接近崩溃时，由于子网络连通性强于相依网络整体连通性导致LREM会略微大于EM。由此表明，相比于现有常用指标最大连通子图比例F和网络效能比EM，本文提出的最大连通子图相对效能比LREM对相依网络中鲁棒性的变化更加敏感，尤其在规模较大以及结构相对脆弱的网络中优势更大，能更准确细致地衡量相依网络在级联失效过程中的鲁棒性变化，适合大规模相依网络中的鲁棒性度量。

5 结 束 语

本文针对相依网络，结合现有常用的最大连通子图比例和网络效能比指标，综合考虑每个子网络在攻击前后网络全局和最大连通子图的连通性，提出了一个结合了最大连通子图比例和网络效能的鲁棒性度量指标—最大连通子图相对效能比LREM，并在BA-BA、BA-WS、WS-WS相依网络模型下与现有常用指标进行对比研究。研究发现，最大连通子图相对效能比LREM相比于现有常用指标能更精确地衡量相依网络在级联失效过程中的鲁棒性变化，尤其在规模较大以及结构相对脆弱的相依网络中具有明显优势，是一个评估相依网络鲁棒性变化的合理度量指标。

本文为保证研究的代表性，主要针对两层一对一相依网络进行鲁棒性研究，而在现实的相依网络中还会存在很多非对称的相依关系，如部分相依、有向相依、一对多或多对多相依等，并且可能会出现更多层的网络以及节点或边带权等情况，需要综合考虑的因素较多。因此，在未来的工作中需要将LREM鲁棒性指标放入更加实际的应用环境中进行验证，综合考虑各种因素改进LREM指标，使其具有更加准确的度量效果。

本文研究工作还得到昆明市卫健委项目(2020-09-04-112)的资助，在此表示感谢。