基于时间序列的网络失效模型*

严玉为 蒋沅 杨松青 余荣斌 洪成

(南昌航空大学信息工程学院,南昌 330063)

随着网络科学的发展,静态网络已不能清晰刻画网络的动态过程.在现实网络中,个体之间的交互随时间而快速演化.这种网络模式将时间与交互过程紧密联系,能够清晰刻画节点的动态过程.因此,如何更好地基于时间序列刻画网络行为变化是现有级联失效研究的重要问题.为了更好地研究该问题,本文提出一种基于时间序列的失效模型.通过随机攻击某时刻的节点,分析了时间、激活比例、连边数、连接概率4 个参数对失效的影响并发现网络相变现象.同时为验证该模型的有效性与科学性,采用真实网络进行研究.实验表明,该模型兼顾时序以及传播动力学,具有较好的可行性,为解释现实动态网络的级联传播提供了参考.

1 引言

随着网络科学的进步,网络已成为分析人类活动与自然现象的有力工具[1−3].随机网络模型、小世界网络模型和以偏好连接的无标度网络模型都是静态网络模型.这些静态网络模型适合捕捉网络中的基本特征,但前提网络节点之间的连接是长期存在的[4].然而,在现实生活中,个体之间的连接快速演变,例如交通网络、社交网络、通信网络.有必要利用一种有效模型来描述这些动态过程.Perra等[5]首次通过定义活动势构建活动驱动模型.Liao等[6]基于动态网络提出节点重要度排序方法.Wang等[7]发现动态网络在整个网络过程中所需的能量以及轨迹数量少.目前时序网络是新兴方向,但是研究意义重大,与静态网络相比,时序网络从时间角度考虑节点间的交互,更加精准反映交互过程.因此基于时序网络的研究已然成为复杂网络科学的重要研究部分.而网络健壮性[8−15]也是网络安全的核心课题之一.级联故障是现实生活中的常见现象,例如电网崩溃、交通网络的中断以及疾病传播.级联失效的原因是由于网络中的故障节点通过渗流作用将失效传递到周围节点从而造成大规模破坏.因此,研究级联失效能更好理解网络失效,进而更好地控制级联失效.

在过去的一段时间,研究者们提出多种级联失效模型.Motter 等[16]提出线性容量模型(ML 模型),通过模拟连锁故障对网络连通性进行评估.实验结果表明,通过移除较高负载的节点可以造成网络全局级联失效.Dou 等[17]针对ML 模型提出一种更为灵活的非线性负载容量模型,进而研究网络成本与鲁棒性之间的关系.实验表明此模型更加符合现实生活中负载与容量之间的关系.Wang[18]将边的初始负载定义为节点度的函数,当一条边的负载超过其自身容量时,边不会从网络中移除,而是将自身额外的负载向周围边进行传递.Li 等[19]将节点或边的负载定义为节点或边的最短路径数量.Wang 等[20]构建一种负载局部重分配的级联失效模型,并考察无标度网络的级联失效.Liu 等[21]提出一种基于多变负载的负载分配策略.通过将节点剩余容量充分利用从而减少网络级联失效.唐亮等[22]构建一种故障概率传播的级联失效模型,节点故障概率随故障次数的增加而减少,网络失效规模减少.Duan 等[23]提出全局分配策略的级联失效模型.Hao 等[24]提出过载级联失效模型,并指出网络节点超出一定容量后并不会失效而是处于过载状态.

综上所述,现有级联失效的研究停留在静态网络,而在现实生活中,事件的发生与时间紧密联系,无论是社交网络还是交通网络,这些网络中节点的接触都是不断变化.基于此,本文构建具有时间戳的网络结构,并以此探讨时间参数T、激活比例pactive、连接边数M、连接概率pcon对网络的影响,此模型更加符合现实网络中失效情况,对进一步研究级联失效具有很强的实用性和现实意义.

2 时序网络的失效模型

2.1 时序网络建模

探讨时序网络下级联失效的前提是对时序网络进行建模.我们仅考虑网络中边的增加与移除,并不考虑节点的出现与消失,也就是说在时序网络中节点数目不变,连边随时间的推移而动态变化.将其表示为G=(vi,vj,t),其中vi和vj分别表示网络源节点与目标节点,t表示两个节点之间的接触时刻.将网络各个接触时刻当成一个快照,即快照反映某一时刻发生的所有事件.在此基础上,通过聚合所有快照进而得到时间聚合图.其时序网络快照以及时间聚合图如图1 所示.从图1 可以看出,节点在不同时刻产生的交互次数以及交互对象不同.在时刻T=1 时(见图1(a)),节点(vA,vB),(vA,vD),(vB,vD),(vD,vC)之间产生连边.而在时刻T=2 时,节点vA不在与节点vB,vD产生交互,而当时刻T=3 时,节点(vB,vD)之间不在交互,取而代之的则是(vB,vC)之间的交互.以此类推直到时间结束.

图1 时序网络图 (a)T=1;(b) T=2;(c) T=3;(d) T=4;(e) T=5;(f) T=6;(g) T=AllFig.1.Sequential network:(a) T=1;(b) T=2;(c) T=3;(d) T=4;(e) T=5;(f) T=6;(g) T=All.

在时序网络初始阶段中,首先选取部分节点作为初始传播节点.在时刻1 中(见图2(a)),每个活跃节点以一定概率随机向M个节点进行连接.随后从时刻1 中激活的节点再次选取一定比例的节点作为第2 时刻的初始活跃节点(见图2(b)).以此进行迭代,直到网络达到时间最大值或网络中没有后继节点进行传播,其时序传播示意如图2 所示.

图2 时序网络传播示意图 (数字表示节点编号) (a) T=1;(b) T=2;(c) T=3Fig.2.Propagation of sequential network (number indicates the node number):(a) T=1;(b) T=2;(c) T=3.

2.2 时序网络级联失效

级联失效是指失效节点引发其他节点失效的一种级联现象,常见于电力网络、交通网络等.为此在本文时序网络中,通过随机攻击某时刻的节点,来观察时序网络的失效情况.同时,本文分别给出静态图和时序图的级联失效,以此显示静态图与时序图级联失效差异,从而更好地说明研究时序下级联失效的必要性.图3(a)表示静态网络,在静态网络中,当某节点失效时,失效节点会将自身周围边进行无差别断开.例如当节点vc遭受损坏时,节点vc会将自身边进行无差别断开,其网络拓扑如图3(b)所示.而在时序图中网络被赋予了时间概念,不仅要考虑节点失效,而且还要考虑节点的失效时刻.例如在图3(c)中节点vA经历的时刻T=2,4,6 如果节点vA在时刻T=6 失效,那么只会影响节点vB,不影响节点vC,而当节点vA在时刻T=2 失效,其节点vA在T≥2 时都会传输错误信息进而影响对应时刻的节点.在静态图中,规定节点失效条件为受到攻击或者脱离巨连通网络,如图3(b)所示,当节点vC受到攻击时,网络破碎成3 个簇结构(A,B),(D,E),(F,G),通过选择节点数最多的簇作为巨连通网络(如果簇大小相同则随机选择),其他节点失效.而在时序图中,节点并不会移除与增加,当一个节点在某一时刻受攻击时,该节点只会对以后时刻产生影响而不会影响之前时刻.同时,注意到在时序网络中一个节点vI在某一时刻会同时接收一定数量的错误信息NTfail与正确信息NTcorrect,如图3(c)所示,假设节点vC在时刻3 受到攻击,则节点vG在时刻5 分别收到节点vF,vC,vE传来的信息.其中节点vE受到节点vC的影响导致节点vE在时刻5 传输错误信息,而节点vF则不受节点vC影响,其传输正确信息.因此节点vG在时刻5 接受了1 个正确信息,2 个错误信息.其在时刻5 失效概率为pfail=0.64.因此,利用一个概率函数p进行模拟节点容错能力:

图3 静态图与时序网络图 (a) 静态图;(b) 静态网络失效图;(c) 时序图Fig.3.Static diagram and sequential network diagram:(a) Static diagram;(b) static network failure diagram;(c) sequential network.

其中,NTcorrect表示节点在T时刻接受的正确信息数量;NTfail表示节点在T时刻接受的错误信息数量.

2.3 时序网络抗级联失效鲁棒性测试

本文将网络鲁棒性度量指标设为节点在受到攻击以后执行的交互次数N′与时间聚合窗口内节点进行的交互总数N之比.即G=N′/N.其中G值越大说明网络损坏程度越大,说明此时网络的鲁棒性越差.

3 仿真结果及分析

首先构建时序网络:在初始时刻,选取一定比例的初始节点,以连接概率随机激活M个节点,随后从上一阶段激活的节点中选取一定比例的节点作为传播节点进行下一时刻的传递,直到时间结束或者没有后继节点.本文设网络具有200 节点,通过对网络进行随机攻击来观察网络的失效程度,为了避免实验的随机性,所有结果均运行500 次并取平均值.

3.1 激活参数pactive 对网络的影响

为了探索激活参数对时序网络的影响,令连边概率pcon=0.3,时间T=5,连边数M=5,攻击比例p从0 开始,以此来观察网络鲁棒性的变化.取pactive=0.1,0.2,0.3,0.5,0.6,1.0 时的仿真结果如图4 所示.

图4 不同激活参数的网络鲁棒性Fig.4.Robustness of networks under different activation parameters.

从图4 可以看出,网络失效程度随激活参数的增大而减小.在时序网络中,激活参数影响每次迭代时间步内节点活跃度.节点活跃度高的节点会向下激活节点活跃度低的节点.当网络中节点活跃度高的数目较高时,信息衰减率就更低,节点交互数目变大.从图4 中得知,虽然网络鲁棒性随着活跃参数的增大而增大,但是抗毁性的变化却不是线性的.其中pactive从0.2 到0.5 变化时,网络抗毁行性提升最多,此后抗毁性提升在逐渐变小.在实际生活中,信息传播是不断衰减的,通过信息论可知,现实中信息衰减率较高.因此,信息衰减的减少能够带来网络抗毁性的提高.同时为了更加直观地展示激活参数在网络中的作用,给出不同激活参数下的网络结构特征(见表1),其中n为节点总数,m为网络连边总数,〈kin/out〉 分别为平均入度和平均出度,其网络拓扑图如图5 所示.

表1 激活参数下的网络特征Table 1.Statistical characteristics of the networks under activation parameters.

图5 不同激活参数下的网络生成图 (a) pactive=0.1;(b) pactive=0.2;(c) pactive=0.3;(d) pactive=0.5;(e) pactive=0.6;(f) pactive=1.0Fig.5.Network diagram with different activation parameters:(a) pactive=0.1;(b) pactive=0.2;(c) pactive=0.3;(d) pactive=0.5;(e) pactive=0.6;(f) pactive=1.0.

3.2 连边数M 和连接概率 pcon 对网络的影响

分别设置pactive=0.3,pcon=0.3,T=5,M=1,2,5,8,10 以及pactive=0.3,时间T=5,连边数M=5,连接概率pcon=0.1,0.2,0.5,0.6,1.0.在随机攻击策略下,分析连边数以及连接概率对网络鲁棒性的影响.其仿真结果如图6 所示.

从图6(a)可以看出,网络鲁棒性随着连接数目以及连接概率的增加而提升.从图中可以清晰看出:连边条数的增加对于网络鲁棒性的提升是有限的.网络连边表示的是节点自身的影响力.当一个节点连接数越大,那么该节点就会与更多节点产生接触,也就表示一个节点在某一个时刻可以同时接受多个节点的连边,节点受到错误信息的影响变小.这与现实生活中谎言传播极为相似,当某个人同时接收相同数量的错误信息和正确信息后,那么这个人就会面临二选一情况,而当另外一个人提供了正确信息后,那么就大大增加选对概率.而连接概率表示的是节点连接效率,即产生有效接触数.如图6(b)所示,随着连接概率的增加,网络鲁棒性有限提高.因此,连接数以及连接概率对网络鲁棒性的影响相辅相成,两者之间存在着关联.其连边参数下的网络生成图如图7 所示.表2 表示不同连边条数以及连接概率下的网络结构特征,其中n为节点总数,m为连边总数,〈kin/out〉 分别为平均入度和平均出度.

表2 不同连接数以及连接概率下的网络特征Table 2.Statistical characteristics of the networks under different connection numbers and connection probabilities.

图6 不同边数以及连接概率下的网络鲁棒性 (a)不同连边数;(b)不同连接概率Fig.6.Network robustness under different connection numbers and connection probabilities:(a) Different edge numbers;(b) different connection probabilities.

图7 不同连接数以及连接概率下的网络生成图 (a) M=1;(b) M=2;(c) M=5;(d) M=8;(e) M=10;(f) pcon=0.1;(g) pcon=0.2;(h) pcon=0.5;(i) pcon=0.6;(j) pcon=1Fig.7.Network diagram with different connection numbers and connection Probability:(a)M=1;(b)M=2;(c) M=5;(d) M=8;(e) M=10;(f) pcon=0.1;(g) pcon=0.2;(h) pcon=0.5;(i) pcon=0.6;(j) pcon=1.

3.3 连边数M 与激活参数pactive 对网络的影响

分别设置pcon=0.3,T=5,M=2,3,4,5,6,并让pactive从0.05 开始变化以此来观察网络鲁棒性.其仿真结果如图8 所示.

从图8 可以看出,网络鲁棒性在连边数以及激活参数的影响下表现并不均衡.当pactive=0.45时,网络鲁棒性发生了相变现象,并且随着连边数M的不同,网络鲁棒性表现也不同.其中网络鲁棒性在M=2,3,4,5,6 时分别提高了11.36%,17.8%,22.8%,24.9%,30.4%.同时从图8 可以看出当pactive<0.45,网络鲁棒性在区间M=4—5提升最多.而当pactive>0.45 时,网络鲁棒性在区间M=2—3 提升最多,这一发现为解释和保护现实网络提供了重要参考.

图8 网络鲁棒性Fig.8.Network robustness.

3.4 时间参数T 对网络的影响

为了探索时间参数T对时序网络的影响,令pactive=0.3,M=5,pcon=0.3,攻击比例p从0开始,以此来观察网络鲁棒性的变化.取T=2,5,10,20,30 时的仿真结果如图9 所示.

图9 不同时间下的网络鲁棒性Fig.9.Network robustness under different time.

从图9 可以看出,网络鲁棒性随着时间T的延长并没有明显变化.在时序网络中,时间T表示网络中节点与节点可接触的最大时间.随着时间T的延长,节点与节点可接触的时刻变多,网络也愈加复杂.当网络中一个节点因失效而发送错误信息时,由于错误信息会受到正确信息的限制,时间越大,这种限制越强.这与现实生活是极为类似的.然而图9 结果却不相同.通过分析发现是由于激活参数以及连接概率相对较小造成的.表3 表示不同时间下的网络结构特征.同时,为了更加直观地观察,其网络结构图如图10 所示.

表3 不同时间下的网络特征Table 3.Statistical characteristics of the networks under different time.

图10 不同时间下的网络生成图 (a) T=2;(b) T=5;(c) T=10;(d) T=20;(e) T=30Fig.10.Network diagram under different times:(a) T=2;(b) T=5;(c) T=10;(d) T=20;(e) T=30.

从图10 可以看出,网络中节点之间并没有生成连通图,而是几个簇.因此将设参数pactive=0.6,连边数M=5,连接概率pcon=0.6.其网络失效如图11 所示.

由图11 可以看到,网络鲁棒性随着时间参数的增大而增强.此时再观察网络结构图,其如图12所示.同时,网络特征如表4 所示.

表4 不同时间下的网络特征Table 4.Statistical characteristics of the networks under different times.

图11 不同时间参数的网络鲁棒性Fig.11.Network robustness under different time.

通过图12 可以看出,在激活参数以及连边概率参数增大后,网络在时刻T=5 时变为连通图.随着T的增大,网络愈加复杂,网络抗毁性得到进一步增强.同时,为了更好地与实际相结合,以美国小型社交网络为例分别仿真了静态网络的级联失效以及时间序列的级联失效.该数据集描述的是35 个人在间隔1 h 的接触情况,其网络失效图以及接触情况如图13 和表5 所示,美国小型社交网络的结构特征n=35,m=118,〈kin/out〉=3.3714.

表5 美国小型社交网络的接触时刻Table 5.Contact time of small social networks in the United States.

图12 不同时间下的网络图 (a) T=2;(b) T=5;(c) T=10;(d) T=20;(e) T=30Fig.12.Network diagram under different times:(a) T=2;(b) T=5;(c) T=10;(d) T=20;(e) T=30.

图13 美国小型社交网络级联传递规模图Fig.13.Scale of transmission through small social networks in the United States.

通过本文的级联传播理论,其失效规模的传递规模如图13 所示.从图13 可以看到,即使在初始阶段中受影响人群规模达到100%,但是由于人群所处的时刻不一样,失效信息的传递随着拓扑结构的变化而变化.其传递只会影响发生时刻之后的时间,因此,网络抗毁性提高.与之对比,静态网络在遭受攻击以后会出现大规模节点永久性失效,如图3(b)所示,当节点vc失效时,其节点以及自身连边会无差别永久性失效,同时造成其他节点脱离巨连通网络失效,以此网络出现大规模失效.而在本文所提模型中,传播过程中遵循一定的方向性、时间性.因此,面对攻击,静态网络相对于时间序列的网络是极其脆弱的,这一方面从图13 可以得出.

4 结论

随着网络科学的发展,静态网络已不能清晰刻画网络的动态过程.为了突破现有研究的局限性,提出了时序网络下的级联失效,此模型将网络交互赋予了时间概念,相对于传统的级联失效模型不仅考虑网络的拓扑结构还考虑节点接触时刻.通过对节点的某时刻进行随机攻击,有效地分析了动态网络下级联反应行为.同时,发现激活参数、连边数、时间、连边概率对时序网络的抗毁性起着重要作用,更为重要的是发现了时序网络的相变现象.

最后,为了验证该模型的有效性与可行性,引入真实网络进行分析.实验显示,本文提出的模型能更好地从时间角度进行描述与分析级联失效,为研究级联失效提供了重要参考.未来将进一步考虑将所提模型应用到实际中,例如电网、交通网等.