搜索

x

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

相依网络上基于相连边的择优恢复算法

吴佳键 龚凯 王聪 王磊

引用本文:
Citation:

相依网络上基于相连边的择优恢复算法

吴佳键, 龚凯, 王聪, 王磊

Enhancing resilience of interdependent networks against cascading failures under preferential recovery strategies

Wu Jia-Jian, Gong Kai, Wang Cong, Wang Lei
PDF
导出引用
  • 如何有效地应对和控制故障在相依网络上的级联扩散避免系统发生结构性破碎,对于相依网络抗毁性研究具有十分重要的理论价值和现实意义.最新的研究提出一种基于相依网络的恢复模型,该模型的基本思想是通过定义共同边界节点,在每轮恢复阶段找出符合条件的共同边界节点并以一定比例实施恢复.当前的做法是按照随机概率进行选择.这种方法虽然简单直观,却没有考虑现实世界中资源成本的有限性和择优恢复的必然性.为此,针对相依网络的恢复模型,本文利用共同边界节点在极大连通网络内外的连接边数计算边界节点的重要性,提出一种基于相连边的择优恢复算法(preferential recovery based on connectivity link,PRCL)算法.利用渗流理论的随机故障模型,通过ER随机网络和无标度网络构建的不同结构相依网络上的级联仿真结果表明,相比随机方法和度数优先以及局域影响力优先的恢复算法,PRCL算法具备恢复能力强、起效时间早且迭代步数少的优势,能够更有效、更及时地遏制故障在网络间的级联扩散,极大地提高了相依网络遭受随机故障时的恢复能力.
    Interdependent networks are extremely fragile because a very small node failure in one network would trigger a cascade of failures in the entire system. Therefore, the resilience of interdependent networks is always a critical issue studied by researchers in different fields. Existing studies mainly focused on protecting several influential nodes for enhancing robustness of interdependent networks before the networks suffer random failures. In reality, it is necessary to repair a failing interdependent network in time to prevent it from suffering total breakdown. Recent investigations introduce a failure-recovery model for studying the concurrent failure process and recovery process of interdependent networks based on a random recovery strategy. This stochastic strategy covers repairing a small fraction of mutual boundary nodes which are the failed neighbors of the giant connected component of each network, with a random probability of recovery . Obviously, the random recovery is simple and straightforward. Here, we analyze the recovery process of interdependent networks with two types of connectivity links, i.e., the first-type connectivity links and the second-type connectivity links, which represent the mutual boundary nodes(being also failed nodes) linked to survival nodes in current giant connected component, and linked to failed nodes out of current giant connected component in networks, respectively. We find that when mutual boundary nodes have more first-type connectivity links, the current giant connected component has higher average degree and immediately makes better interdependent network resilience, on the other hand, more second-type connectivity links generate more candidates during the recovery procedure, and indirectly make better system resilience. In short, two types of connectivity links of mutual boundary nodes both have great effects on the resilience of interdependent networks during the recovery. In this paper, we propose a new recovery strategy (preferential recovery based on connectivity link, or PRCL) to identify the mutual boundary node recovery influence in interdependent networks, based on the failure-recovery model. By defining two indexes that represent the numbers of first-type and links second-type connectivity links, respectively, we calculate the boundary influence with one parameter f by combining together with two indexes. After calculating all boundary nodes in the current process, we obtain a boundary importance index which is more accurate to indicate recovery influence of boundary node for each boundary node in interdependent networks. Our strategy is applied to interdependent networks constructed by ER random network or/and scale-free network with the same average degree. And a dynamical model of random failure based on percolation theory is used to make a comparison of performance between PRCL and other recovery strategies(including random recovery, preferential recovery based on degree, preferential recovery based on local centrality) in terms of four quantitative indices, i.e., probability of existence of the giant connected component, number of iteration steps, recovery robustness and average degree of the steady state of the giant connected component. Experiments on different interdependent networks (ER-ER/SF-SF/ER-SF/SF-ER) demonstrate that with a very small number of mutual boundary node recoveries by PRCL strategy, the resilience and robustness of entire system under the recovery process can be greatly enhanced. Finally, the only parameter f in PRCL strategy is also discussed. Our strategy is meaningful in practice as it can largely enhance interdependent network resilience and contribute to the decrease of system breakdown risk.
      通信作者: 龚凯, gongkai1210@swufe.edu.cn
    • 基金项目: 国家自然科学基金(批准号:61602331)、中央高校基本科研业务费(批准号:JBK170133)和四川省教育厅科研基金(批准号:J17ZB0434)资助的课题.
      Corresponding author: Gong Kai, gongkai1210@swufe.edu.cn
    • Funds: Project supported by the National Natural Science Foundation of China (Grant No. 61602331), the Fundamental Research Funds for the Central Universities of China (Grant No. JBK170133), and the Scientific Research Foundation of the Education Department of Sichuan Province, China (Grant No. 17ZB0434).
    [1]

    Vespignani A 2010 Nature 464 984

    [2]

    Buldyrev S V, Parshani R, Paul G, Stanley H E, Havlin S 2010 Nature 464 1025

    [3]

    Gao J X, Buldyrev S V, Stanley H E, Havlin S 2012 Nat. Phys. 8 40

    [4]

    Chen S M, L H, Xu Q G, Xu Y F, Lai Q 2015 Acta Phys. Sin. 64 048902 (in Chinese)[陈世明, 吕辉, 徐青刚, 许云飞, 赖强 2015 物理学报 64 048902]

    [5]

    Rinaldi S M, Peerenboom J P, Kelly T K 2001 IEEE Contr. Syst. 21 11

    [6]

    Morris R G, Barthelemy M 2013 Sci. Rep. 3 2764

    [7]

    Liu L J, Yin Y F, Zhang Z H, Malaiya Y K 2016 Plos One 10 e0164777

    [8]

    Korkali M, Veneman J G, Tivnan B F, Bagrow J P, Hines P D H 2017 Sci. Rep. 7 44499

    [9]

    Wang X F, Li X, Chen G R 2012 Network Science:An Introduction (Beijing:Higher Education Press) (in Chinese)[汪小帆, 李翔, 陈关荣 2012 网络科学导论(北京:高等教育出版社)]

    [10]

    Cohen R, Erez K, Ben-Avraham D, Havlin S 2001 Phys. Rev. Lett. 86 3682

    [11]

    Albert R, Albert I, Nakarado G L 2004 Phys. Rev. E 69 025103

    [12]

    Gong K, Tang M, Hui P M, Zhang H F, Younghae D, Lai Y C 2013 Plos One 8 83489

    [13]

    Zhang Z K, Liu C, Zhan X X, Lu X, Zhang C X, Zhang Y C 2016 Phys. Rep. 65 1

    [14]

    Schneider C M, Yazdani N, Arajo N A M, Havlin S, Herrmann H 2013 Sci. Rep. 3 1969

    [15]

    Du R J, Dong G G, Tian L X, Liu R R 2016 Physica A 450 687

    [16]

    Gong M G, Ma L J, Cai Q, Jiao L C 2015 Sci. Rep. 5 8439

    [17]

    Wang J D, Lao S Y, Ruan Y R, Bai L, Hou L L 2017 Appl. Sci. 7 597

    [18]

    Shang Y L 2016 Sci. Rep. 6 30521

    [19]

    Shekhtman L M, Danziger M M, Havlin S 2016 Chaos Solition. Fract. 90 28

    [20]

    Muro M A D, Rocca C E L, Stanley H E, Havlin S, Braunstein L A 2016 Sci. Rep. 6 22834

    [21]

    Schneider C M, Moreira A A, Andrade J S, Havlin S, Herrmann H J 2011 Proc. Natl. Acad. Sci. USA 108 3838

    [22]

    Huang X Q, Gao J X, Buldyrev S V, Havlin S, Stanley H E 2011 Phys. Rev. E 83 065101

    [23]

    Hu F Y, Yeung C H, Yang S N, Wang W P, Zeng A 2016 Sci. Rep. 6 24522

    [24]

    Majdandzic A, Podobnki B, Buldyrev S V, Kenett D Y, Havlin S, Stanley H E 2013 Nat. Phys. 10 34

    [25]

    Liu J G, Lin J H, Guo Q, Zhou T 2016 Sci. Rep. 6 21380

    [26]

    Weng J S, Lim E P, Jiang J, He Q 2010 Proceedings of the Third ACM International Conference on Web Search and Data Mining (New York:ACM Press) pp261-270

    [27]

    Liu C, Zhang Z K 2014 Commun. Nonlinear. Sci. 19 896

    [28]

    Ren X L, L L Y 2014 Chin. Sci. Bull. 13 1175 (in Chinese)[任晓龙, 吕琳媛 2014 科学通报 13 1175]

    [29]

    Liu R R, Li M, Jia C X, Wang B H 2016 Sci. Rep. 6 25294

    [30]

    Sun S W, Wu Y F, Ma Y L, Wang L, Gao Z K, Xia C Y 2016 Sci. Rep. 6 32983

    [31]

    Wang X Y, Cao J Y, Qin X M 2016 Plos One 11 e0160545

    [32]

    Boccaletti S, Bianconi G, Criado R, del Genio C I, Gmez-Gardees J, Romance M, Sendia-Nadal I, Wang Z, Zanin M 2014 Phys. Rep. 544 1

    [33]

    Valdez L D, Macri P A, Braunstein L A 2014 J. Phys. A:Math. Theor. 47 055002

    [34]

    Freeman L C 1979 Social Networks 1 215

    [35]

    Chen D B, L L Y, Shang M S, Zhang Y C, Zhou T 2012 Physica A 391 1777

    [36]

    Erds P, Rnyi A 1959 Publ. Math. Debrecen 6 290

    [37]

    Newman M E 2003 SIAM Rev. 45 167

    [38]

    Radicchi F 2015 Nat. Phys. 11 7

    [39]

    Liu R R, Jia C X, Zhang J L, Wang B H 2012 J. Univ. Shanghai Sci. Technol. 34 235 (in Chinese)[刘润然, 贾春晓, 章剑林, 汪秉宏 2012 上海理工大学学报 34 235]

  • [1]

    Vespignani A 2010 Nature 464 984

    [2]

    Buldyrev S V, Parshani R, Paul G, Stanley H E, Havlin S 2010 Nature 464 1025

    [3]

    Gao J X, Buldyrev S V, Stanley H E, Havlin S 2012 Nat. Phys. 8 40

    [4]

    Chen S M, L H, Xu Q G, Xu Y F, Lai Q 2015 Acta Phys. Sin. 64 048902 (in Chinese)[陈世明, 吕辉, 徐青刚, 许云飞, 赖强 2015 物理学报 64 048902]

    [5]

    Rinaldi S M, Peerenboom J P, Kelly T K 2001 IEEE Contr. Syst. 21 11

    [6]

    Morris R G, Barthelemy M 2013 Sci. Rep. 3 2764

    [7]

    Liu L J, Yin Y F, Zhang Z H, Malaiya Y K 2016 Plos One 10 e0164777

    [8]

    Korkali M, Veneman J G, Tivnan B F, Bagrow J P, Hines P D H 2017 Sci. Rep. 7 44499

    [9]

    Wang X F, Li X, Chen G R 2012 Network Science:An Introduction (Beijing:Higher Education Press) (in Chinese)[汪小帆, 李翔, 陈关荣 2012 网络科学导论(北京:高等教育出版社)]

    [10]

    Cohen R, Erez K, Ben-Avraham D, Havlin S 2001 Phys. Rev. Lett. 86 3682

    [11]

    Albert R, Albert I, Nakarado G L 2004 Phys. Rev. E 69 025103

    [12]

    Gong K, Tang M, Hui P M, Zhang H F, Younghae D, Lai Y C 2013 Plos One 8 83489

    [13]

    Zhang Z K, Liu C, Zhan X X, Lu X, Zhang C X, Zhang Y C 2016 Phys. Rep. 65 1

    [14]

    Schneider C M, Yazdani N, Arajo N A M, Havlin S, Herrmann H 2013 Sci. Rep. 3 1969

    [15]

    Du R J, Dong G G, Tian L X, Liu R R 2016 Physica A 450 687

    [16]

    Gong M G, Ma L J, Cai Q, Jiao L C 2015 Sci. Rep. 5 8439

    [17]

    Wang J D, Lao S Y, Ruan Y R, Bai L, Hou L L 2017 Appl. Sci. 7 597

    [18]

    Shang Y L 2016 Sci. Rep. 6 30521

    [19]

    Shekhtman L M, Danziger M M, Havlin S 2016 Chaos Solition. Fract. 90 28

    [20]

    Muro M A D, Rocca C E L, Stanley H E, Havlin S, Braunstein L A 2016 Sci. Rep. 6 22834

    [21]

    Schneider C M, Moreira A A, Andrade J S, Havlin S, Herrmann H J 2011 Proc. Natl. Acad. Sci. USA 108 3838

    [22]

    Huang X Q, Gao J X, Buldyrev S V, Havlin S, Stanley H E 2011 Phys. Rev. E 83 065101

    [23]

    Hu F Y, Yeung C H, Yang S N, Wang W P, Zeng A 2016 Sci. Rep. 6 24522

    [24]

    Majdandzic A, Podobnki B, Buldyrev S V, Kenett D Y, Havlin S, Stanley H E 2013 Nat. Phys. 10 34

    [25]

    Liu J G, Lin J H, Guo Q, Zhou T 2016 Sci. Rep. 6 21380

    [26]

    Weng J S, Lim E P, Jiang J, He Q 2010 Proceedings of the Third ACM International Conference on Web Search and Data Mining (New York:ACM Press) pp261-270

    [27]

    Liu C, Zhang Z K 2014 Commun. Nonlinear. Sci. 19 896

    [28]

    Ren X L, L L Y 2014 Chin. Sci. Bull. 13 1175 (in Chinese)[任晓龙, 吕琳媛 2014 科学通报 13 1175]

    [29]

    Liu R R, Li M, Jia C X, Wang B H 2016 Sci. Rep. 6 25294

    [30]

    Sun S W, Wu Y F, Ma Y L, Wang L, Gao Z K, Xia C Y 2016 Sci. Rep. 6 32983

    [31]

    Wang X Y, Cao J Y, Qin X M 2016 Plos One 11 e0160545

    [32]

    Boccaletti S, Bianconi G, Criado R, del Genio C I, Gmez-Gardees J, Romance M, Sendia-Nadal I, Wang Z, Zanin M 2014 Phys. Rep. 544 1

    [33]

    Valdez L D, Macri P A, Braunstein L A 2014 J. Phys. A:Math. Theor. 47 055002

    [34]

    Freeman L C 1979 Social Networks 1 215

    [35]

    Chen D B, L L Y, Shang M S, Zhang Y C, Zhou T 2012 Physica A 391 1777

    [36]

    Erds P, Rnyi A 1959 Publ. Math. Debrecen 6 290

    [37]

    Newman M E 2003 SIAM Rev. 45 167

    [38]

    Radicchi F 2015 Nat. Phys. 11 7

    [39]

    Liu R R, Jia C X, Zhang J L, Wang B H 2012 J. Univ. Shanghai Sci. Technol. 34 235 (in Chinese)[刘润然, 贾春晓, 章剑林, 汪秉宏 2012 上海理工大学学报 34 235]

计量
  • 文章访问数:  5976
  • PDF下载量:  339
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-11-24
  • 修回日期:  2018-01-26
  • 刊出日期:  2019-04-20

/

返回文章
返回