基于节点重要度动态评估的复杂网络级联失效分析

姜敏勤, 石小晶, 杨钰, 张正勇

(南京财经大学管理科学与工程学院, 南京 210023)

复杂系统可以抽象成各种与现实生活密切相关的复杂网络,如社交网络[1]、航空网络[2]、交通网络[3]及电力网络[4]等。随着复杂网络研究的不断深入,网络的级联失效行为作为复杂网络研究领域的重要分支,学者对其的探索从未间断。网络的级联失效是指当复杂网络中的节点失效后,需根据相邻节点间的耦合关系对失效节点的负载进行重分配,重分配过程可能会导致邻居节点的负载超过自身的容量,从而发生邻居节点连续失效的连锁反应,导致网络的部分瘫痪或是全面崩溃[5]。级联失效现象让现代社会依赖的各类网络系统面临严峻的挑战,如2019年新冠肺炎疫情在中国武汉爆发,并迅速蔓延至全国各地,引发一系列的连锁故障,尤其是其物流网络接近瘫痪,对各行各业都造成了巨大的冲击[6]。因此,网络的稳定性和抗毁性问题已逐渐成为一个亟待解决且极具挑战性的前沿课题。为有效预防和控制网络的级联失效现象,增强网络的鲁棒性,研究级联失效具有极强的现实意义。

已有学者对复杂网络的级联失效行为进行了诸多探索,研究主要集中在级联失效的建模及级联抗毁性研究两个方面。Motter等[7]首次提出了经典的线性容量负载模型来研究网络的级联失效,并指出具有高异质性负载分布的网络在负载较高的节点受到攻击时,容易引发级联故障。Crucitti等[8]提出一个基于网络流量动态重分配的级联失效模型,指出一个负载最大的节点失效,便足以击垮整个网络。而Kim等[9]的研究发现网络中容量较小的节点却拥有较大的剩余容量,即真实网络中的负载和容量并非是一种简单的线性关系。基于此,窦炳琳等[10]对网络的经典负载容量模型做出改进,以有效地抵御网络的级联失效。郝羽成等[11]基于节点过载状态构建了一种级联失效模型,指出节点负载的混合分配策略能够有效控制级联失效的影响。Ma等[12]提出一种新级联失效模型,该模型基于度中心性和接近中心性来定义任意两节点之间的连接负载,以增强无标度网络的鲁棒性。刘凤增等[13]给出了一种考虑资源限制的节点负载分配方式,研究级联失效下非对称依赖网络的鲁棒性,指出根据度值分配节点容量的网络鲁棒性更强。谢本凯等[14]建立了一种考虑节点状态的民航网络容量负载模型,指出应注重增强网络关键节点的鲁棒性,以保证网络的安全运行。Feng等[15]提出一种匹配级联失效模型来同时分析节点和边的潜在过载,研究表明在无标度网络中,一个关键节点的故障可能会导致整个网络的崩溃。高洁等[16]提出一种基于非线性容量负载模型,研究具有电气特征的加权电网和只具有拓扑结构的无权电网,分别面对网络级联故障时的抗毁性情况。

纵观已有研究,多侧重于探讨如何定义网络节点的初始负载和容量,以及容量的分配策略等方面,鲜有研究关注级联失效过程中网络节点重要性的度量,普遍认为度值较高的节点更为重要,在级联失效仿真过程中,较多采用度值攻击策略,即优先攻击度值较高的节点,但根据单一指标评估节点的重要度有一定的局限性。而现有的其他节点重要性度量方法[17-19],虽已取得诸多进展,但基本还停留在网络的静态层面,鲜有报道研究级联失效过程中网络结构随节点失效呈现出变化的动态特性,且重要度不同的节点受到攻击会对网络抗毁性大小的变化存在不同程度的影响,故尚未深刻揭示节点重要性动态规律。因此,现提出一种基于网络结构实时状态演化的节点重要度评估方法,以提高重要节点评估方法的科学性及后续级联失效仿真分析的可靠性,在此基础上引入两个容量参数,分析网络节点负载与容量间的非线性行为,并提出一种新的节点攻击策略,以保证每次仿真实验攻击的节点都是当下网络中最重要的节点,对网络抵制级联失效的抗毁性进行深入研究。

1 复杂网络节点重要度评估方法

复杂网络中的重要节点对分析网络的结构和功能,增强网络鲁棒性和稳定性至关重要。为挖掘网络中的重要节点,现提出一种基于灰色关联法和多准则妥协解排序法(VIKOR),综合考虑节点的度中心性、介数中心性和接近中心性的重要节点评估模型。

(1)构建评价决策矩阵。根据文献[20]计算节点的度中心性指标、介数中心性指标和接近中心性指标值,构建网络节点重要性评估的决策矩阵X,即

(1)

式(1)中:Xij为节点i的第j个中心性指标;n为节点数;m为中心性指标个数。

(2)标准化决策矩阵。由于中心性准则之间存在维度差异,需对矩阵进行标准化处理[21],处理后的标准化决策矩阵为D=(dij)n×m,计算公式为

(2)

(3)计算各中心性指标的权重。采用客观赋权法中的熵权法,利用中心性准则之间的关联程度和提供的信息来确定权重wj,计算公式为

(3)

式(3)中:Ej为中心性准则j的信息熵。

(4)确定正负理想解。根据标准化决策矩阵,确定正理想解d+和负理想解d-,计算公式为

(4)

(5)

式中:J为效益型指标;O为成本型指标。

(5)采用欧氏距离计算各节点的初始群体效用值Si和个别遗憾值Ri,公式为

(6)

(7)

(8)

(9)

式中:i=1,2,…,m;j=1,2,…,n;ρ为分辨系数,一般ρ=0.5。

(10)

(11)

(12)

(13)

(9)确定各节点的综合评估值Qi,公式为

(14)

2 级联失效模型

2.1 初始负载

初始负载反映了节点在某一时刻处理信息的能力[22]。已有的研究往往以度值[23]或介数值[24]来定义节点的初始负载,但网络节点的有效运行也依赖于其他邻居节点[25],故设置节点的初始负载为

(15)

式(15)中:Fi为节点i的初始负载;ki为节点i的度值;Γi为节点i的邻居节点的集合;α为调节初始负载强度的参数,α>0。

2.2 节点容量

一个节点的容量是其能承受的最大负载。根据Motter-Lai模型,一个节点的容量与该节点的初始负载呈线性关系,但在真实的网络中,容量和负载表现出一种非线性关系,为保证节点容量的模型更接近真实的复杂系统,定义节点容量为

Ci=Fi+θFiβ

(16)

式(16)中:Fi为节点i的初始负载;Ci为节点i的最大容量;θ和β为控制节点容量的容量参数,且有θ>0,β>0 ;当β=0时,该模型转化为经典的Motter-Lai模型。

2.3 负载重分配模型

当节点的负载超过了节点自身的最大容量时,则该节点会发生故障,从而引起负载的重分配。本文中采取与节点的初始负载成比例的重分配方式将故障节点的负载分配给邻居节点,表达式为

(17)

式(17)中:ΔFj为邻居节点j增加的负载量;wj为负载的分配比例;Γi为节点i的邻居节点的集合。

此时,邻居节点j的实时负载为

Fj(t)=Fj(t-1)+ΔFj

(18)

式(18)中:Fj(t)为节点j的t时刻的实时负载;Fj(t-1)为t-1时刻节点i没有失效时的实时负载。若Fj(t)>Cj,节点j也会失效,则进行失效节点j的二次负载重分配,直至相邻节点所分配到的负载与初始负载之和满足其最大容量限制。若Fj(t)≤Cj,则级联失效中断。

2.4 抗毁性测度指标

最大连通子图指网络受到攻击,被分为若干个子网络后的最大连通分量,而最大连通子图比例指网络受到攻击后,网络最大连通子图的节点数与初始网络节点数量的比值[26]。本文中采用最大连通子图比例来量化复杂网络的抗毁性,计算公式为

(19)

式(19)中:S为最大连通子图的比例,S越大,表示网络的鲁棒性越强[27];N′为最大连通子图所包含的节点数;N为网络总节点数。

上述级联失效算法流程如图1所示。

3 仿真实验与分析

为验证所提方法的有效性和可靠性,选择以《成渝地区城际铁路建设规划 (2015—2020年)》的数据为例,绘制其网络拓扑图如图2所示,进行仿真分析。文献[28]表明,成渝地区铁路网络具有小世界特性和无标度特性,且与京津翼和西北地区的铁路网络相比,具有更为明显的复杂网络特性。

图2 成渝地区铁路网络拓扑图Fig.2 Topological map of intercity railway network in the Chengdu-Chongqing region

3.1 静态节点重要性评估

根据式(2)～式(14)计算出节点重要性指标数值如表1所示,由于网络节点数较多,只展示重要度排名前20的节点。

表1 静态评估下节点重要度排名前20的节点排序Table 1 Ranking of the top 20 nodes in terms of node importance under static evaluation

由表1可以看出,节点41所在的城市——广安是成渝地区铁路网络中最关键的节点,其虽然度值只有3,但是网络中大部分节点间的最短路径都会途径该节点,且广安的邻居城市重庆和南充的重要度排名均相对靠前,进一步强化了广安在整个铁路网络中的重要性,使其成为网络中控制信息传输的关键位置。从铁路运输的现实意义来看,若广安丧失正常的运转功能,会使得部分城市间的铁路运输距离大大增加,从而导致铁路网络运输的效率大幅下降。节点55(重庆)、节点27(成都)、节点29(遂宁)、节点40(合川)和节点16(南充)在网络中的各项中心性指标均相对较大,位于网络中心位置,连接多个节点城市,具有重要的枢纽作用。节点14(中江)、节点73(自贡)、节点70(乐山)、节点45(浦江)、节点19(达州)、节点56(永川)、节点8(德阳)虽靠近网络的边缘位置,但是其重要度排名依旧靠前,这是由于这类节点坐落于成渝地区与省会中心城市(重庆和成都)的连接处,其介数中心性、度中心性和接近中心性指标值都相对较高,若此类节点发生故障,则会在一定程度上影响边缘城市与中心城区的联系。

采用随机攻击、重要度攻击、度值攻击以及介数攻击4种攻击策略,攻击成渝地区铁路交通网络,根据最大连通子图比例的变化情况反映网络的受损程度,以初步验证节点重要度评估模型的有效性。随机攻击是通过python编程随机生成节点的序列,依次对网络进行攻击;蓄意攻击则是根据前文方法得到的节点排序,依次对网络进行攻击;度值攻击和介数攻击为按节点的度中心性和介数中心性从大到小的顺序排序,依次对网络进行攻击。最大连通子图的变化情况如图3所示。

图3 静态攻击下最大连通子图比例变化情况Fig.3 Changes in the proportion of the maximum connected subgraph under static attack

从图3可以看出,网络受到随机攻击时,最大连通子图比例下降的速度较为缓慢,累计攻击20个节点,网络的最大连通子图比例才降至70.7%。表明小范围内的节点失效并不会对网络的整体连通性造成较大的影响,但当移除的节点数目达到一定规模时,也会使网络剩余的节点变成孤点。网络在度值攻击下的静态抗毁性最差,网络最大连通子图比例下降最快,累计攻击15个节点时,最大连通子图比例下降至18.7%,说明网络节点的度中心性最能代表节点在静态网络拓扑结构中的重要程度。在介数攻击下,累计攻击18个节点时,网络的最大连通子图的比例才降至18.7%,累计攻击24个节点时,网络接近崩溃。在重要度攻击下,网络表现的静态抗毁性与度值攻击下的大致相同,当受攻击的节点数少于12个时,最大连通子图的比例并没有明显的下降,这是由于节点重要度排名前12的节点均具有较大的度值,即周围的邻居节点比较密集,节点失效后,可以找到可替代路径疏通网络,所以并不会在很大程度上降低网络的连通性。当累计攻击12个节点时,最大连通子图比例骤降到54.7%,网络连通性受到较大的影响,当被攻击的节点数量达到15个时,最大连通子图比例急剧下降到20%,大大降低了网络的连通度和可达性,这是由于受到攻击的节点是发挥连通网络作用的关键节点,这些节点的故障导致网络受到重创被分裂成多个子网络,无法实现跨城区的运输。

3.2 动态节点重要性评估

考虑网络静态特性下的节点重要性评估已取得了诸多进展[29],但实际网络的结构会随节点所受的攻击而发生改变,根据初始网络数据评估出的重要节点,当下可能已经不再重要。为提高方法识别的精确性及后续级联失效仿真分析的可靠性,应每当一个节点受到攻击失效后,就重新计算网络节点的重要度,以保证每次攻击的节点都应是当前网络最重要的节点,采用上述动态评估方法得到成渝铁路网络中,节点重要度排名前20的节点如表2所示。

由表2可以看出,动态评估模式下得到的节点重要度排名与根据网络初始状态得到的节点重要度排名有较大的出入,由于铁路网络的初始拓扑结构相同,故节点41(广安)无论是在网络的静态还是动态特性下,都是成渝铁路网络中最关键的节点,节点41(广安)失效后,在更新后的网络拓扑结构中,节点55所在的城市——重庆成为当下网络下最关键的节点,重要性仅次于节点41,这与静态评估模式下的排名相同。但后续的节点重要度的排名变化较大,节点27(成都)在动态评估模式下,其重要性排名从第3降至第7,而节点52(内江)的重要度则从第18升至第4,在静态评估下重要度排名前20的节点中,节点14(中江),节点28(大英),节点45(浦江),节点44(长寿),节点56(永川)均未进入动态评估模式下节点重要度排名前20中,说明这些站点在成渝铁路网络的关键站点受到攻击后,已经不再是网络的关键节点,可见,网络节点的重要度是伴随网络拓扑结构的变化而发生改变的,进一步验证了进行网络节点重要度动态评估的必要性。

表2 动态评估下节点重要度排名前20的节点排序Table 2 Ranking of the top 20 nodes in terms of node importance under dynamic evaluation

为对比分析,采用随机攻击、重要度攻击、度值攻击以及介数攻击4种攻击策略,其中重要度攻击、度值攻击和介数攻击均为根据网络的实时状态计算得到,累计攻击20个节点。得到网络最大连通子图比例随攻击节点数目的变化情况如图4所示。

图4 动态攻击下最大连通子图比例变化Fig.4 Maximum connected subgraph scale change under dynamic attack

如图4所示,在不考虑级联失效情况下,从网络的连通性而言,网络面对随机攻击时,网络依旧表现出较好的鲁棒性,但当面临蓄意攻击时,则表现出更为明显的脆弱性。其中,根据介数攻击网络节点时,网络下降的趋势最快,累计攻击5个节点,最大连通子图的比例便下降至48%。从度值攻击策略来看,累计攻击9个节点时,最大连通子图比例值才降至46.7%,累计攻击19个节点时,网络接近崩溃。在重要度攻击策略下,其最大连通子图比例值的下降趋势与介数攻击策略下的非常相似,当6个网络节点受到攻击时,网络的最大连通子图比例骤降至46.7%,被攻击的节点数量达到11个时,最大连通子图比例骤降至21%,此时网络的连通性和可达性已经受到了严重影响。与度值攻击策略相比较,重要度攻击策略可以更快速地使网络崩溃,这表明采用动态的节点重要度计算方法,可以有效提高关键节点识别的精确性。

3.3 基于动态节点重要度评估的级联失效分析

考虑级联失效情况下,设置参数α=0.2,β=0.5,θ=0.8。同样采用随机攻击、重要度攻击、度值攻击以及介数攻击4种攻击策略,得到最大连通子图比例的变化情况如图5所示。可以看出,重要节点在网络中的作用相较于非级联失效情形更为突出。网络面对随机攻击时,最大连通子图下降的趋势较为平缓,但累计攻击一定数量的节点后,则会出现级联失效的现象,可能是因为攻击到网络中的关键节点,导致网络中大部分剩余节点变成孤点,从而引起最大连通子图比例值的急剧下降。网络面对蓄意攻击下,当攻击节点达到5个时,介数攻击策略下的最大连通子图的比例迅速下降至47.3%;当失效节点达到8个时,度值攻击策略下的最大连通子图比例骤降至2.63%;攻击9个节点时,度值攻击策略和介数攻击策略下的最大连通子图比例值均下降到0,说明每一轮攻击后,度值和介数较大的节点都有可能是网络的关键节点,这些关键节点的失效引发了多轮负载重新分配过程,这也进一步验证,节点的重要度评估不能只关注网络单一属性指标,应考虑多个指标进行综合评估。网络面对重要度攻击策略时,最大连通子图比例变化最为明显,仅攻击一个节点时,对网络的连通性没有造成太大影响,但累计攻击2个节点后,网络便迅速崩溃,最大连通子图比例骤降至0。攻击的前2个节点分别为节点41和节点55,就第2个受攻击的节点55而言,其度值最大,即周围的邻居节点较多,但其大部分邻居节点的度值较小,且部分邻居节点之间又互为邻居节点,根据级联失效的初始负载及负载分配策略的定义来看,由于节点55的初始负载较大,且攻击的第一个节点41也是节点55的邻居节点,节点41失效之后,节点55又承接了来自失效节点41分配的额外负载,这就导致该节点受到攻击之后,其周围的邻居受到节点最大容量的限制,无法承接来自节点55分配的高额负载,从而引发级联故障,使最大连通子图比例值突变为0。

图5 级联失效下最大连通子图比例变化Fig.5 Proportional change of maximum connected subgraph under cascade failure

3.4 模型参数对网络级联失效鲁棒性的影响

级联失效模型中包含α、θ和β共3个参数,采用重要度攻击策略,探究参数对级联失效下网络鲁棒性的影响。参数α用于控制节点初始负载的强度。设置β=0.9,θ=0.8,令α∈[0.1,0.9],得到最大连通子图比例的变化情况如图6所示。当α∈[0.1,0.3]时,最大连通子图比例曲线没有明显的变化趋势,但网络表现出一定的脆弱性,且α=0.2时,网络的抗毁性最差,这说明当参数α∈[0.1,0.3]时,可能存在一个边界值,导致网络在抵制级联失效时表现出一定的脆弱性。当α≥0.4时,最大联通子图比例曲线迅速上移,此时网络具有较强的抗毁性,且趋于稳定,说明当α超过某一阈值时,最大连通子图比例对于网络级联失效所带来的影响反应减缓,能在一定程度上提高网络的抗毁性。

图6 不同α下的最大连图子图比例变化情况Fig.6 Variation of the proportion of maximum contiguous subgraphs for different values of α

β和θ都是用于控制节点最大容量的容量参数,为探究容量参数对网络抵御级联失效的抗毁性的影响,令α=0.4,β=0.9,得到参数θ不同取值对网络最大连图子图比例的演化情况如图7所示。可以看出,随着θ取值的增大,网络最大联通子图比例曲线逐渐右移,当θ≥0.7时,级联失效的临界值较大,此时网络有较好的抗毁性,网络受到攻击也不会导致最大连通子图比例曲线有较大的波动。

令α=0.4,θ=0.8,在实验中,当0<β≤0.3时,由于节点的容量较小,导致网络的抗毁性较差,仅攻击一个重要节点,网络便迅速崩溃,且最大连通子图比例曲线均与β=0.4时相重合,故取β∈[0.4,1.2],得到参数β不同取值导致的网络最大连图子图比例变化情况如图8所示。可以看出,网络最大连通子图比例变化趋势与θ导致的最大连图子图比例变化情况相似,都是随着参数的增大,网络的抗毁性也逐渐增强,β≥0.9时,网络发生级联失效的概率较低,节点的失效对网络造成的影响也较小,网络的级联失效抗毁性就会逐渐增强,且趋于稳定。

图7 不同θ下的最大连图子图比例变化情况Fig.7 Variation of the proportion of maximum contiguous subgraphs for different values of θ

图8 不同β下的最大连图子图比例变化情况Fig.8 Variation of the proportion of maximum contiguous subgraphs with different β

综上,可以发现,容忍系数的增大可以提高网络抵御级联失效的抗毁性,且当容忍系数达到一定值时,网络的抗毁性趋于稳定,级联失效也不会对网络的连通性造成严重的影响,但再继续提高容忍参数对网络抗毁性的提高作用不大。其次,当容量系数取较高的值时,网络的抗毁性能便会趋于稳定,这是因为根据重要度策略攻击的节点对网络的连通性起着关键作用,这类节点最大容量的设置应使其能够满足节点失效后负载流的传播,这样网络才能具有较强的抗毁性。此外,本文仿真分析选取的网络具有显著的无标度特性,即只有少量的节点拥有较大的度值,级联失效模型的初始负载是根据节点及邻居节点的度值所定义,且采取了与节点的初始负载成比例的重分配策略,故当网络节点受到攻击的过程发生级联失效时,会有较多的负载流经度值较小的节点,而这类节点的初始负载和容量一般都相对较小,无法承接来自失效节点的高额负载,从而加剧了对网络连通性和可达性的破坏,需要设置较大的容量参数获取更大的节点容量,以增强网络抵御级联失效的能力。

分析可知:成渝铁路网络在面对随机攻击时表现出较强的抗毁性,而面对重要度攻击时,则表现出一定的脆弱性,在关键节点级联失效情况下,其脆弱性更为显著,随着关键节点的失效,网络性能也急剧下降,失效节点达到一定数量时,网络会被分裂成多个孤立的子网络,网络彻底瘫痪,因此,在制定铁路网络相关应急策略时,应尽量避免级联故障现象的发生,应做好铁路网络关键站点的防护措施,在考虑经济效益的基础上,适当提高节点的容量,增加关键节点其他节点间的耦合关系,以增强节点在出现负载过载情况时向其他站点的进行负载输送的能力。此外,发生级联失效现象后,应严格控制负载向度值较少的节点转移的流量,以防止发生承接负载的节点没有足够的可替代路径疏通路径来继续分配负载,造成更大规模的失效情况。

4 结论

提出了基于灰色关联法和VIKOR法的复杂网络节点重要度评估模型,并应用于成渝地区铁路交通网络,能有效识别出网络中的重要节点。考虑到网络节点受到攻击的同时,网络的结构也会随之改变,为更精准的识别出网络实时的关键节点,对节点重要度评估过程做出改进,选择根据网络的动态演化来评估节点的重要性,即每攻击一个节点,便重新计算当前网络的节点重要度,实验结果表明,采用动态的节点重要度评估过程可以有效提高识别的精确性。在此基础上,采用一种更符合真实网络非线性容量负载的复杂网络级联失效模型进行仿真分析,仿真结果进一步验证了节点重要度动态评估模型的有效性。同时讨论了初始负载控制参数及容量控制参数在重要度攻击策略下对网络级联失效的影响,实验得到以下结论。

(1)广安和重庆是成渝铁路网络中最关键的节点;不考虑级联失效情况时,节点的度中心性最能表示节点在静态网络下的重要性,而在动态网络拓扑结构中,介数最能代表网络节点的重要程度;考虑级联失效情况下,综合性的动态评估模型更能代表节点的重要性。

(2)在以节点和邻居节点的度值定义节点的初始负载方式下,当初始负载控制参数α∈[0.1,0.3]时,网络在抵制级联失效时表现出一定的脆弱性;当α≥0.4时,随着α的增大,网络的抗毁性也逐渐增强,但当α超过某一阈值时,网络的鲁棒性趋于稳定,继续提高α,对网络的增强网络鲁棒性没有明显效果。

(3)网络的抗毁性与容量参数取值呈正相关,增大网络的容量参数可以增加网络节点的容量,减小级联失效行为对网络的破坏程度;受网络拓扑结构和攻击策略的影响,取较大的容量参数时,网络具备较强的的抗毁性。

(4)由于选取的成渝地区铁路网络节点数量相对较少,在分析网络面对级联失效的鲁棒性时,网络容易发生多级级联失效而迅速崩溃,导致一些结果的呈现不太明显,因此,可进一步将本文模型应用于大型网络,以更好地反映网络面对级联失效时的抗毁性情况。