具有弱依赖组的复杂网络上的级联失效*

潘倩倩 刘润然 贾春晓

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

1 引言

真实世界中的许多复杂系统都可以抽象成复杂网络,如常见的交通网络[1-4]、电力网络[5]、社交网络[6]、疾病传播网络[7,8]和生物网络[9,10]等.在复杂系统鲁棒性的研究中,人们常常借助于复杂网络级联失效模型对复杂系统的崩溃过程进行建模和研究,节点的失效不仅会对网络整体的连通性造成影响,也可能会因节点之间的依赖关系而引起失效在网络中蔓延.最初复杂网络鲁棒性的研究是将两种效应分开进行的,即针对网络节点之间的连接关系来探讨网络在失去部分连接或节点之后的连通性[11-13],以及节点间的耦合或依赖性所引起的失效节点的雪崩或级联效应[14].对于前者,人们借助于渗流模型发现,随机网络发生渗流相变的临界点与网络平均度呈反比关系[15];无标度网络具备“鲁棒性和脆弱性共存”的特征[16-18],即对随机故障的鲁棒性较强,但面对蓄意攻击时则显得十分脆弱;对于小世界网络,“捷径”使得网络的鲁棒性增强[19],但也更容易在蓄意攻击下破碎[20].对于复杂网络级联失效的研究,如何对节点之间的耦合和依赖进行建模是一个核心问题.研究人员考虑了真实复杂系统的特征,主要考虑了动态负载分配、局部依赖和依赖组的引入等几个方案.

1) 动态负载分配[21-27].当网络中部分节点失效后,网络节点之间最短路径的分布发生较大的变化,网络中信息或能量的流动路径就会重新分配,从而引起部分节点的运行效率下降[21],甚至过载失效[27].在这类模型中,一个负载较小节点的失效可能不会引起负载失衡并诱发较大范围的过载故障;而失效节点的负载较大时,这些节点的失效可能会显著影响其他节点的负载,并引发一系列大范围的过载故障[23,27].为了探讨级联失效的产生条件并为级联失效的防御和控制提供思路和策略,节点失效后荷载的分配方案对网络级联失效动力学的影响也受到广泛关注,如随机荷载再分配机制[28]、基于边权重的再分配策略[29,30]、供需网络中的供应策略[31]等.除了流量分配机制外,网络结构调整策略[32]、攻击策略[33]、网络中流量的涨落[34]、网络的结构特征[35]等因素对于级联失效的影响也受到广泛的关注.

2)局部依赖.Watts 模型研究了邻居中相反状态节点比例对节点状态的影响,发现了复杂网络发生级联失效的临界判据[36,37].此外,考虑到网络高度值互连部分节点(k核)所组成结构的重要性,Dorogovtsev 等[38]提出了k核渗流模型,该模型将通过一个反复迭代的剪枝过程获得的最小度为k的节点所形成的连通子图视为k核.度分布的二阶矩有限时,随着初始删除节点的增加,k核巨分支在某一临界点会突然消失,表现为不连续的混合相变现象.如果度分布的第二阶矩发散,则网络包含一个无限序列的k核,这些k核对随机攻击具有很强的鲁棒性.类似地,靴攀渗流模型考虑了失效邻居的数量对节点状态的影响,当节点失效邻居数达到某个阈值时该节点就会失效,研究发现,在不同的度分布情形下,网络中也会出现一阶不连续相变和连续相变的现象[39].

3)依赖组的引入.上述两种模型中节点都是通过相互邻接关系进行状态传递的,但现实网络中不相邻的节点也可能存在隐含的相互影响.Parshani等[40]考虑到不相邻节点之间也可能存在依赖性,于是提出了依赖组概念来描述复杂网络中节点的隐含依赖性,这种依赖组的存在导致网络能够发生级联失效并导致网络更加脆弱,如在依赖组的密度较高或依赖组规模较大时网络会在遭受攻击时以一阶不连续相变的方式发生突然性的崩溃[41],同时依赖组的规模和分布[41]以及依赖规则[42-44]等特征的变化对网络鲁棒性和级联失效有着不同程度的影响.

在关于依赖组的研究中,大多数模型基于一个简单的假设:一个节点的失效可以直接导致其依赖节点的全部失效,这种“节点对节点”的“强依赖”的假设导致了网络在遭受攻击时极为脆弱,这一结果不但与现实中某些观测不符,也不能充分描述部分复杂系统节点之间的依赖关系[45,46].在现实网络中,一个节点的失效可能对其依赖节点的一部分功能造成影响,而不是导致其完全失效[47,48].如金融系统中,所属同一个投资者的公司之间相互依赖,由于风险分散,一家公司的倒闭不太可能直接导致投资者的其他公司全部破产,而现实的情况是,其余公司可能会因现金流的减少而收缩自己的业务.因此与以往模型所描述的“节点对节点”依赖模式不同,在一些普遍场景下系统节点之间的依赖关系体现在“节点对边”的相互作用上,即一个节点失效后,依赖组内的其余节点会因受到冲击而损失部分连接.这种描述“节点对边”的相互作用机制可以描述更为一般化的场景,如属于同一个依赖组的若干节点,当其中一个节点失效的时候,不会引起其余全部或部分节点立即失效,而是失效节点给剩余依赖节点带来一定程度的冲击和影响.

本文引入了“弱依赖组”概念,通过一个可调参数来控制同一依赖组内节点的相互依赖强度并研究依赖组的大小、分布和网络度分布对网络的级联失效的影响.通过理论研究和数值模拟的结果,发现改变依赖组的参数时,网络能够发生连续和不连续的两种渗流相变,且无标度网络在渗流过程中可能会出现双重相变现象.

2 具有弱依赖组的网络级联失效模型

考虑一个由N个节点通过一些连接边所组成的网络,节点的连接度服从概率分布函数P(k)[7],同时网络中的每一个节点都随机地与其他节点形成一个包含M个节点的依赖组,组内的节点互相依赖.当依赖组中一个节点失效时,其余节点会受到一定程度的冲击,影响强度由解耦系数α控制,即其余每个节点的每条边都以α的概率保留下来,而以 1-α的概率被删除.参数α在描述失效节点对其余依赖节点所造成破坏性的同时,也描述了一种“节点对边”的作用机理,在描述依赖节点之间的相互作用上更具有一般性的意义,当α →1 时,依赖组内节点的耦合强度最弱,一个节点的失效不能对组内其余节点造成任何影响,此时模型与普通的座渗流等价;而当α →0 时,依赖组内节点的耦合强度最强,一个节点的失效就能造成组内所有节点全部失效,此时模型与文献[41]中强依赖组的模型等价.通过调整模型参数α可以研究不同耦合强度对网络级联失效动力学和鲁棒性的影响[49,50].

网络级联失效通过随机攻击网络中比例为1—p的节点来触发,这些被攻击节点及其连接被从网络中全部删除,进而导致网络发生破碎.在网络中,能够连接到巨分支的节点视为功能节点,其他节点视为失效节点.由于弱依赖组内节点之间存在一定程度的依赖性,网络中一个节点的失效会造成两种影响:1)组外影响,节点失效会引起网络破碎,进而导致组外部分节点不能通过该节点连接到网络巨分支而失效;2)组内影响,失效节点所在的依赖组内的其余节点会受到损害,其每一条连接边都以1 —α的概率被删除,即以α的概率被保留.当一个节点失效后,组外影响导致失效能够跨依赖组传播,从而使失效扩展到更大的范围,而组内影响导致组内的其余节点的边受到破坏,从而引起组内更多节点失效.在这两种影响的交替作用下,网络上的级联失效就会发生.我们将这两种扩散过程称为“组间级联失效”和“组内级联失效”.当这两个过程停止时,网络不会产生新的失效节点而发生进一步的破碎,所有依赖组内也不会有新的连接边被删除,网络即达到稳态.本文用网络稳态巨分支的相对大小S来衡量网络的完整性,随着初始保留节点比例p的降低,网络巨分支的大小S会以二阶连续相变或一阶不连续相变的方式在一个临界点或处降低至零,二阶相变的临界点或一阶相变的临界点通常用于度量网络的鲁棒性[15,51,52].

图1 为具有弱依赖组的网络的级联失效示意图.图中虚线椭圆内的节点形成一个依赖组,实线表示网络内功能正常的连接边,点状虚线表示被删除的连接边;功能正常的节点用绿色标记,失效节点用红色标记,黄色节点表示功能正常但受到损坏的节点.图1 中(a)表示的是一个未受到攻击的网络;(b)网络中存在一个最初被删除的节点2;(c)由于节点2 被删除,其所有连接边失效;(d)由于节点1 与网络巨分支之间的连接边被移除,导致节点1 脱离网络巨分支而失效;(e)由于节点7 和节点1 属于同一个弱依赖组,相互依赖,故节点1的失效会导致节点7 受损;(f)节点7 受到了一定的冲击,节点7 与节点6 之间的连接边失效;(g)因节点7 与节点6 之间的连接边失效,导致节点6 脱离网络巨分支,发生故障;(h)由于处在同一弱依赖组,节点5,4 受节点6 失效的影响而受损;(i)节点5 受损导致节点3 和节点5 之间的连接边失效,并且网络达到了最终的稳定状态.

图1 具有弱依赖组的网络的级联失效示意图Fig.1.Schematic diagram of the cascading process in a network with weak interdependency groups.

3 理 论

用概率生成函数理论来对模型求解.在求解过程中,采用度分布的生成函数来生成网络的度分布,即一个随机节点度值为k的概率是P(k);类似地,采用余度分布生成函数来生成一条随机边到达一个度值为k的节点的概率,即排除这条随机边之外到达节点的余度为k—1的概率[53].在这两个生成函数中,表示网络的平均度.为了求解稳态时网络巨分支的规模,定义R为网络中任意一条随机边能够连接到巨分支的概率.假定在网络中随机挑选一条边后,沿着这条边的任意一端可到达一个度值为k的节点i,若该节点所属依赖组内有t个失效节点,他的每条边能够保留下来的概率为αt.由于任意一个节点度值k服从概率分布P(k),节点i的任意一条随机边能够连到巨分支的概率分布遵循根据生成函数G1(x) 并考虑k的概率分布,可将一条随机边连接到巨分支的概率简写为αt[1-G1(1-αtR)][54,55].如果将任意一个节点所在的依赖组内失效节点数t所服从的概率分布记为f(t),考虑所有可能的t,可以得到R满足自洽方程:

同理,可以得到一个随机节点属于网络稳态巨分支的概率S的方程:

求解方程(1)和方程(2)需要用到概率分布函数f(t),该函数可以通过概率R来获得.当网络处在稳定状态时,假如随机选择一个节点具有t个失效的依赖节点,那么该节点还能保留下来的概率为p[1-G0(1-αtR)],与其同在一个依赖组中的其他M—t—1 个依赖节点全部存活的概率为{p[1-G0(1-αtR)]}M-t-1.此外,依赖组内的失效节点分为两种,一种是因遭受初始攻击或因组外节点失效导致其脱离巨分支而失效,另一种是组内其他节点的失效导致其连接的减少而失效.假设有s个节点的失效是由前一种原因造成的,其发生概率为{1-p[1-G0(1-R)]}s,那么t-s个节点的失效是由后一种原因导致的,概率为{p[G0(1-αsR)-G0(1-R)]}t-s.因此,t的概率分布函数f(t) 为

对于给定的度分布P(k)和弱依赖组大小M,结合方程(3)并通过联立方程(1)和方程(2)可以得到网络中巨分支的最终大小S.

当α →1 时,依赖组内节点依赖强度趋向0,节点之间无相互依赖性而不会发生级联失效,随着保留节点比例p的降低,网络以二阶连续相变的方式发生破碎[15].当α →0 时,弱依赖组内节点之间的依赖强度最强,一旦组内一个节点被删除,组内其余节点将全部失效,网络以一阶不连续相变的方式发生破碎.因此,弱依赖组内节点之间的依赖强度α的值决定着网络在遭受攻击时的破碎形式,当α超过临界点αc时,网络的破碎方式可以从二阶渗流相变转变为一阶渗流相变.在网络以二阶相变方式发生破碎的情况下,当p接近二阶渗流相变点时,随机边属于稳态巨分支的概率R趋于零.在R ≡ε →0 和p →时,可以将(1)式进行泰勒展开表示为

进而可以求出二阶渗流相变点:

当α=1 或M=1 时,网络不存在弱依赖组,其结果和普通网络的渗流结果相同,二阶渗流相变点(1)[17].同时还可以发现,二阶渗流相变点随着弱依赖组大小M的增大而减小,这意味着网络中弱依赖组规模越大,网络就越脆弱.这一结果与弱依赖多层网络的结果类似,即二阶相变点与网络的层数和参数α有关[56].

图2 在不同初始保留节点比例p 和解耦系数α 时(1)式的图解 (a) α=0.5 的结果;(b) α=0.63 的结果;(c) α=0.8 的结果.本图中所用网络的度分布服从幂率分布 P(k)～k-γ(kmin ≤k ≤kmax),其中 kmin=2 ,kmax=141 ,γ=2.3Fig.2.The graphical solutions of Eq.(1) for different values of p and α:(a) Result for α=0.5 ;(b) result for α=0.63 ;(c) result for α=0.8 .For each panel,the degree distribution of networks follows a truncated power-law distributionP(k)～k-γ(kmin ≤k ≤kmax)with kmin=2 ,kmax=141,and γ=2.3 .

通过对(9)式求解,可以得到一阶相变和二阶相变发生转变的临界点αc.在随机网络中,节点度值服从泊松分布,方程(9)可以简化为

从(10)可以看出,αc依赖于网络平均度和依赖组的规模M.对于无标度网络,(9)式可以写成

其中括号〈·〉表示依据度分布对括号内的项取平均.因此,αc不仅取决于依赖组的规模M,而且依赖于无标度网络的度分布P(k).

4 数值模拟结果与分析

本文选择了两种网络模型,即度分布满足泊松分布的ER 随机网络和度分布满足近似幂律的无标度网络,来研究弱依赖组内节点的依赖强度、依赖组的规模和分布等不同特征对网络级联失效动力学和鲁棒性的影响,并通过理论计算对数值模拟的结果予以验证.对于ER 随机网络,采用随机向N个节点随机加边的方式生成.而对于无标度网络,首先生成一个近似满足幂率分布的度序列,然后采用配置模型生成其对应的无标度网络.在两种模型的生成过程中,自环和重复连接被禁止.

4.1 弱依赖组规模均匀分布

为了描述具有弱依赖组的网络上的“组间级联”和“组内级联”两种失效过程对网络鲁棒性的影响,本文以依赖组大小M=3 和M=4 的两种情况为例,研究当弱依赖组大小均匀分布时网络级联失效动力学的特点.图3(a)和图3(b)分别给出了当M=3和M=4 时,平均度〈k〉=4 的随机网络稳态巨分支的大小S随初始节点保留概率p的增加而变化情况.图3(c)和图3(d)给出了平均度〈k〉=5的随机网络,当弱依赖组大小M分别为3 和4 时,网络稳态巨分支规模S随p的增加而变化的情况.从图3(a)和图3(b)可以发现,无论是M=3还是M=4 的情况,当α较小时,随着初始保留节点p的降低,网络都是以一阶不连续相变的方式发生崩溃;而对于较大的α值,随着初始保留节点p的降低,网络以二阶连续相变的形式逐步瓦解.另外,可以发现M=3 的网络的临界点小于M=4的网络的临界点,这意味着前者比后者具有更强的鲁棒性.对于〈k〉=5 的随机网络,虽然定量的结果与〈k〉=4 时存在差异,但定性的结果是相似的.这些结果证实了依赖组的规模和组内节点的依赖强度对网络的破碎形式有着重要影响,依赖组规模越大,网络的鲁棒性就越差,同时依赖强度对网络的鲁棒性也有重要影响,当依赖强度较大时网络以一阶不连续相变的形式发生破碎,而依赖强度较小时网络以二阶连续相变的形式发生破碎.

图3 依赖组规模 M=3 和 M=4 的随机网络上的渗流相变 (a),(b)平均度为 〈k〉=4 的随机网络,弱依赖组大小分别为M=3和 M=4 的结果;(c),(d)在 〈k〉=5 时,弱依赖组平均大小分别为 M=3 和 M=4 的随机网络的结果.图中网络规模N=105,实线表示由(1)式和(2)式得到的理论预测,而垂直虚线分别表示由(5)式和(7)式所预测的一阶和二阶渗流相变点.模拟结果来自于100 次不同初始条件下的平均Fig.3.Simulation results for the percolation transitions on random networks with group sizes M=3 and M=4 :(a),(b) Results for random networks with the interdependency group sizes M=3 and M=4 respectively,where the average degree 〈k〉 is set to 4 for both panels;(c),(d) results for random networks with the interdependency group sizes M=3 and M=4 respectively,where average degree 〈k〉 is set to 5 for both panels.The network size is N=105 .The solid lines behind the symbols denote the theoretical predictions that were obtained by Eqs.(1) and (2).The vertical dashed lines denote the first-order and second-order percolation transition points predicted by Eqs.(7) and (5),respectively.The simulation results were averaged from 100 realizations of different initial conditions.

图3 还提供了理论预测的结果,理论预测的网络巨分支规模S与模拟结果非常符合,另外,数值模拟所得到的网络巨分支的规模S在理论预测的相变点处消失为0.这些结果证实了本文理论的正确性.此外,在不同初始条件下,初始节点保留概率p值对于极大簇的规模分布有着非常重要的影响.在p值远离临界点时,极大簇的规模分布是非常均匀的,而在p值处于临界点附近时,极大簇规模的涨落会非常大.因此除了理论预测的方法之外,还可以通过数值模拟来获得极大簇方差的大小来定位网络发生破碎的临界点[47].

图4 给出了弱依赖组大小分布均匀时,无标度网络的巨分支规模S随初始保留节点比例p的变化.此时,网络节点度服从P(k)～k-γ(kmin≤k≤kmax),其中kmax和kmin分别是节点度的上下限,γ是幂律指数,其平均度.与ER 随机网络的结果类似,对于较小的α值,网络以一阶不连续的方式发生崩溃,对于较大的α值,网络以二阶连续的方式逐步瓦解.两种渗流相变形式由临界点αc隔开.且当M=3 时,网络的渗流相变点小于M=4 的网络的渗流相变点,这意味着M=3的网络比M=4 的网络具有更强的鲁棒性.有趣的是,我们还发现当α增大到一定程度时无标度网络会发生双重相变,如α=0.63 .对于双重相变,网络首先以二阶连续相变的方式渗流,然后随着p的增加又会发生一阶不连续相变.随着α的增加,网络破碎形式转变为单个二阶连续相变;随着α的减小,二阶连续相变消失,网络的破碎形式转变为单个一阶不连续相变.

图4 依赖组规模 M=3 和 M=4 的无标度网络渗流相变 (a),(b)在 〈k〉=4 (kmin=2 ,kmax=63,γ=2.5)时,弱依赖组平均大小分别为 M=3 和 M=4 时的结果;(c),(d)在 〈k〉=5 (kmin=2 ,kmax=141 ,γ=2.3)时,弱依赖组规模分别为M=3和 M=4 时的结果.网络规模 N=105 .图中实线表示由(1)式和(2)式得到的理论预测.垂直虚线分别表示(7)式和(5)式预测的一阶和二阶渗流相变点.模拟结果来自于100 次不同初始条件下的平均Fig.4.Simulation results for the percolation transitions on scale-free networks with the interdependency group sizes M=3 and M=4:(a),(b) Results for scale-free networks withthe interdependency group sizes M=3 and M=4 respectively,where the average degree 〈k〉 is 4 with kmin=2,kmax=63 and γ=2.5 ;(c),(d) results for scale-free networks with the interdependency group sizes M=3 and M=4 respectively,where the average degree 〈k〉 is 5 with kmin=2,kmax=141 and γ=2.3 .The network sizeis N=105 .The solid lines behind the symbols denote the theoretical predictions by Eqs.(1) and (2),and the vertical dashed lines denote the first-order or second-order percolation transition points predicted by Eqs.(7) and (5),respectively.The simulation results are averaged from 100 realizations of different initial conditions.

此外,图4 的结果还表明,双重相变发生于度分布异质性较强的无标度网络且依赖组内节点依赖强度适中时.这是由于无标度网络节点的度分布异质性较强,当网络受到攻击而发生级联失效时,较多度值较小的节点会率先脱离网络的巨分支而失效,当失效节点的规模发散时网络就会发生一阶不连续的相变,而此时网络中度值较大的节点仍然能够形成稳定的簇结构,需要更大的攻击强度才能够将其彻底破坏.当依赖组中节点的依赖强度较大时,度值较大的中心节点很容易受到度值较小节点的影响而失效,无法形成规模较大的簇结构来对抗级联失效,此时网络只能发生一阶相变;在当依赖组中节点的依赖强度较弱时,节点会因相互之间的依赖太弱无法形成较大规模的级联失效而发生二阶连续相变.

图5(a)和图5(b)分别给出了在M=3 和M=4时随机网络的渗流相变点pc随α变化的情况,其中不同颜色的曲线表示不同网络平均度的结果.图中αc表示一阶相变和二阶相变的转变点,其值由弱依赖组的大小M和网络平均度〈k〉决定.图5(c)和图5(d)分别给出了在M=3 和M=4 时无标度网络的渗流相变点随α的变化.

图5 随机网络和无标度网络在弱依赖组规模服从平均分布时渗流相变点 pc 与α 的关系 (a)依赖组规模 M=3 的随机网络的渗流相变点 或与α 的关系,其中平均度 〈k〉 为4,5 和6;(b)依赖组规模 M=4 的随机网络的结果;(c)平均度 〈k〉 为4,5 和6 (分别对应度分布的幂律指数 γ 为2.5,2.3 和2.1)且依赖组规模 M=3 的无标度网络的结果;(d)依赖组规模 M=4 的无标度网络的结果.图中实线为一阶渗流相变点,虚线为二阶渗流相变点 .模拟结果来自于100 次不同初始条件下的平均Fig.5.The percolation transition point pc as functions of αon random networks and scale-free networks with uniform interdependency group size:(a) Results for random networks with the interdependency group size M=3,where the average degree 〈k〉 is 4,5 and 6 from high to low;(b) results for random networks with the group size M=4,where the average degree 〈k〉 is 4,5 and 6 from high to low;(c) results for scale-free networks with thegroup size M=3,where the average degree 〈k〉 is 4,5 and 6 (corresponding to a power-law exponent of degree distribution γ is 2.5,2.3 and 2.1,respectively);(d) results for scale-free networks with the interdependency group size M=4,where the average degree 〈k〉 is 4,5 and 6.The solid line is the first-order percolation transition point ,and the dashed line is the second-order percolation transition point .The simulation results were averaged from 100 realizations of different initial conditions.

从中可以发现,相变的方式以αc为界分为不连续和连续两种,但αc的值取决于弱依赖组的大小M和网络度分布P(k).另外,当无标度网络出现双重相变情况时,网络先以二阶连续相变的方式渗流,因此网络渗流相变点为二阶相变点.同时也可以发现,在大多数情况下,当依赖组内节点依赖强度较弱时,随机网络鲁棒性比无标度网络差,而当依赖组内节点依赖强度较强时,无标度网络鲁棒性比随机网络差.这是由于在随机攻击时,无标度网络中度值较大的中心节点不容易受到攻击,在依赖组内节点依赖强度较弱时也不容易受到其他节点的影响而受到损害,然而在依赖强度较大时,无标度网络中度值较大的节点容易受到组内其他节点失效的影响而造成大量连接被删除,从而对网络整体的连通性造成较大的影响.这一结果表明,无标度网络的鲁棒性与依赖组内节点的依赖强度有着密切的关联.

4.2 弱依赖组大小泊松分布

考虑到现实中一些复杂系统节点所形成的依赖组的规模并不一定是均匀的,本节以弱依赖组规模服从泊松分布的情况为例,用ER 随机网络和无标度网络来研究弱依赖组规模的非均匀分布对网络级联失效动力学的影响.考虑弱依赖组规模服从泊松分布函数Q(M=i)=,i=1,2,···,Mmax,其中〈M〉表示依赖组的平均规模.此时方程(1) 转换成

全国家用电器工业信息中心是面向全国家用电器行业服务的专业信息机构，拥有强大的行业研究、技术研究、标准研究和信息处理能力。全方位地提供行业分析、企业分析、市场分析及预测、预警等方面服务，在家电行业极具影响力。全国家用电器工业信息中心总部位于北京。

同理,方程(2)要转换成

关于渗流相变点的求值与上文所述的弱依赖组平均分布的求值方法相同,可得到二阶渗流相变点:

根据方程(14)可以发现,当网络中弱依赖组规模分布服从泊松分布时,网络的二阶渗流相变点与依赖组平均规模〈M〉相关,二阶渗流相变点随着弱依赖组平均规模〈M〉的增大而减小,这意味着网络中弱依赖组平均规模越大,网络鲁棒性就越差.

当网络发生一阶渗流相变时,R在相变点处从零跳跃到一个非零值Rc,此时方程(7)同样成立,通过联立方程(7) 和方程(12)求得弱依赖组规模服从泊松分布时的一阶渗流相变点

与弱依赖组规模平均分布时一阶与二阶渗流相变的临界点αc满足的条件相同,当p →pc和α=αc时,h′′(0)=0,此时得到

在度分布服从泊松分布的随机网络中,方程(15)可简化为

在度分布近似幂率分布的无标度网络中,方程(15)可简化为

图6(a)和图6(b)分别给出了弱依赖组规模服从泊松分布且平均值〈M〉分别为3 和4 时,平均度〈k〉=4随机ER 网络稳态巨分支的大小S随p增加而变化的情况.图6(c)和图6(d)分别给出了弱依赖组规模服从泊松分布且平均值〈M〉分别为3 和4 时,平均度〈k〉=5 的随机网络稳态巨分支的大小S随p增加而变化情况.从图中可以发现在随机网络中,对于较小的α值,网络以一阶不连续相变方式渗流,对于较大的α值,网络以二阶连续相变方式渗流.两种相变的形式在临界点αc处发生改变.另外,可以发现〈M〉=3 时,网络渗流相变点小于〈M〉=4 的网络,这意味着依赖组平均规模较小的网络鲁棒性更强.当〈k〉=5 时,弱依赖组平均规模〈M〉=3和〈M〉=4 的随机网络也具备类似的现象.图6 还提供了理论预测,结果与模拟结果基本符合.

图6 弱依赖组平均规模 〈M〉=3 和 〈M〉=4 的随机网络渗流相变的模拟结果 (a),(b) 平均度 〈k〉=4 的ER 随机网络在依赖组平均规模分别为 〈M〉=3 和 〈M〉=4 时的结果;(c),(d)平均度 〈k〉=5 的ER 随机网络在依赖组平均规模分别为 〈M〉=3 和〈M〉=4时的结果.网络规模设为 N=105 .图中实线表示由(12)式和(13)式得到的理论预测.垂直虚线分别表示理论预测的一阶和二阶渗流相变点.模拟结果来自于100 次不同初始条件下的平均Fig.6.Simulation results for percolation transitions on random networks with average group sizes 〈M〉=3 and 〈M〉=4 :(a),(b) Results for random networks with the average group sizes 〈M〉=3 and 〈M〉=4,respectively,where the average degree 〈k〉 is 4 ;(c),(d) results for random networks with the average group sizes〈M〉=3 and 〈M〉=4 respectively,where 〈k〉 is 5.The network size is N=105 .The solid linesbehind the symbols denote the theoretical predictions that were obtained by Eqs.(12) and(13),and the vertical dashed lines denote the first-order and second-order percolation transition points predicted by theory.The simulation results were averaged from 100 realizations of different initial conditions.

图7 给出了弱依赖组大小分布为泊松分布Q(M),且规模平均值〈M〉=5 和〈M〉=6 时,无标度网络上的渗流相变.从图7 可以发现类似于随机网络的结果,对于较小的α值,网络以一阶不连续相变方式渗流,对于较大的α值,网络以二阶连续相变方式渗流.两种渗流相变的形式的转变点发生于αc处,且〈M〉=5 的网络的渗流相变点小于〈M〉=6的网络,这意味着前者比后者具有更强的鲁棒性.同时发现,当弱依赖组大小服从泊松分布时,无标度网络的双重相变现象依然存在.图7 还提供了理论预测,理论结果与模拟结果的误差相对于随机网络较大,主要存在两个原因.首先对于无标度网络在给定度序列的情况下,由于度值较大的节点的数量较小,但这些节点对网络的鲁棒性产生了非常关键的作用,不同网络连接结构的差异性会对模拟结果产生较大的影响,因此模拟结果的误差较大.第二,极大簇在相变点附近有较大的涨落,也会导致模拟结果存在一定的误差.

图7 弱依赖组平均规模 〈M〉=5 和 〈M〉=6 的无标度网络渗流相变的模拟结果 (a),(b)在 〈k〉=4,即 kmin=2 ,kmax=63,γ=2.5时,弱依赖组平均规模分别为 〈M〉=5 和 〈M〉=6 的结果;(c),(d) 在 〈k〉=5,即 kmin=2,kmax=141,γ=2.3 时,弱依赖组平均规模分别为 〈M〉=5和 〈M〉=6 的结果.网络规模为 N=105 .图中实线表示由(12)式和(13)式得到的理论预测.垂直虚线分别表示预测的一阶和二阶渗流相变点Fig.7.Simulation results for percolation transitions on scale-free network with average group sizes 〈M〉=5 and 〈M〉=6 :(a),(b)Results for scale-free networks with average group sizes 〈M〉=5and 〈M〉=6 respectively,where the average degree 〈k〉 is 4 with kmin=2 ,kmax=63 and γ=2.5 ;(c),(d) results for scale-free networks with 〈M〉=5 and 〈M〉=6 respectively,where〈k〉is 5 with kmin=2 ,kmax=141 and γ=2.3 .The network size is N=105 .The solid lines behind the symbols denote the theoretical predictions by Eqs.(12)and (13),and the vertical dashed lines denote the first-order and second-order percolation transition points predicted by theory.The simulation results were averaged from 100 realizations of different initial conditions.

图8(a)和图8(b)分别给出了当网络平均度〈k〉不同时,弱依赖组平均规模〈M〉=3和〈M〉=4的随机网络的渗流相变点pc随α的变化.图中网络渗流相变的形式在αc处发生改变,且αc的大小由弱依赖组平均规模〈M〉和随机网络的平均度〈k〉决定.图8(c)和图8(d) 分别给出了不同平均度〈k〉时,弱依赖组平均大小〈M〉=3 和〈M〉=4 无标度网络的渗流相变点pc随α的变化.从中也可以发现类似依赖组大小平均分布的相变情况,相变的方式以αc为临界点分为不连续和连续两种,但临界点αc还取决于度分布的参数设置.另外,由于无标度网络出现双重相变情况时,网络先以连续相变的形式渗流,所以将视为此时渗流相变点pc.通过比较图8 和图5,可以发现依赖组规模不均匀分布的网络比依赖组规模均匀分布的网络具有更强的鲁棒性.

图8 随机网络和无标度网络在弱依赖组规模服从泊松分布时渗流相变点 pc 与α 的关系 (a) 〈M〉=3 的随机网络的渗流相变点 pc (或)与α 的关系,其中平均度 〈k〉 分别为4,5 和6;(b) 〈M〉=4 的随机网络的结果;(c)平均度 〈k〉 分别为4,5 和6 (度分布的幂指数 γ 分别为2.5,2.3 和2.1)且 〈M〉=3 的无标度网络的结果;(d) 〈M〉=4 的无标度网络的结果.图中实线为一阶渗流相变点,虚线为二阶渗流相变点Fig.8.The percolation transition point pc as functions of α on random networks and scale-free networks when the interdependency groups size follows poisson distribution:(a) Results for random networks with the average interdependency group size〈M〉=3,where the average degree 〈k〉 is 4,5 and 6 from high to low;(b) the same results to panel (a) but for 〈M〉=4 ;(c)results for scale-free networks with the average interdependency group size 〈M〉=3,where the average degree 〈k〉 is 4,5 and 6 from high to low (corresponding to a power-law exponent of degree distribution 2.5,2.3 and 2.1,respectively);(d) the same results to panel (c) but for 〈M〉=4 .The solid line is the first-order percolation transition point ,and the dashed line is the second-order percolation transition point .

5 总结与展望

在一些真实的复杂系统中,网络节点可能通过隐含的依赖关系而形成一些依赖组,其中一个节点失效后会对依赖组内其余节点造成一定程度的损害,进而会引发更多节点的失效而形成级联过程.基于此,本文提出了一种具有“弱依赖组”的复杂网络级联失效模型,依赖组中节点的依赖方式由一种“节点对边”的相互作用机制决定,与过去“节点到节点”的相互作用机制不同,当依赖组内一个节点失效时,组中其余节点都会受到一定程度的损害,而非完全失效.本文通过引入一个可调参数α来描述复杂网络中弱依赖组内节点的依赖强度,并研究了网络节点所形成的弱依赖组的规模,规模分布和依赖强度等几个特征对于复杂网络级联失效动力学和网络鲁棒性的影响.

由于“节点对边”的弱依赖机制的引入,本文发现网络在级联失效过程中存在两种效应:组间级联失效和组内级联失效.具体而言,组间级联失效表示一个节点的失效使依赖组外的部分节点不能通过失效节点连接到网络的巨分支而失效,这些新增失效节点进而会造成更多节点的失效,组间级联使得失效节点能够跨依赖组传播;组内级联失效表示一个节点的失效会给依赖组内其余功能节点造成损害而失去部分连接,从而使这些节点脱离网络巨分支而失效,这些新增失效节点进而给组内其余节点造成更大的损害而诱发更多节点失效,导致故障在依赖组内传播,这一微观效应在之前强依赖机制的模型中是不存在的,因在强依赖机制下,一旦依赖组中一个节点被删除,其余节点将会被完全删除.由于组外级联失效的存在,某一个依赖组内产生的失效会在扩张到其他依赖组后又传播到该依赖组内,从而进一步导致组内更多节点失效.而组内级联失效的存在打破了网络在部分节点在脱离网络巨分支后的平衡.因此可以看出,二者存在协同作用.

在两种级联动力学的共同作用下,网络以一阶或二阶相变的形式瓦解,且网络瓦解的形式由节点之间的依赖强度决定.这说明依赖组内节点的依赖强度对网络发生级联失效的形式产生了至关重要的影响.当节点之间的依赖性较弱时,节点的失效不能对组内依赖节点造成较大的破坏性,从而抑制了故障的传播,使系统通过二阶渗流相变的形式发生破碎.当节点之间的依赖性较强时,节点的故障会以组内级联的方式传播到较为广泛的范围,从而导致系统的突然崩溃.这些结果表明,组内级联失效过程影响着组间级联失效的过程,并对网络级联失效的形式和网络鲁棒性起到了至关重要的作用.

数值模拟和理论分析的结果表明,随着依赖组的规模和依赖组内节点的依赖强度的增大,网络的鲁棒性会逐渐下降,这是由于弱依赖组规模更小的网络可将组内级联限制在一个较小的范围内,避免了失效在较大范围内扩散.同时,依赖组规模不均匀分布的网络比依赖组规模均匀分布的网络具有更强的鲁棒性,这是因为依赖组规模分布不均匀的网络虽允许更大规模的依赖组出现,但大规模依赖组出现的概率较低,不容易受到攻击,且攻击数量较多且规模较小的依赖组也不会造成太大范围的组内级联,从而限制了组内级联的范围.

此外,在大多数情况下,当依赖组内节点依赖强度较弱时,随机网络鲁棒性比无标度网络差,而当依赖组内节点依赖强度较强时,无标度网络鲁棒性比随机网络差.这一结果表明,存在依赖组的情况下,度分布的异质性和依赖组规模分布的异质性都能够对系统的鲁棒性造成显著的影响.

最后,本文还发现了无标度网络中在依赖组中节点依赖强度适中时会发生二重相变的现象,这是由于无标度网络度分布的异质性较强,当网络受到一定程度的攻击时所发生的级联失效只能破坏为数众多的度值较小的节点,而对于度值较大的节点还能形成稳定的簇结构,如将网络彻底破坏还需更强的攻击强度.

本文将“节点对边”作用机理引入到了具有依赖组的的级联失效模型中,描述了节点之间更为一般的依赖机制,不但对于理解依赖组的规模、规模分布和节点依赖强度等因素对网络级联失效的作用和级联失效的发生机理具有重要的科学意义,而且对于通过依赖组的特征来对复杂网络级联失效的控制、预防干预策略的设计和鲁棒性的优化具有重要的启发意义.本文所研究的依赖组基于组内节点的相互依赖性完全相同的假设,然而在现实中依赖组内节点的相互影响可能不是完全等同的.因此后续的研究仍然存在较大的拓展空间,如依赖强度的非均匀性或非对等性对于网络的级联失效动力学是否具有显著的影响？此外,依赖组内的节点是否能够形成某种结构,依赖组的内节点的依赖结构是否对网络级联失效有较大的影响？这些问题都值得我们进一步进行实证或理论研究.