考虑相依边负载的相依网络鲁棒性研究
时间：2023-02-22 18:25:06 来源：千叶帆 本文已影响人
余荣斌，蒋 沅，严玉为，洪 成
(南昌航空大学信息工程学院 南昌 330063)
在现实世界中，存在着许多相互依赖的复杂网络，这些不同网络之间存在着紧密联系。当网络受到某些因素影响时，会对其他相关网络产生不同程度的危害，进而造成大规模损失。如2019 年3 月委内瑞拉电力系统遭遇多次攻击[1]，国内大部分地区持续停电，电网故障导致交通堵塞、信息网络受阻；
2020 年新冠肺炎疫情在全球爆发[2]，造成大规模传播，社会各个行业都受到严重影响；
2021年3 月“长赐”号在苏伊士运河搁浅[3]，导致全球海运航道发生堵塞，对一些大宗商品市场、全球供应链和原材料价格带来了一系列影响。因此，研究此类相依网络之间的联系和鲁棒性具有重要的现实意义。
自2010 年，文献[4]在《Nature》杂志上发表后，相依网络的应用与研究成为了国内外学者关注的热点。目前，相依网络失效模型在一系列基础设施网络中应用较为广泛，如文献[5]分析了在极端天气下，公交−地铁复杂双层网络的连锁故障和网络系统的脆弱性演化。文献[6]基于出行时间的可达性、出发的最佳可及性和往返行程的无障碍性3 种衡量行程时间的指标，来分析时变可访问性对地铁和高铁相依网络系统的影响。文献[7]先对电力信息物理相依系统进行建模，后深入分析了节点脆弱性新特性、线路耦合深度和信息失效对网络相变特性的影响。文献[8]构建了高铁−普铁交通双层复杂网络，并对子网络和相依网络的拓扑静态指标进行了分析。而文献[9-10]分别在随机攻击和蓄意攻击的基础上，提出了一种考虑破坏力随距离衰减的局部攻击模式和多种攻击方式组合下的联合攻击策略。文献[11-12]分别提出局部优化NPC(邻居节点优先连接)的耦合策略和基于重叠链路结构的相互依赖网络耦合策略，这些耦合策略相较于传统的随机、同配和异配耦合模式能更有效地增强网络系统的鲁棒性。文献[13]在渗流理论的基础上提出了级联故障渗流模型，并分析了相依网络的耦合强度对网络相变特性的影响。文献[14-15]基于负载局域分配原则提出了负载级联失效模型，引入了节点负荷过载的失效情况，并研究了具有不同攻击策略、连接模式和负载分配机制的相互依赖网络的鲁棒性。文献[16]提出一种新的基于社区结构的容量分配策略，在不改变网络结构的情况下，这种策略能有效减少级联故障，提高网络鲁棒性。文献[17]提出了一个基于负载波动下相互流量重新分配的依赖网络级联失效模型，并通过流量损失参数来分析网络现有资源的流量损耗。但这些研究的负载级联失效模型集中于分析网络内的节点和连边，忽视了网络间的相依边同样具有负荷流动的现象。文献[18]通过建立对称相依网络和不对称相依网络模型，对负载最大的子网络相连边和相依边分别进行失效，对比网络相连边和相依边对相依网络临界成本的贡献，然而文献中并未考虑现实相依网络中相连边和相依边负载所指代的物理意义并不相同，网络内的负载在进行负载重分配时一般不进行跨网络传输。
通过对上述文献的梳理，发现多数文献的研究并没有考虑子网络之间相依边的负载，现实中不但网络内部存在负载，而且不同网络之间的信息传递也具有负荷流动的现象。相依网络中的相依边不但具备逻辑上的相依关系，也存在功能上的实际负载量。如电力网络与交通网络之间存在具体信息的传递，这些信息也受负荷流动和容量限制的约束；
在不同的交通网络间存在换乘问题，公交网络站台和地铁网络站点之间的换乘路线可视作网络间的相依边，换乘的人数为相依边上的负载量，而恶劣天气造成的部分路面积水和道路维修导致的局部封路等情况都会使乘客换乘不便，不得不改换邻近站点进行换乘。
本文在这些研究的基础上，提出了考虑相依边负载的相依网络级联失效模型，并定义相依边的初始负载和初始容量，失效情况综合考虑了相依边过载失效、相依节点故障和非最大连通子图损失。以2021 年6 月南昌地铁网络(http://www.ncmtr.com)和部分公交网络(https://nanchang.8684.cn)组成的相依网络作为模型的实际用例，对模型的物理意义和合理性进一步说明。另外本文对考虑相依边负载的相依网络进行了多角度的分析，为进一步改善相依网络的级联失效提供新的途径。
1.1 相依网络拓扑结构与性质分析
本文的相依网络系统由独立的两个子网络构成，分别为子网络GA和 子网络GB，而且节点总数为N=NA+NB，它们都有特定的网络拓扑结构，并通过一定的方式进行连接。其中子网络中内部节点连接的边定义为相连边，子网络GA和GB之间节点连接的边定义为相依边。
网络系统中的子网络以GA网络为例，它的简单系统图可以表示为GA=[VA,EA]， 其中VA={vAi|i=1,2,···,NA}表 示相依网络中子网络GA的节点集，EA={eAij|eAij=(vAi,vAj),i=1,2,···,NA;j=1,2,···,NA;i代 表了子网络GA中节点之间相连边的边集，eAij表示子网络GA中 节点vAi与节点vAj相连，同理子网络GB也具有相类似的系统图表示。
在相依网络中将相依边的边集定义为EAB={eAiBj|eAiBj=(vAi,vBj),i=1,2,···,NA;j=1,2,···,NB;i和j可以相等}，当eAiBj=1表 示子网络GA中的节点vAi与子网络GB中 的节点vBj连接，即子网络GA中节点vAi与子网络GB中 节点vBj具有相依关系，反之则eAiBj=0。
为方便研究相依边的负载分配，本文定义一个新的参数：邻近相依边集，某相依边eAiBj的邻近相依边集可表示为E L=ELA∪ELB， 其中ELA={eAiBb=(vAi,vBb)|vBb∈Γi}， ELB={eAaBj=(vAa,vBj)|vAa∈Γj}，Γi表示子网络GB中 除节点vBj以外与节点vAi相连的节点集合， Γj表示子网络GA中 除节点vAi以外与节点vBj相连的节点集合， Γi和 Γj为点集。邻近相依边集如图1 所示，设某相依边为eAiBj，那么它的邻近相依 边 集 EL 有eAa1Bj、eAiBb1和eAiBb2。上 式 中Γi={vBb1,vBb2}， Γj={vAa1}， ELA={eAiBb1,eAiBb2} ， ELB={eAa1Bj}， EL=ELA∪ELB={eAa1Bj,eAiBb1,eAiBb2}。
图1 相依网络的邻近相依边集
为进一步分析文中所提出的考虑相依边负载的相依网络的相依程度和耦合模式，沿用文献[19]定义的两个参数F和K，F为相依节点的比例，K为相依冗余度。FA表 示子网络GA的相依节点数占子网络GA节 点总数的比例，FB表示子网络GB的相依节点数占子网络GB节 点总数的比例；
而KA为在子网络GA中 相依节点的平均相依边数，KB为在子网络GB中相依节点的平均相依边数。本文定义相依网络为对称相依网络时，NA=NB，F=FA=FB，即两个子网络具有相同的网络规模和相依节点比例，且K=KA=KB；
若为不对称相依网络时，即NANB，FAFB时 ，此时K=min{KA,KB}。如在图2中，FA=1，FB=0.6，KA=KB=3。
图2 两个简易子网络构成的相依网络
同时网络之间的耦合关系以节点的度值为标准，子网络GA与GB之间有同配耦合、异配耦合和随机耦合3 种不同的耦合模式。其中同配耦合是先对子网络GA与 子网络GB中的节点分别按节点度值的降序排列，再将节点进行配对连接，连接的具体步骤为先将每个子网络中降序排列好的前M个节点进行分组(当NA=NB时 ，M=NA=NB；
当NANB时，M=min{NA,NB}) ，以K个节点为一个单元组(其中K为相依网络的相依冗余度，当M个节点无法被相依冗余度K整除时，则剩余的余数单独组成最后一组)。假设子网络GA和GB中 前M个节点被分为n组 ：Z1,Z2,···,Zn和U1,U2,···,Un， 将子网络GA中第一组的每个节点与子网络GB中第一组的所有节点进行连接，即Z1−U1， 并以此类推使得Zi−Ui，最终Zn−Un。
同理可知，异配耦合则将子网络GB中的节点按度值的升序排列，将子网络GA中的节点按度值降序排列，具体连接方式与同配一致；
随机耦合则对每个子网络随机选取M个节点进行分组，具体连接方式与异配相同。
在子网络的选取时，本文采用3 种经典的人工网络模型作为相依网络的子网络。其中BA(Barabási-Albert)无标度网络模型的具体构建算法是先在给定初始节点m0的情况下，每一步都添加一个新的节点，然后将新节点与m个已存在的节点进行相连，且规定m⩽m0，相连方式按择优连接的概率进行连接[20]。WS(Watts-Strogatz)小世界网络模型的构造算法是先从规则网络开始，再进行随机化重连，即将网络中的每条边以概率p进行重连[21]。ER(Erdős-Rényi)网络模型构建方法是以WS 网络模型为基础的，不同点在于重新布线的概率p=1[22]。本文中这3 种经典网络的节点数都选择200 个节点。
将2021 年6 月南昌地铁与部分公交网络系统作为模型的应用实例，地铁公交网络是由3 条地铁线路与40 条客流量最大的市区公交线路组成。由3 条地铁线路组成的地铁网络共有70 个站点，而由40 条市区公交线路组成的公交网络共有511 个公交站点。将站点抽象为网络节点，相同交通工具的站点间的连接线路看作相连边，不同交通工具站点之间可换乘的线路为相依边，可换乘的条件设为地铁站点和公交站点之间距离在800 m 以内，换乘的人数抽象为相依边的负载。若在换乘时遇到不可避免的因素，乘客不得不改换邻近站点进行换乘，如何优化分配改换站点的人数以使得换乘线路不会因为换乘人数太多而导致拥堵和滞留，这一问题可看作考虑相依边负载的相依网络级联失效模型的实际应用之一。将市区公交网络设为子网络GA，地铁网络为子网络GB，此相依网络的相关参数如表1所示。
表1 2021 年6 月南昌地铁与部分公交网络的相关参数
1.2 相依边负载容量模型
在ML 模型的基础上[23]，本文提出了一种考虑相依边的负载容量模型，相依边eAiBj的初始负载表示为：
式中， α为可调参数，一般 α ⩾0，表示相依边的冗余程度即容忍系数，控制相依边的容量阈值。
基于相依边的负载重分配规则，假设相依边eAiBj失 效时，邻近相依边eAxBy以一定的分配比例获得额外的负载 ∆LAiBj， 当LAxBy+∆LAiBj>CAxBy时，邻近相依边eAxBy过载失效，网络继续对失效的相依边进行负载分配，直到任意相依边的容量大于负载时，网络间相依边的负载失效才停止。相依边的负载重分配示意图如图3 所示。
图3 相依边的负载重分配
1.3 级联失效模型的构建
本文的级联失效模型中失效具体情况一般分为以下4 种，并且任意一种攻击和故障导致的节点失效，其对应的所有边也会被清除：
1) 在初始状态下外部攻击导致的初始失效可分为3 种，其中任意一种攻击方式都可以引发网络的初始失效。
① 外部直接攻击节点导致的节点失效。
② 外界进攻网络内的相连边，以至于节点失去所有相连边，则该节点故障并被移除。
③ 外部袭击网络间的相依边，致使相依节点失去所有相依边，此相依节点失去了所有与另一个子网络耦合链接的物理通道，相对应的信息或负荷无法通过该相依节点进行跨网络传输，故视该节点失效。
2) 基于渗流理论的级联故障渗流模型[19]，在子网络中若某一节点脱离了最大连通子图，则该节点失效[24]。
3) 在级联失效过程中，若节点为相依节点，由于失去了所有的相依边，该相依节点与另一个子网络的依存关系消失，相依节点与另一子网络间的正常联系中断，此相依节点失效[25]。
4) 基于上文中的相依边负载容量模型，当网络间的相依边失效时，会将失效相依边上的负载以一定比例分配给邻近相依边，若负载超过容量则发生过载失效，继续导致邻近相依边集的故障。在地铁公交网络中，假设在理想状态下换乘线路上的换乘人数超出额定的容量时，换乘线路失去基本换乘功能。根据以上4 种失效模式，制定了模拟考虑相依边负载的级联失效模型的详细步骤如下。
① 对子网络GA进 行初始攻击，移除被攻击的节点与连边。
② 子网络GA分 裂成若干个子图和孤立节点。基于渗流理论，当节点移除比例超过临界相变点，子网络被分解成多块互相不连通的集团。在网络中只有最大连通片保持基本的功能和相对的全局连通性，由于其余子图中的节点和孤立节点在结构上与最大连通子图并不连通，故可视为故障节点[4]。
③ 子网络GA内节点的移除，导致大量相依边失效。根据相依边负载容量模型，失效的相依边对邻近相依边集分配额外的负载，当邻近相依边的总负载量超过容量限制时会导致过载失效。
④ 相依边的过载失效和子网络GA内节点的移除使得子网络GB内相依节点失去大量的相依边，子网络GA的故障经过相依边负载重分配后传播到子网络GB。
在子网络GB中，那些失去所有相依边的节点失效。
⑤ 基于级联故障渗流模型，子网络GB内发生步骤②中相似的非最大连通子图失效。若此时整个系统达到稳定状态，则失效结束，反之则将故障传播到子网络GA继续步骤⑥，如此反复迭代直到系统达到稳定。
⑥ 子网络GB内的失效会同样影响网络间的相依边，网络间的相依边会发生步骤③中的相依边过载失效。
⑦ 相依边的过载失效会使得大量相依边被移除，进而导致子网络GA发生相依失效，故障又传播回子网络GA。
⑧ 系统的故障经过相依边的传递，再次回到子网络GA中，重复步骤②～⑦，直到系统达到稳定。
图4 展示了一个简易相依网络的级联失效过程，在相依网络的初始状态(如阶段1)下，先蓄意攻击子网络GA中 的节点A3， 则节点A3和它的连边(包括相连边和相依边)都失效，节点A3的失效导致节点A4脱 离最大连通子图，则节点A4发生非最大连通子图失效。相依边eA3B1的失效，使得相依边发生负载重分配，若邻近相依边eA5B1获得额外负载后其总负载超过容量，则发生过载失效，继续进行负载分配。相依边eA5B1的邻近相依边获得额外负载，若相依边的总负载小于容量，则停止负载分配。又因为子网络GB中 节点B1的 相依边都被删除，节点B1失效被移除，并且节点B1的 移除导致节点B4和B7脱离最大连通子图，故而同样发生节点失效，这些失效节点对应的连边也被移除。在阶段1 中失效结束后，网络的状态如图4b 所示，此时子网络GA中节点A7的 所有相依节点失效，故而导致节点A7发生相依失效。此时系统中节点不再发生失效，相依网络达到稳定而且整个系统的状态如图4c 所示。
图4 简易相依网络级联失效的过程
1.4 网络鲁棒性测量指标
攻击一定比例的节点后(若未特别说明，则是随机攻击子网络GA的节点)，考虑相依边负载的相依网络模型会发生级联失效。当网络级联失效达到稳定时，剩余最大连通子图中有效节点数与初始状态下子网络的节点总数的比例为鲁棒性指标，本文定义s为相依网络的鲁棒性测量指标，表示为：
式中，XA、XB分 别为子网络GA和 子网络GB中幸存最大连通子图中的有效节点；
NA、NB分别为子网络GA和 子网络GB中初始状态下节点的总数。显然s值越大，相依网络的有效节点越多，整个网络系统的鲁棒性就越好。
为了避免随机因素对整体仿真效果的影响，本文随机仿真生成SM个相依网络，并在相同的规则运行下得到一组鲁棒性测量指标分别为s1,s2,···,sSM。对这组数据取均值S=(s1+s2+···+sSM)/SM。本文仿真均取SM=2 000。
2.1 相依边负载分配策略对网络鲁棒性的影响
在相依边负载分配时，相依边的负载重分配策略对网络的抗毁性有一定程度的影响，本文采用4 种不同的负载重分配比例来对相依边过载失效进行分析。
1) 平均分配策略。当相依边eAiBj失效且存在邻近相依边时，将相依边的负载平均分配给其所有邻近相依边。则相依边eAiBj分 配给邻近相依边eAxBy的分配比例为：
式中，m表示子网络GA中 节点vAi上的相依边数；
n表示子网络GB中 节点vBj上的相依边数。
2) 负载分配策略。由于负载反映了相依边上实际信息量，故对所有邻近相依边负载进行归一化，取其相对大小来作为分配比例。按失效相依边的邻近相依边负载比例进行重新分配，相依边eAiBj分配给邻近相依边eAxBy的比例为：
式中，LAxBy为 邻近相依边eAxBy的 负载；
Γi表示子网络GB中 除节点vBj以外与节点vAi相连的节点集合；
Γj表示子网络GA中 除节点vAi以外与节点vBj相连的节点集合。其中LAiBb为求和内容，即求和的通项，表示eAiBb的 负载，eAiBb=(vAi,vBb)，求和的取值范围为vBb∈Γi，同理LAaBj具有类似意义。
3) 剩余容量分配策略。在级联失效的过程中，相依边所剩余的容量与其剩余可承受的负载成正比。所以相依边eAiBj分 配给邻近相依边eAxBy的比例为：
式中，LAxBy为 邻近相依边eAxBy的 负载；
CAxBy为邻近相依边eAxBy的 容量；
Γi表示子网络GB中除节点vBj以外与节点vAi相连的节点集合；
Γj表示子网络GA中 除节点vAi以外与节点vBj相连的节点集合。
4) 混合分配策略。将以上几种不同的重分配策略进行加权组合，则可得到混合分配策略。定义加权参数w1,w2,w3且w1+w2+w3=1，则分配比例为：
为研究相依边负载分配策略对网络鲁棒性的影响，将3 种经典人工网络作为相依网络的子网络，子网络间采用随机耦合。令子网络的平均度
图5 不同相依边的负载分配策略下鲁棒性的对比
2.2 网络组合形式对相依网络鲁棒性的影响
为考察不同网络组合对网络鲁棒性影响的差异性，设子网络的平均度
从图6 中可以看出，在考虑相依边负载的相依网络模型中，不同的组合网络的平均幸存节点比例都随着攻击不断下降，当破坏比例达到0.8 时，网络系统完全坍塌；
在 0 .2 ⩽q ⩽0.7时，网络的组合形式对系统抗毁性的区别最明显。WS-WS 网络的下降速度在这些组合网络中最慢，BA-BA 网络的鲁棒性最差，而ER-ER 网络的抗毁性相对较好，混合网络则介于两者之间，并且混合相依网络相较与单一网络组成的依赖网络差异性更小。通过对比分析，考虑相依边负载的相依网络模型在不同的组合方式下的鲁棒性与文献[26]的研究结论类似，混合网络的鲁棒性往往介于两者之间，而本文考虑相依边负载的相依网络在WS-WS 网络模式下抗毁性更加优异。
图6 不同网络组合下的相依网络鲁棒性的对比
2.3 子网络的平均度对网络鲁棒性的影响
为分析子网络的平均度
图7 不同子网络的平均度下的相依网络鲁棒性的对比
由图7 可知，随着子网络的平均度
当q⩾0.7时系统的坍塌速率明显增加。且无论哪种耦合方式，整体下降趋势相同，而同配耦合下相依网络的鲁棒性最好。故此，提高子网络的平均度能在一定程度上改善网络系统的抗毁性。
2.4 网络间的相依程度对相依系统鲁棒性的影响
分析网络间的相依程度对网络系统的影响，两个子网络都为BA 无标度网络，并以不同的耦合方式为研究对象，令子网络的平均度
从图8 可知，在3 种耦合模式下，网络系统的鲁棒性都随着攻击节点比例的增加而递减。且当相依冗余度K为4 时，不同的相依节点比例对网络系统鲁棒性具有差异性。在攻击比例q=0.4 时，不同的相依节点比例所导致的系统鲁棒性差异性开始显现，并随着攻击比例的增大，网络系统鲁棒性差异性越大。另外，相依节点比例越大，系统的鲁棒性越差，这与文献[19]中的结论相同，再次验证了相依节点比例对相依网络系统鲁棒性的影响。而且本文中相依节点比例的增加，增加了网络间信息沟通和传输的渠道，但这也利于相依边过载失效和相依失效的发生。
图8 不同相依节点比例对相依网络鲁棒性对比
从图9 可知，在F=1 下，相依冗余度对相依网络系统的鲁棒性影响较大。随着相依冗余度的增加，相依网络系统的鲁棒性越强，即相依冗余度能有效地增强系统抵抗级联失效的抗毁性，原因在于每个节点的相依边数的增加有利于缓解相依失效和相依边过载失效，并且单个相依节点增加相依边也有助于分摊负载重分配时的额外负载，并减小相依失效的概率。此外随着相依冗余度K的增加，K对相依网络鲁棒性的影响在逐步减小。这与文献[19]中的结论相近，但本文考虑了相依边的负载重分配，所以系统鲁棒性的下降速率相较于文献[19]更迅速，下降比例也更大。综上所述，减少相依节点比例F，提高相依冗余度K能有效降低相依网络的崩溃比例。
图9 不同相依冗余度对相依网络鲁棒性对比
2.5 不同边攻击方式下相依网络的鲁棒性
本节在初始失效时分别攻击一定比例的相连边和相依边，并通过系统处于稳定状态时鲁棒性指标的大小来判断相连边和相依边对相依网络的影响。在对系统进行蓄意攻击时，先对相连边进行加权处理，相连边的权重为连接节点度值的乘积，即weij=ki×kj。初始状态时将相连边按权值降序排列，相依边按初始负载的大小降序排列，取前面一定比例的边进行攻击。若子网络中节点的相连边或相依边全都失效，则该节点失效。令系统的参数与负载重分配策略同上，子网络模型选择无标度网络和地铁公交网络，并通过上文中3 种不同的耦合方式分别进行连接。在初始状态下，采用不用的攻击方式分别攻击相连边和相依边，分析系统网络的鲁棒性。仿真结果如图10 所示。
由图10 可知，蓄意攻击比随机攻击对相依网络鲁棒性的影响更大，蓄意攻击相依边时系统网络的有效节点比例下降最快。因为攻击负载较大的相依边更容易导致相依边的过载失效和相依失效。且无论网络间的耦合采用何种方式，攻击相依边比攻击相连边对相依网络的失效风险更高。另外相比于其他耦合方式，相依网络在同配耦合下对于蓄意攻击产生的故障效果最明显，这是由于同配耦合时子网络间度值较大的节点相连接，使得失效的传播途径和故障范围更加广泛。此外，对真实地铁公交网络的仿真结果，也同样反映了相依边对网络系统的重要性，系统的整体下降趋势与无标度相依网络相似。相较于无标度网络组成的相依系统，地铁公交网络的失效速率和故障比例更大，原因在于地铁公交相依网络的子网络平均度和节点的相依冗余度较小，无法有效地抑制级联失效的传播。同时在地铁公交网络中子网络的节点总数不相等，相依节点的比例FAFB，公交网络中存在较多没有相依边的节点，这就使得在攻击相依边时，会幸存大量没有相依边的节点，所以在攻击相依边的比例达到100%时，系统依然存在一些幸存节点。
图10 不同边攻击方式下相依网络鲁棒性对比
在现实中不同网络之间信息或流量的传递与运输往往具有明显的负载效应，本文提出的考虑相依边负载的相依网络级联失效模型综合分析了此类现象。文中新定义了邻近相依边集，详细解释了相依边失效时负载重分配的原则。并通过人工网络和真实网络对这一现象进行说明，考虑相依边的负载会增加级联失效的复杂性，但同时这也更符合实际网络的故障状态，并探讨了耦合程度、子网络平均度和攻击方式等因素对考虑相依边负载的相依网络鲁棒性的影响。仿真结果表明了增强网络间的相互依赖比例会使得系统变得脆弱，但较大的相依冗余度能有效地遏制失效造成的破坏范围；
提高子网络的平均度能显著地抵御网络内的非最大连通子图失效；
相较于相连边，攻击相依边会加速整个网络系统的坍塌。这些研究对优化相依网络系统的鲁棒性提供了参考，也对现实中不同网络之间信息和流量的传递现象做出了一定的分析和解释。然而，这些研究都是在无向网络的基础上进行的，考虑相依边负载的级联失效模型对有向网络的影响有待进一步解决；
此外，在对网络系统进行级联失效预防和恢复的过程中，文中所建立的失效模型如何增加恢复与预防的复杂性和困难程度是下一步研究的重点。
