高级搜索

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

,  ,  ,  , 

downloadPDF

上一篇

下一篇

严玉为, 蒋沅, 杨松青, 余荣斌, 洪成. 基于时间序列的网络失效模型[J]. 物理学报, 2022, 71(8): 088901-1. doi: 10.7498/aps.71.20212106
引用本文: 严玉为, 蒋沅, 杨松青, 余荣斌, 洪成. 基于时间序列的网络失效模型[J]. 物理学报, 2022, 71(8): 088901-1. doi: 10.7498/aps.71.20212106
shu
Yu-Wei Yan, Yuan Jiang, Song-Qing Yang, Rong-Bin Yu, Cheng Hong. Network failure model based on time series[J]. Acta Physica Sinica, 2022, 71(8): 088901-1. doi: 10.7498/aps.71.20212106
Citation: Yu-Wei Yan, Yuan Jiang, Song-Qing Yang, Rong-Bin Yu, Cheng Hong. Network failure model based on time series[J]. Acta Physica Sinica, 2022, 71(8): 088901-1. doi: 10.7498/aps.71.20212106
shu

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

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

    • 作者简介: lihongxingniran@163.com .
    通讯作者: E-mail: jiangyuan@nchu.edu.cn; 

  • 中图分类号: 89.90.+n, 89.75.-k, 89.75.Da

Network failure model based on time series

  • Institute of Information Engineering, Nanchang Hangkong University, Nanchang 330063, China

    • Corresponding author: E-mail: jiangyuan@nchu.edu.cn; 

  • MSC: 89.90.+n, 89.75.-k, 89.75.Da

  • 摘要: 随着网络科学的发展, 静态网络已不能清晰刻画网络的动态过程. 在现实网络中, 个体之间的交互随时间而快速演化. 这种网络模式将时间与交互过程紧密联系, 能够清晰刻画节点的动态过程. 因此, 如何更好地基于时间序列刻画网络行为变化是现有级联失效研究的重要问题. 为了更好地研究该问题, 本文提出一种基于时间序列的失效模型. 通过随机攻击某时刻的节点, 分析了时间、激活比例、连边数、连接概率4个参数对失效的影响并发现网络相变现象. 同时为验证该模型的有效性与科学性, 采用真实网络进行研究. 实验表明, 该模型兼顾时序以及传播动力学, 具有较好的可行性, 为解释现实动态网络的级联传播提供了参考.
    Abstract: With the development of network science, the static network has been unable to clearly characterize the dynamic process of the network. In real networks, the interaction between individuals evolves rapidly over time. This network model closely links time to interaction process. Compared with static networks, dynamic networks can clearly describe the interaction time of nodes, which has more practical significance. Therefore, how to better describe the behavior changes of networks after being attacked based on time series is an important problem in the existing cascade failure research. In order to better answer this question, a failure model based on time series is proposed in this paper. The model is constructed according to time, activation ratio, number of edges and connection probability. By randomly attacking nodes at a certain time, the effects of four parameters on sequential networks are analyzed. In order to validate the validity and scientificity of this failure model, we use small social networks in the United States. The experimental results show that the model is feasible. The model takes into account the time as well as the spreading dynamics and provides a reference for explaining the dynamic networks in reality.
  • 加载中

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

    Figure 1.  Sequential network: (a) T = 1; (b) T = 2; (c) T = 3; (d) T = 4; (e) T = 5; (f) T = 6; (g) T = All.

    下载: 全尺寸图片 幻灯片

    图 2  时序网络传播示意图 (数字表示节点编号)　(a) T = 1; (b) T = 2; (c) T = 3

    Figure 2.  Propagation of sequential network (number indicates the node number): (a) T = 1; (b) T = 2; (c) T = 3.

    下载: 全尺寸图片 幻灯片

    图 3  静态图与时序网络图　(a) 静态图; (b) 静态网络失效图; (c) 时序图

    Figure 3.  Static diagram and sequential network diagram: (a) Static diagram; (b) static network failure diagram; (c) sequential network.

    下载: 全尺寸图片 幻灯片

    图 4  不同激活参数的网络鲁棒性

    Figure 4.  Robustness of networks under different 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.0

    Figure 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.

    下载: 全尺寸图片 幻灯片

    图 6  不同边数以及连接概率下的网络鲁棒性　(a)不同连边数; (b)不同连接概率

    Figure 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 = 1

    Figure 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.

    下载: 全尺寸图片 幻灯片

    图 8  网络鲁棒性

    Figure 8.  Network robustness.

    下载: 全尺寸图片 幻灯片

    图 9  不同时间下的网络鲁棒性

    Figure 9.  Network robustness under different time.

    下载: 全尺寸图片 幻灯片

    图 10  不同时间下的网络生成图　(a) T = 2; (b) T = 5; (c) T = 10; (d) T = 20; (e) T = 30

    Figure 10.  Network diagram under different times: (a) T = 2; (b) T = 5; (c) T = 10; (d) T = 20; (e) T = 30.

    下载: 全尺寸图片 幻灯片

    图 11  不同时间参数的网络鲁棒性

    Figure 11.  Network robustness under different time.

    下载: 全尺寸图片 幻灯片

    图 12  不同时间下的网络图　(a) T = 2; (b) T = 5; (c) T = 10; (d) T = 20; (e) T = 30

    Figure 12.  Network diagram under different times: (a) T = 2; (b) T = 5; (c) T = 10; (d) T = 20; (e) T = 30.

    下载: 全尺寸图片 幻灯片

    图 13  美国小型社交网络级联传递规模图

    Figure 13.  Scale of transmission through small social networks in the United States

    下载: 全尺寸图片 幻灯片

    表 1  激活参数下的网络特征

    Table 1.  Statistical characteristics of the networks under activation parameters.

    pactivenm$\langle {k^{ { { {\rm{in} }/{\rm{out} } } } } } \rangle$
    0.1200320.16
    0.2200680.34
    0.32001910.955
    0.52007873.945
    0.62008434.215
    1.0200320316.015
    下载: 导出CSV

    表 2  不同连接数以及连接概率下的网络特征

    Table 2.  Statistical characteristics of the networks under different connection numbers and connection probabilities.

    Parameternm$\langle {k^{ {\text{in} }/{\text{out} } } } \rangle$
    M = 1200120.060
    M = 2200240.120
    M = 52001430.715
    M = 82005072.535
    M = 102008534.265
    pcon = 0.1200160.080
    pcon = 0.2200450.225
    pcon = 0.52001790.895
    pcon = 0.62002761.380
    pcon = 1.02009834.915
    下载: 导出CSV

    表 3  不同时间下的网络特征

    Table 3.  Statistical characteristics of the networks under different time.

    Tnm$\langle {k^{ {\text{in} }/{\text{out} } } } \rangle$
    2200570.285
    5200680.340
    10200700.350
    20200810.405
    30200710.355
    下载: 导出CSV

    表 4  不同时间下的网络特征

    Table 4.  Statistical characteristics of the networks under different times.

    Tnm$\langle {k^{ {\text{in} }/{\text{out} } } } \rangle$
    22009314.655
    5200525826.290
    102001168958.445
    202001546477.320
    3020023062115.310
    下载: 导出CSV

    表 5  美国小型社交网络的接触时刻

    Table 5.  Contact time of small social networks in the United States.

    Source nodeTarget nodeTimeSource nodeTarget nodeTimeSource nodeTarget nodeTime
    ${v_1}$${v_{12}}$4${v_3}$${v_{13}}$2${v_{16}}$${v_{10}}$2
    ${v_1}$${v_{18}}$9${v_3}$${v_{18}}$2${v_{16}}$${v_{12}}$4
    ${v_2}$${v_{10}}$7${v_3}$${v_{25}}$2${v_{16}}$${v_{14}}$2
    ${v_2}$${v_{12}}$1${v_4}$${v_{10}}$4${v_{16}}$${v_{18}}$4
    ${v_2}$${v_{13}}$1${v_4}$${v_{12}}$1${v_{16}}$${v_{32}}$1
    ${v_2}$${v_{14}}$1${v_4}$${v_{27}}$1${v_{17}}$${v_{10}}$3
    ${v_2}$${v_{18}}$1${v_4}$${v_{32}}$4${v_{18}}$${v_{12}}$2
    ${v_3}$${v_{10}}$2${v_5}$${v_{12}}$4${v_{18}}$${v_{13}}$1
    ${v_5}$${v_{13}}$1${v_8}$${v_{10}}$1${v_{18}}$${v_{14}}$2
    ${v_5}$${v_{18}}$5${v_8}$${v_{12}}$2${v_{19}}$${v_{14}}$7
    ${v_5}$${v_{20}}$1${v_8}$${v_{13}}$7${v_{21}}$${v_{13}}$1
    ${v_5}$${v_{27}}$1${v_8}$${v_{15}}$1${v_{21}}$${v_{20}}$4
    ${v_7}$${v_1}$1${v_8}$${v_{18}}$2${v_{22}}$${v_{10}}$3
    ${v_7}$${v_{18}}$1${v_8}$${v_{20}}$2${v_{22}}$${v_{12}}$4
    ${v_7}$${v_{33}}$1${v_8}$${v_{27}}$2${v_{22}}$${v_{13}}$1
    ${v_8}$${v_2}$1${v_8}$${v_{32}}$2${v_{22}}$${v_{18}}$11
    ${v_9}$${v_1}$3${v_{11}}$${v_{10}}$3${v_{22}}$${v_{27}}$3
    ${v_9}$${v_5}$2${v_{11}}$${v_{12}}$1${v_{22}}$${v_{31}}$1
    ${v_9}$${v_{12}}$1${v_{11}}$${v_{14}}$6${v_{24}}$${v_3}$2
    ${v_9}$${v_{18}}$1${v_{11}}$${v_{18}}$1${v_{24}}$${v_6}$1
    ${v_9}$${v_{33}}$2${v_{11}}$${v_{25}}$1${v_{24}}$${v_{10}}$8
    ${v_{10}}$${v_{12}}$1${v_{11}}$${v_{30}}$3${v_{24}}$${v_{12}}$4
    ${v_{10}}$${v_{13}}$1${v_{11}}$${v_{32}}$1${v_{24}}$${v_{13}}$3
    ${v_{10}}$${v_{18}}$2${v_{16}}$${v_2}$1${v_{24}}$${v_{18}}$2
    ${v_{24}}$${v_{25}}$3${v_{28}}$${v_5}$10${v_{33}}$${v_{10}}$2
    ${v_{24}}$${v_{32}}$3${v_{28}}$${v_{12}}$2${v_{33}}$${v_{14}}$2
    ${v_{24}}$${v_{33}}$1${v_{28}}$${v_{23}}$1${v_{33}}$${v_{25}}$1
    ${v_{24}}$${v_{35}}$1${v_{29}}$${v_3}$1${v_{34}}$${v_{10}}$1
    ${v_{25}}$${v_{10}}$1${v_{29}}$${v_{10}}$2${v_{34}}$${v_{12}}$9
    ${v_{25}}$${v_{12}}$5${v_{29}}$${v_{12}}$6${v_{34}}$${v_{13}}$1
    ${v_{25}}$${v_{14}}$4${v_{29}}$${v_{14}}$2${v_{34}}$${v_{14}}$1
    ${v_{25}}$${v_{18}}$2${v_{29}}$${v_{15}}$2${v_{34}}$${v_{18}}$7
    ${v_{26}}$${v_{10}}$3${v_{29}}$${v_{25}}$1${v_{34}}$${v_{20}}$2
    ${v_{26}}$${v_{12}}$1${v_{29}}$${v_{32}}$4${v_{35}}$${v_2}$1
    ${v_{26}}$${v_{14}}$12${v_{30}}$${v_{13}}$1${v_{35}}$${v_6}$1
    ${v_{26}}$${v_{15}}$2${v_{30}}$${v_{14}}$7${v_{35}}$${v_{10}}$2
    ${v_{26}}$${v_{18}}$1${v_{31}}$${v_{10}}$2${v_{35}}$${v_{12}}$2
    ${v_{26}}$${v_{30}}$3${v_{31}}$${v_{13}}$3${v_{35}}$${v_{13}}$1
    ${v_{35}}$${v_{14}}$4${v_{35}}$${v_{25}}$2${v_{35}}$${v_{32}}$3
    ${v_{35}}$${v_{18}}$1
    下载: 导出CSV
  • [1] Holme P 2003 Europhys. Lett. 64 427 doi: 10.1209/epl/i2003-00505-4
    [2] Holme P, Park S M, Kim B J, Edling C R 2007 Physica A 373 821 doi: 10.1016/j.physa.2006.04.066
    [3] Onody R N, Castro P A 2004 Phys. Rev. E 70 037103 doi: 10.1103/PhysRevE.70.037103
    [4] Albert R Jeong, H, Barabasi A 1999 Nature 401 130 doi: 10.1038/43601
    [5] Perra N, Gonçalves B, Pastor R, Vespignani A 2012 Sci. Rep. 2 469 doi: 10.1038/srep00469
    [6] Liao H, Mariani M S, Medo M, Zhang Y C 2017 Phys. Rep. 689 1 doi: 10.1016/j.physrep.2017.05.001
    [7] Li A, Cornelius S, Liu Y Y, Wang L, Barabasi, A 2016 Science 358 1042 doi: 10.1126/science.aai7488
    [8] Steven H 2001 Nature 401 268 doi: 10.1038/35065725
    [9] Remacle, Jean F, Flaherty, Joseph E, Shephard, Mark S 2003 SIAM Rev. 45 53 doi: 10.1137/S00361445023830
    [10] 杨松青, 蒋沅, 童天驰, 严玉为, 淦各升 2021 物理学报 70 216401 doi: 10.7498/aps.70.20210979 Yang S Q, Jiang Y, Tong T C, Yan Y W, Gan G S 2021 Acta Phys. Sin. 70 216401 doi: 10.7498/aps.70.20210979
    [11] Sole R V, Rosas M, Corominas B, Valverde S 2007 Phys. Rev. E 77 26102 doi: 10.1103/PhysRevE.77.026102
    [12] Goh K I, Kahng B, Kim D 2002 Phys. Rev. Lett. 88 108701 doi: 10.1103/PhysRevLett.88.108701
    [13] Holme P, Kim B J, Yoon C N, Han S K 2002 Phys. Rev. E 65 056109 doi: 10.1103/PhysRevE.65.056109
    [14] Albert R, Jeong H, Barabasi A. L 2000 Nature 406 387 doi: 10.1038/35019019
    [15] Zhou T, Wang B H 2005 Chin. Phys. Lett. 22 1072 doi: 10.1088/0256-307X/22/5/012
    [16] Motter A E, Lai Y C 2003 Phys. Rev. E 66 065102 doi: 10.1103/PhysRevE.66.065102
    [17] Dou B L, Wang X G, Zhang S Y 2010 Physica A 389 2310 doi: 10.1016/j.physa.2010.02.002
    [18] Wang J 2012 Nonlinear Dyn. 70 1959 doi: 10.1007/s11071-012-0587-8
    [19] Li S, Li L, Yang Y, Luo Q 2012 Nonlinear Dyn. 69 837 doi: 10.1007/s11071-011-0308-8
    [20] Wang J, Rong L, Liang Z, Zhang Z 2008 Physica A 387 6671 doi: 10.1016/j.physa.2008.08.037
    [21] Liu J, Xiong Q Y, Shi X, Wang K, Shi W R 2015 Chin. Phys. B 24 371 doi: 10.1088/1674-1056/24/7/076401
    [22] 唐亮, 焦鹏, 李纪康, 靖可, 靳志宏 2018 控制与决策 33 116 doi: 10.13195/j.kzyjc.2017.0728 Tang L, Jiao P, Li J K, Jing K, Le Z H 2018 Control and Decision 33 116 doi: 10.13195/j.kzyjc.2017.0728
    [23] Duan D L, Ling X D, Wu X Y, Ouyang D H, Zhong B 2014 Physica A 2014 416 252 doi: 10.1016/j.physa.2014.08.040
    [24] 郝羽成, 李成兵, 魏磊 2018 系统工程与电子技术 40 2282 doi: 10.3969/j.issn.1001-506X.2018.10.19 Hao Y C, Li C, Wei L 2018 Syst. Eng. Electron. 40 2282 doi: 10.3969/j.issn.1001-506X.2018.10.19
  • 加载中
图( 13) 表( 5)
计量
  • 文章访问数:  411
  • HTML全文浏览数:  411
  • PDF下载数:  0
  • 施引文献:  0
出版历程
  • 收稿日期:  2021-08-09
  • 刊出日期:  2022-04-20

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

    通讯作者: E-mail: jiangyuan@nchu.edu.cn; 
    作者简介: lihongxingniran@163.com
  • 南昌航空大学信息工程学院, 南昌　330063
  • 收稿日期:  2021-08-09

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

English Abstract

    全文HTML

    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 = {{(}}{v_i}, {v_j}, t{{)}}$, 其中${v_i}$和${v_j}$分别表示网络源节点与目标节点, t表示两个节点之间的接触时刻. 将网络各个接触时刻当成一个快照, 即快照反映某一时刻发生的所有事件. 在此基础上, 通过聚合所有快照进而得到时间聚合图. 其时序网络快照以及时间聚合图如图1所示. 从图1可以看出, 节点在不同时刻产生的交互次数以及交互对象不同. 在时刻T = 1时(见图1(a)), 节点(${v_A}$, ${v_B}$), (${v_A}$, ${v_D}$), (${v_B}$, ${v_D}$), (${v_D}$, ${v_C}$)之间产生连边. 而在时刻T = 2时, 节点${v_A}$不在与节点${v_B}$, ${v_D}$产生交互, 而当时刻T = 3时, 节点(${v_B}$, ${v_D}$)之间不在交互, 取而代之的则是(${v_B}$, ${v_C}$)之间的交互. 以此类推直到时间结束.

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

      • 2.2.   时序网络级联失效

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

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

      • 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为连边总数, $ \langle {k^{{\text{in}}/{\text{out}}}} \rangle $分别为平均入度和平均出度.

      • 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提升最多, 这一发现为解释和保护现实网络提供了重要参考.

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

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

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

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

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

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

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

    4.   结　论

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

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

    参考文献 (24)

目录

/

返回文章
返回