搜索

文章查询

x

留言板

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

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

相依网络的条件依赖群逾渗

韩伟涛 伊鹏

相依网络的条件依赖群逾渗

韩伟涛, 伊鹏
PDF
HTML
导出引用
导出核心图
  • 相依网络鲁棒性研究多集中于满足无反馈条件的一对一依赖, 但现实网络节点往往依赖于多节点构成的依赖群, 即使群内部分节点失效也不会导致依赖节点失效. 针对此现象提出了一种相依网络的条件依赖群逾渗模型, 该模型允许依赖群内节点失效比例不超过容忍度$\gamma $时, 依赖节点仍可正常工作. 通过理论分析给出了基于生成函数方法的模型巨分量方程, 仿真结果表明方程理论解与相依网络模拟逾渗值相吻合, 增大$\gamma $值和依赖群规模可提高相依网络鲁棒性. 本文模型有助于更好地理解现实网络逾渗现象, 对如何增强相依网络鲁棒性有一定指导作用.
      通信作者: 伊鹏, yipengndsc@163.com
    • 基金项目: 国家重点研发计划(批准号: 2017YFB0803200, 2018YFB0804002)和国家自然科学基金(批准号: 61802429, 61872382)资助的课题.
    [1]

    Albert R, Barabási A 2002 Rev. Mod. Phys. 74 47

    [2]

    Dorogovtsev S N, Goltsev A V, Mendes J F 2008 Rev. Mod. Phys. 80 1275

    [3]

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

    [4]

    Rosato V, Issacharoff L, Tiriticco F, Meloni S, Porcellinis S, Setola R 2008 Int. J. Crit. Infr. 4 63

    [5]

    Parshani R, Buldyrev S V, Havlin S 2010 Phys. Rev. Lett. 105 48701

    [6]

    Shao J, Buldyrev S V, Havlin S, Stanley H E 2011 Phys. Rev. E 83 36116

    [7]

    Parshani R, Buldyrev S V, Havlin S 2011 Proc. Natl. Acad. Sci. USA 108 1007

    [8]

    Li M, Wang B H 2014 Chin. Phys. B 23 79

    [9]

    Wang H, Li M, Deng L, Wang B H 2015 Plos One 10 e126674

    [10]

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

    [11]

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

    [12]

    Yuan X, Hu Y Q, Stanley H E, Havlin S 2017 Proc. Natl. Acad. Sci. USA 114 3311

    [13]

    吴佳键, 龚凯, 王聪, 王磊 2018 物理学报 67 088901

    Wu J J, Gong K, Wang C, Wang L 2018 Acta Phys. Sin. 67 088901

    [14]

    Newman M 2010 Networks. An introduction(1st Ed.) (Oxford: Oxford University Press) pp 414 − 423

    [15]

    La Rocca C E, Stanley H E, Braunstein L A 2018 Physica A 508 577

    [16]

    Kong L W, Li M, Liu R R, Wang B H 2017 Phys. Rev. E 95 32301

    [17]

    Li W, Bashan A, Buldyrev S V, Stanley H E, Havlin S 2012 Phys. Rev. Lett. 108 228702

    [18]

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

    [19]

    Di Muro M A, Buldyrev S V, Stanley H E, Braunstein L A 2016 Phys. Rev. E 94 42304

    [20]

    Wang Z X, Zhou D, Hu Y Q 2018 Phys. Rev. E 97 32306

    [21]

    Wang H, Li M, Deng L, Wang B H 2018 Physica A 502 195

    [22]

    Newman M E, Strogatz S H, Watts D J 2001 Phys. Rev. E 64 26118

    [23]

    Feng L, Monterola C P, Hu Y Q 2015 New J. Phys. 17 63025

    [24]

    Erdős P, Rényi A 1959 Publ. Math. 62 90

    [25]

    Wilf H S 1994 Generating Functionology (2nd Ed.)(London: Academic Press) pp 1 − 16

  • 图 1  具有多依赖关系的相依网络逾渗示意图, 初始攻击导致红色节点失效, 随后发生级联失效过程, 最终相依网络仅有极少数节点存活

    Fig. 1.  The model of percolation of interdependent networks with multiple support-dependence relations. The red node fails after the initial attack. Then the cascading failure process leads to a catastrophiccollapse of the interdependent networks. Finally, only a small fraction of nodes survive.

    图 2  相依网络的条件依赖群逾渗模型 A网络节点随机依赖于B网络的$\tilde k$个节点($\tilde k \geqslant 0$), 反之亦然; A网络的a节点依赖的3个节点有一个失效, 但失效比例未超过容忍度$\gamma = 0.5$, a节点继续工作; B网络的b节点依赖的节点失效比例超过$\gamma = 0.5$, 所以b节点失效

    Fig. 2.  The model of percolation in interdependent networks with conditional dependency clusters. Nodes in network A randomly depends on $\tilde k$ ($\tilde k \geqslant 0$) nodes in network B and vice versa. One of the three nodes which node a in network A depends on fails, but the failure proportion does not exceed $\gamma = 0.5$, node a still works. Two of the three nodes which node b in network B depends on fail, the failure proportion exceeds$\gamma = 0.5$, node bfails.

    图 3  不同$\gamma $取值的RR-RR相依网络逾渗, 每个网络节点数$N = 200000$, 平均度$\left\langle k \right\rangle = 6$, $\tilde P(10) = 1$, 空心标记为仿真值, 实线为逾渗方程数值解 (a) 巨分量${\mu _\infty }$$p$对应关系; (b) 级联失效迭代次数(number of iterations, NOI)

    Fig. 3.  The results of the percolation of RR-RR interdependent networks for different $\gamma $, each network has 200000 nodes, average degree is 6, $\tilde P(10) = 1$. The symbols represent the simulation results, and the solid linesshow the corresponding analytical predictions. (a) The size ofthe giant component ${\mu _\infty }$versus $p$; (b) number of iterations.

    图 4  不同$\gamma $值对应的ER-ER相依网络相变点, 网络平均度$\left\langle k \right\rangle = 6$, $\tilde P(10) = 1$

    Fig. 4.  Graphical solutions of ER-ER interdependent networks transition for different $\gamma $. The average degree is 6, $\tilde P(10) = 1$.

    图 5  不同$\gamma $取值的ER-ER相依网络逾渗, 每个网络节点数$N = 200000$, 平均度$\left\langle k \right\rangle = 6$, $\tilde P(10) = 1$, 空心标记为仿真值, 实线为逾渗方程数值解 (a) 巨分量${\mu _\infty }$$p$对应关系; (b) 级联失效迭代次数

    Fig. 5.  The results of the percolation of ER-ER interdependent networks for different $\gamma $, each network has 200000 nodes, average degree is 6, $\tilde P(10) = 1$. The symbols represent the simulation results, and the solid linesshow the corresponding analytical predictions. (a) The size ofthe giant component ${\mu _\infty }$ versus $p$; (b) number of iterations.

    图 6  不同依赖度分布的ER-ER相依网络逾渗, $\tilde P(10) = 1$, $\tilde P(5) = 1$分别用实心和空心标记表示, 每个网络节点数$N = 200000$, 平均度$\left\langle k \right\rangle = 6$ (a) 巨分量${\mu _\infty }$$p$对应关系; (b) 级联失效迭代次数

    Fig. 6.  The results of the percolation of ER-ER interdependent networks for different dependency degrees, each network has 200000 nodes, average degree is 6. The dependency degrees are $\tilde P(10) = 1$ (solid symbols) and $\tilde P(5) = 1$ (empty symbols). (a) The size ofthe giant component ${\mu _\infty }$ versus $p$; (b) number of iterations.

    图 7  不同$\gamma $取值的ER-ER相依网络相变点, 空心标记为仿真结果, 实线是理论值

    Fig. 7.  The critical point ${p_{\rm{c}}}$ versus $\gamma $ of ER-ER interdependent networks, The symbols represent the simulation results, and the solid linesshow the corresponding analytical predictions.

    图 8  不同$\gamma $取值的SF-SF相依网络逾渗, 每个网络节点数$N = 200000$, 平均度$\left\langle k \right\rangle = 6$, $\lambda = 2.7$, $\tilde P(10) = 1$, 空心标记为仿真值, 实线为逾渗方程数值解 (a) 巨分量${\mu _\infty }$$p$对应关系; (b) 级联失效迭代次数

    Fig. 8.  The results of the percolation of SF-SF interdependent networks for different $\gamma $, each network has 200000 nodes, average degree is 6, $\lambda = 2.7$, $\tilde P(10) = 1$. The symbols represent the simulation results, and the solid linesshow the corresponding analytical predictions. (a) The size ofthe giant component ${\mu _\infty }$ versus $p$; (b) number of iterations.

  • [1]

    Albert R, Barabási A 2002 Rev. Mod. Phys. 74 47

    [2]

    Dorogovtsev S N, Goltsev A V, Mendes J F 2008 Rev. Mod. Phys. 80 1275

    [3]

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

    [4]

    Rosato V, Issacharoff L, Tiriticco F, Meloni S, Porcellinis S, Setola R 2008 Int. J. Crit. Infr. 4 63

    [5]

    Parshani R, Buldyrev S V, Havlin S 2010 Phys. Rev. Lett. 105 48701

    [6]

    Shao J, Buldyrev S V, Havlin S, Stanley H E 2011 Phys. Rev. E 83 36116

    [7]

    Parshani R, Buldyrev S V, Havlin S 2011 Proc. Natl. Acad. Sci. USA 108 1007

    [8]

    Li M, Wang B H 2014 Chin. Phys. B 23 79

    [9]

    Wang H, Li M, Deng L, Wang B H 2015 Plos One 10 e126674

    [10]

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

    [11]

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

    [12]

    Yuan X, Hu Y Q, Stanley H E, Havlin S 2017 Proc. Natl. Acad. Sci. USA 114 3311

    [13]

    吴佳键, 龚凯, 王聪, 王磊 2018 物理学报 67 088901

    Wu J J, Gong K, Wang C, Wang L 2018 Acta Phys. Sin. 67 088901

    [14]

    Newman M 2010 Networks. An introduction(1st Ed.) (Oxford: Oxford University Press) pp 414 − 423

    [15]

    La Rocca C E, Stanley H E, Braunstein L A 2018 Physica A 508 577

    [16]

    Kong L W, Li M, Liu R R, Wang B H 2017 Phys. Rev. E 95 32301

    [17]

    Li W, Bashan A, Buldyrev S V, Stanley H E, Havlin S 2012 Phys. Rev. Lett. 108 228702

    [18]

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

    [19]

    Di Muro M A, Buldyrev S V, Stanley H E, Braunstein L A 2016 Phys. Rev. E 94 42304

    [20]

    Wang Z X, Zhou D, Hu Y Q 2018 Phys. Rev. E 97 32306

    [21]

    Wang H, Li M, Deng L, Wang B H 2018 Physica A 502 195

    [22]

    Newman M E, Strogatz S H, Watts D J 2001 Phys. Rev. E 64 26118

    [23]

    Feng L, Monterola C P, Hu Y Q 2015 New J. Phys. 17 63025

    [24]

    Erdős P, Rényi A 1959 Publ. Math. 62 90

    [25]

    Wilf H S 1994 Generating Functionology (2nd Ed.)(London: Academic Press) pp 1 − 16

  • [1] 韩伟涛, 伊鹏, 马海龙, 张鹏, 田乐. 异质弱相依网络鲁棒性研究. 物理学报, 2019, 68(18): 186401. doi: 10.7498/aps.68.20190761
    [2] 陈世明, 邹小群, 吕辉, 徐青刚. 面向级联失效的相依网络鲁棒性研究. 物理学报, 2014, 63(2): 028902. doi: 10.7498/aps.63.028902
    [3] 高彦丽, 陈世明. 一种全局同质化相依网络耦合模式. 物理学报, 2016, 65(14): 148901. doi: 10.7498/aps.65.148901
    [4] 吴佳键, 龚凯, 王聪, 王磊. 相依网络上基于相连边的择优恢复算法. 物理学报, 2018, 67(8): 088901. doi: 10.7498/aps.67.20172526
    [5] 陈世明, 吕辉, 徐青刚, 许云飞, 赖强. 基于度的正/负相关相依网络模型及其鲁棒性研究. 物理学报, 2015, 64(4): 048902. doi: 10.7498/aps.64.048902
    [6] 彭兴钊, 姚宏, 杜军, 王哲, 丁超. 负荷作用下相依网络中的级联故障. 物理学报, 2015, 64(4): 048901. doi: 10.7498/aps.64.048901
    [7] 蒋文君, 刘润然, 范天龙, 刘霜霜, 吕琳媛. 多层网络级联失效的预防和恢复策略概述. 物理学报, 2020, 69(8): 088904. doi: 10.7498/aps.69.20192000
    [8] 袁铭. 带有层级结构的复杂网络级联失效模型. 物理学报, 2014, 63(22): 220501. doi: 10.7498/aps.63.220501
    [9] 欧阳博, 金心宇, 夏永祥, 蒋路茸, 吴端坡. 疾病传播与级联失效相互作用的研究:度不相关网络中疾病扩散条件的分析. 物理学报, 2014, 63(21): 218902. doi: 10.7498/aps.63.218902
    [10] 牟威圩, 许小亮. 感染生长模型的逾渗模拟. 物理学报, 2006, 55(6): 2871-2876. doi: 10.7498/aps.55.2871
    [11] 马仲发, 庄奕琪, 杜 磊, 包军林, 李伟华. 栅氧化层介质经时击穿的逾渗模型. 物理学报, 2003, 52(8): 2046-2051. doi: 10.7498/aps.52.2046
    [12] 冯增朝, 赵阳升, 吕兆兴. 二维孔隙裂隙双重介质逾渗规律研究. 物理学报, 2007, 56(5): 2796-2801. doi: 10.7498/aps.56.2796
    [13] 赵 刚, 刘志峰, 张有为, 刘正锋, 王晓宏, 赖远庭. 随机多孔介质逾渗模型渗透率的临界标度性质. 物理学报, 2008, 57(4): 2011-2015. doi: 10.7498/aps.57.2011
    [14] 段东立, 战仁军. 基于相继故障信息的网络节点重要度演化机理分析. 物理学报, 2014, 63(6): 068902. doi: 10.7498/aps.63.068902
    [15] 李炎, 唐刚, 宋丽建, 寻之朋, 夏辉, 郝大鹏. Erds Rnyi随机网络上爆炸渗流模型相变性质的数值模拟研究. 物理学报, 2013, 62(4): 046401. doi: 10.7498/aps.62.046401
    [16] 袁坚, 任勇, 刘锋, 山秀明. 复杂计算机网络中的相变和整体关联行为. 物理学报, 2001, 50(7): 1221-1225. doi: 10.7498/aps.50.1221
    [17] 王 磊, 周淑华, 袁 坚, 任 勇, 山秀明. 虚拟网络行为对互联网整体特性的影响. 物理学报, 2007, 56(1): 36-42. doi: 10.7498/aps.56.36
    [18] 罗植, 杨冠琼, 狄增如. 具有空间因素的社会网络上的舆论形成 . 物理学报, 2012, 61(19): 190509. doi: 10.7498/aps.61.190509
    [19] 刘 锋, 张 军, 山秀明, 任 勇, 马正新. 计算机网络的长程相关特性. 物理学报, 2004, 53(2): 373-378. doi: 10.7498/aps.53.373
    [20] 王建伟, 荣莉莉. 基于负荷局域择优重新分配原则的复杂网络上的相继故障. 物理学报, 2009, 58(6): 3714-3721. doi: 10.7498/aps.58.3714
  • 引用本文:
    Citation:
计量
  • 文章访问数:  182
  • PDF下载量:  3
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-12-24
  • 修回日期:  2019-01-31
  • 上网日期:  2019-03-23
  • 刊出日期:  2019-04-01

相依网络的条件依赖群逾渗

  • 国家数字交换系统工程技术研究中心, 郑州 450000
  • 通信作者: 伊鹏, yipengndsc@163.com
    基金项目: 国家重点研发计划(批准号: 2017YFB0803200, 2018YFB0804002)和国家自然科学基金(批准号: 61802429, 61872382)资助的课题.

摘要: 相依网络鲁棒性研究多集中于满足无反馈条件的一对一依赖, 但现实网络节点往往依赖于多节点构成的依赖群, 即使群内部分节点失效也不会导致依赖节点失效. 针对此现象提出了一种相依网络的条件依赖群逾渗模型, 该模型允许依赖群内节点失效比例不超过容忍度$\gamma $时, 依赖节点仍可正常工作. 通过理论分析给出了基于生成函数方法的模型巨分量方程, 仿真结果表明方程理论解与相依网络模拟逾渗值相吻合, 增大$\gamma $值和依赖群规模可提高相依网络鲁棒性. 本文模型有助于更好地理解现实网络逾渗现象, 对如何增强相依网络鲁棒性有一定指导作用.

English Abstract

    • 现实世界中的许多复杂系统都可以用复杂网络描述, 例如生物神经系统、社交网络、交通系统、互联网等[1-3]. 随着研究人员对复杂网络认识的逐渐深入, 相关研究成果已成为人们理解现实世界复杂系统的重要工具. 但现实生活中的复杂系统通常并不是孤立的, 往往多个系统之间存在相互依赖关系, 这种依赖性会导致网络鲁棒性的急剧下降. 2003年意大利大停电是典型的相依网络级联失效引起的重大生产事故, 最初电网和通信网中极少的节点失效使意大利接近半数的电力设施瘫痪, 数百万人失去电力供应[4]. 在单个网络中, 随着初始删除节点比例增大, 网络巨分量(giant component)连续减小, 整个解体过程呈现出二阶相变, 但在多个相依网络, 巨分量减小的过程多为一阶相变, 表明相依网络的鲁棒性远不如单个网络. 近些年来, 相依网络的鲁棒性开始引起研究人员的重视[3,5-13], 网络鲁棒性研究主要基于经典统计物理的逾渗模型[14], 该模型能准确描述网络解体的相变过程.

      以往关于相依网络鲁棒性的研究主要针对一对一相依节点[12,15-19], 但在现实情况中, 一个节点往往会依赖于多个节点[6], 这多个被依赖节点称为该节点的依赖群. 例如一个通信基站会有多个电厂为其供电, 食物链中一种生物会捕食多种生物. 近年来, 已有学者对存在依赖群的网络展开了研究. Shao等[6]提出了一种耦合网络中存在依赖群的模型, 该模型认为只有当某节点依赖群的全部节点失效后该节点才会失效, 这种依赖模式有效改善了相变点. Wang等[20]研究了网络的群渗流现象, 网络节点的存活取决于其所在超级节点是否连向巨分量, 这种网络模型在一定程度上提高了网络的鲁棒性, 但逾渗类型仍然是一阶相变. Parshani等[7]研究了单个网络中存在依赖群的情况, 发现随着依赖群规模增大网络会变得更加脆弱, 极少数节点失效会导致整个网络崩溃. Wang等[9,21]提出了一种单个网络中存在条件依赖群的模型, 认为当某节点依赖的节点失效数量超过一定比例时该节点才失效, 研究发现随着失效比例阈值增大, 一阶相变甚至会变为二阶相变.

      本文研究了具有多依赖节点的相依网络的逾渗现象, 提出相依网络的条件依赖群逾渗模型并给出巨分量相变方程. 仿真结果表明, 在确定依赖度分布的情况下, 相依网络逾渗模拟结果与方程数值解相吻合, 并且通过增大失效容忍度$\gamma $或依赖群规模可增强网络鲁棒性. 虽然模型对于任意依赖度分布的相依网络不存在二阶相变, 但本文所述逾渗模型对提高相依网络鲁棒性仍具有一定指导作用.

      本文的内容主要包括: 第2部分阐述相依网络的条件依赖群逾渗模型的基本概念; 第3部分通过理论分析给出模型的巨分量相变方程; 第4部分仿真验证理论框架有效性; 第5部分讨论本文研究成果; 第6部分是结论.

    • 传统相依网络逾渗模型多为一对一依赖, 一对一依赖可使网络满足无反馈条件, 便于理论分析[3], 但严格的一对一依赖在现实网络中通常是不存在的, 一个网络节点可能会依赖于另一个网络的多个节点, 若节点依赖的所有节点中有任意一个节点失效, 按照传统模型的分析方法, 该节点也会失效, 如图1所示.

      图  1  具有多依赖关系的相依网络逾渗示意图, 初始攻击导致红色节点失效, 随后发生级联失效过程, 最终相依网络仅有极少数节点存活

      Figure 1.  The model of percolation of interdependent networks with multiple support-dependence relations. The red node fails after the initial attack. Then the cascading failure process leads to a catastrophiccollapse of the interdependent networks. Finally, only a small fraction of nodes survive.

      这种严格的多依赖关系会大幅降低相依网络的鲁棒性, 少部分节点失效就会造成相依网络完全崩溃. 但现实中的网络却没有这么脆弱. 通过观察可以发现, 只要依赖群有部分节点存活则依赖节点仍有效, 例如在某产业链中, 存在生产同类型产品的工厂若干, 其中少部分同类工厂倒闭并不会导致有关产业链的瘫痪[9]. 因此本文提出了一种允许部分相依节点失效的相依网络逾渗模型, 用以描述在部分被依赖节点失效情况下依赖节点仍正常工作的现象, 如图2所示.

      图  2  相依网络的条件依赖群逾渗模型 A网络节点随机依赖于B网络的$\tilde k$个节点($\tilde k \geqslant 0$), 反之亦然; A网络的a节点依赖的3个节点有一个失效, 但失效比例未超过容忍度$\gamma = 0.5$, a节点继续工作; B网络的b节点依赖的节点失效比例超过$\gamma = 0.5$, 所以b节点失效

      Figure 2.  The model of percolation in interdependent networks with conditional dependency clusters. Nodes in network A randomly depends on $\tilde k$ ($\tilde k \geqslant 0$) nodes in network B and vice versa. One of the three nodes which node a in network A depends on fails, but the failure proportion does not exceed $\gamma = 0.5$, node a still works. Two of the three nodes which node b in network B depends on fail, the failure proportion exceeds$\gamma = 0.5$, node bfails.

    • 本文提出的相依网络逾渗模型级联失效过程如下.

      Step 0: 随机删除A网络$1 - p$比例的节点, 与这些节点相连的边也被移除.

      Step 1: A网络中依赖群节点失效比例超过$\gamma $的节点失效, 随后与巨分量失去连接的节点也相继失效.

      Step 2: B网络中依赖群节点失效比例超过$\gamma $的节点失效, 随后与巨分量失去连接的节点也相继失效.

      Step 3: 循环进行Step 2, Step 3直至相依网络中不再有新的节点失效.

      根据生成函数理论[22], 网络的度分布生成函数为${G_0}(x) = \displaystyle\sum\nolimits_k {P(k){x^k}} $, 余度分布生成函数为${G_1}(x) = \displaystyle\sum\nolimits_k {{{P(k)k{x^{k - 1}}}/{\left\langle k \right\rangle }}} $, 其中$P(k)$表示任取一个节点其度为$k$的概率, $\left\langle k \right\rangle $表示网络的平均度. 随机删除网络$1 - p$比例节点后, 令$f$为随机选择一条边连接的节点通向巨分量的概率, 则$f$满足自恰方程

      $f = p\sum\limits_k {\frac{{P(k)k}}{{\left\langle k \right\rangle }}} [1 - {(1 - f)^{k - 1}}] = p\left[ {1 - {G_1}(1 - f)} \right],$

      网络巨分量大小${\mu _\infty }$

      ${\mu _\infty } = p\sum\limits_k {P(k)[1 - {{(1 - f)}^k}] = p[1 - {G_0}(1 - f)]} .$

      对于单个网络, 联立上述两式可解出巨分量的大小. 传统的一对一相依网络求解与单网络相似, 这里直接给出[23]

      $\left\{ \begin{aligned} & \mu _\infty ^{\rm{A}} = p[1 - {G_{{\rm{A}}0}}(1 - {f_{\rm{A}}})][1 - {G_{{\rm{B0}}}}(1 - {f_{\rm{B}}})], \\ & \mu _\infty ^{\rm{B}} = p[1 - {G_{{\rm{B0}}}}(1 - {f_{\rm{B}}})][1 - {G_{{\rm{A}}0}}(1 - {f_{\rm{A}}})], \\ & {f_{\rm{A}}} = p[1 - {G_{{\rm{A}}1}}(1 - {f_{\rm{A}}})][1 - {G_{{\rm{B0}}}}(1 - {f_{\rm{B}}})], \\ & {f_{\rm{B}}} = p[1 - {G_{{\rm{B}}1}}(1 - {f_{\rm{B}}})][1 - {G_{{\rm{A}}0}}(1 - {f_{\rm{A}}})], \end{aligned} \right.$

      其中$\mu _\infty ^i$表示$i$网络巨分量, ${f_i}$表示在$i$网络中任取一边通向巨分量的概率.

      与一对一相依网络情况不同, 本文提出的模型一个节点可依赖多个节点, 只有当某节点依赖的节点失效比例超过容忍度$\gamma $时, 该节点失效, 令${h_i}({\mu _\infty })$表示在$i$网络中随机选择节点的依赖群失效比例不超过$\gamma $的概率, 则本文模型关于巨分量的方程为

      $\left\{ \begin{aligned} & \mu _\infty ^{\rm{A}} = p[1 - {G_{{\rm{A}}0}}(1 - {f_{\rm{A}}})]{h_{\rm{B}}}(\mu _\infty ^{\rm{B}}), \\ & \mu _\infty ^{\rm{B}} = p[1 - {G_{{\rm{B}}0}}(1 - {f_{\rm{B}}})]{h_{\rm{A}}}(\mu _\infty ^{\rm{A}}), \\ & {f_{\rm{A}}} = p[1 - {G_{{\rm{A}}1}}(1 - {f_{\rm{A}}})]{h_{\rm{B}}}(\mu _\infty ^{\rm{B}}), \\ & {f_{\rm{B}}} = p[1 - {G_{{\rm{B1}}}}(1 - {f_{\rm{B}}})]{h_{\rm{A}}}(\mu _\infty ^{\rm{A}}), \end{aligned} \right.$

      其中

      ${h_i}(x) = \sum\limits_{\tilde k} {{{\tilde P}_i}(\tilde k)} \sum\limits_{s = 0}^{\left\lfloor {\tilde k\gamma } \right\rfloor } {\left( \begin{gathered} {\tilde k} \\ s \\ \end{gathered} \right)} {(1 - x)^s}{x^{\tilde k - s}},$

      式中$\left\lfloor {\tilde k\gamma } \right\rfloor $为小于等于$\tilde k\gamma $的最大整数, ${\tilde P_i}(\tilde k)$表示在网络$i$中任取一个节点, 并且该节点依赖于另一个网络$\tilde k$个节点的概率. 通过分析可知, 若取$\tilde P(1) = $1, $\gamma = 0$, 则本文模型与经典一对一相依网络模型[3]一致; 若$\gamma \to 1$($\gamma \ne 1$)时, 意味着只要依赖群内有1个节点存活, 依赖节点仍可以正常工作, 此时(5)式可以改写为${h_i}(x) = \sum\nolimits_{\tilde k} {\tilde P}_i(\tilde k)$$\left[ 1 - {(1 - x)}^{\tilde k} \right] $, 把上式代入(4)式可以得到与文献[6]相同的结果.

      理论上${f_{\rm{A}}}$,${f_{_{\rm{B}}}}$可分别表示为${f_{\rm{A}}} = {\varPsi_1}(p,{f_{\rm{B}}})$,${f_{\rm{B}}} = {\varPsi _1}(p,{f_{\rm{A}}})$, 如果相依网络存在一阶相变点, 则有

      $\frac{{\partial {\varPsi _1}(p_{\rm{c}}^{\rm{I}},f_{\rm{B}}^{\rm{I}})}}{{\partial f_{\rm{B}}^{\rm{I}}}} \cdot \frac{{\partial {\varPsi _2}(p_{\rm{c}}^{\rm{I}},f_{\rm{A}}^{\rm{I}})}}{{\partial f_{\rm{A}}^{\rm{I}}}} = 1,$

      ${f_{\rm{A}}} = {\varPsi _1}(p_{\rm{c}}^{\rm{I}},{f_{\rm{B}}})$${f_{\rm{B}}} = {\varPsi _2}(p_{\rm{c}}^{\rm{I}},{f_{\rm{A}}})$在点$(f_{\rm{A}}^{\rm{I}},f_{\rm{B}}^{\rm{I}})$处相切. 因上式求解较为复杂, 大部分情况下不存在解析解, 为了方便计算, 本文仅考虑具有相同度分布的相依网络, 即A, B网络同分布, 则(4)式简化为

      $\left\{ \begin{aligned} & {\mu _\infty } = p[1 - {G_0}(1 - f)]h({\mu _\infty }), \\ & f = p[1 - {G_1}(1 - f)]h({\mu _\infty }). \end{aligned} \right.$

      对上式第二个式子两边求$f$的导数,

      $p[1 - {G_1}(1 - f)]\frac{{{\rm{d}}h({\mu _\infty })}}{{{\rm{d}}f}} + p\frac{{{\rm{d}}{G_1}(1 - f)}}{{{\rm{d}}f}}h({\mu _\infty }) = 1.$

      通常情况下, 在存在相变点${p_{\rm{c}}}$的相依网络中, 上式在$p = {p_{\rm{c}}}$时存在${\mu _\infty } \geqslant 0$的解, 若只考虑二阶相变点, 则$p = p_{\rm{c}}^{{\rm{II}}}$时应有${f^{{\rm{II}}}} = 0$, $\mu _\infty ^{I{\rm{I}}} = 0$, 把两个值代入上式可得

      $p_{\rm{c}}^{{\rm{II}}}{G'_1}(1)h(0) = 1.$

      对于任意$\tilde P(\tilde k)$分布, 只有当$\gamma = 1$时, $h(0) \ne 0$, 二阶相变点为

      $p_{\rm{c}}^{{\rm{II}}} = \frac{1}{{{{G'}_1}(1)}},$

      这是单个网络的二阶相变点, $\gamma = 1$意味着两个网络之间不存在相依关系, 逾渗类型转变为单网络普遍存在的二阶相变. 上述关于相变点的理论分析表明, 对于任意依赖度分布, 本文提出的相依网络模型不存在二阶相变点($\gamma = 1$除外).

    • 随机规则(random regular, RR)网络的度分布生成函数为${G_0}(x) = {x^{\left\langle k \right\rangle }}$, 余度分布生成函数为${G_1}(x) = {x^{\left\langle k \right\rangle - 1}}$. 假设两个RR网络具有相同的分布, 那么将两个生成函数代入(7)式可得方程

      $\left\{ \begin{aligned} &{\mu _\infty } = p[1 - {(1 - f)^{\left\langle k \right\rangle }}]h({\mu _\infty }), \\ & f = p[1 - {(1 - f)^{\left\langle k \right\rangle - 1}}]h({\mu _\infty }). \end{aligned} \right.$

      对于任意$\tilde P(\tilde k)$分布求解逾渗方程较为复杂, 本文只考虑依赖群规模固定的情况. 图3是不同$\gamma $取值的RR-RR相依网络逾渗的仿真结果.

      图  3  不同$\gamma $取值的RR-RR相依网络逾渗, 每个网络节点数$N = 200000$, 平均度$\left\langle k \right\rangle = 6$, $\tilde P(10) = 1$, 空心标记为仿真值, 实线为逾渗方程数值解 (a) 巨分量${\mu _\infty }$$p$对应关系; (b) 级联失效迭代次数(number of iterations, NOI)

      Figure 3.  The results of the percolation of RR-RR interdependent networks for different $\gamma $, each network has 200000 nodes, average degree is 6, $\tilde P(10) = 1$. The symbols represent the simulation results, and the solid linesshow the corresponding analytical predictions. (a) The size ofthe giant component ${\mu _\infty }$versus $p$; (b) number of iterations.

    • Erdös-Rényi (ER)网络[24]的度分布与余度分布生成函数相同, 都为${G_0}(x) = {G_1}(x) = {{\rm{e}}^{ - \left\langle k \right\rangle (1 - x)}}$, 假设两个ER网络具有相同的分布, 那么将两个生成函数代入(7)式可得方程

      $\left\{ \begin{aligned} & {\mu _\infty } = p[1 - {{\rm{e}}^{ - \left\langle k \right\rangle {\mu _\infty }}}]h({\mu _\infty }), \\ & f = p[1 - {{\rm{e}}^{ - \left\langle k \right\rangle f}}]h({\mu _\infty }). \end{aligned} \right.$

      因为ER网络度分布与余度分布生成函数相同, 所以${\mu _\infty } = f$, 则上式可进一步简化为

      $f = p[1 - {G_0}(1 - f)]h(f),$

      上式即为相同度分布的ER-ER相依网络巨分量方程. 定义$D(f)$如下:

      $D(f) = p[1 - {G_0}(1 - f)]h(f) - f,$

      随着$p$值发生变化, $D(f)$会与横轴相切, 相切时$p$的取值${p_{\rm{c}}}$为相变点. 图4为同分布ER-ER相依网络相变点数值解, 图5为不同$\gamma $取值的ER-ER相依网络逾渗的仿真结果.

      图  4  不同$\gamma $值对应的ER-ER相依网络相变点, 网络平均度$\left\langle k \right\rangle = 6$, $\tilde P(10) = 1$

      Figure 4.  Graphical solutions of ER-ER interdependent networks transition for different $\gamma $. The average degree is 6, $\tilde P(10) = 1$.

      图  5  不同$\gamma $取值的ER-ER相依网络逾渗, 每个网络节点数$N = 200000$, 平均度$\left\langle k \right\rangle = 6$, $\tilde P(10) = 1$, 空心标记为仿真值, 实线为逾渗方程数值解 (a) 巨分量${\mu _\infty }$$p$对应关系; (b) 级联失效迭代次数

      Figure 5.  The results of the percolation of ER-ER interdependent networks for different $\gamma $, each network has 200000 nodes, average degree is 6, $\tilde P(10) = 1$. The symbols represent the simulation results, and the solid linesshow the corresponding analytical predictions. (a) The size ofthe giant component ${\mu _\infty }$ versus $p$; (b) number of iterations.

      图6图7分别对比了ER-ER相依网络不同${\tilde P_i}(\tilde k)$分布的逾渗结果和不同$\gamma $取值的相变点.

      图  6  不同依赖度分布的ER-ER相依网络逾渗, $\tilde P(10) = 1$, $\tilde P(5) = 1$分别用实心和空心标记表示, 每个网络节点数$N = 200000$, 平均度$\left\langle k \right\rangle = 6$ (a) 巨分量${\mu _\infty }$$p$对应关系; (b) 级联失效迭代次数

      Figure 6.  The results of the percolation of ER-ER interdependent networks for different dependency degrees, each network has 200000 nodes, average degree is 6. The dependency degrees are $\tilde P(10) = 1$ (solid symbols) and $\tilde P(5) = 1$ (empty symbols). (a) The size ofthe giant component ${\mu _\infty }$ versus $p$; (b) number of iterations.

      图  7  不同$\gamma $取值的ER-ER相依网络相变点, 空心标记为仿真结果, 实线是理论值

      Figure 7.  The critical point ${p_{\rm{c}}}$ versus $\gamma $ of ER-ER interdependent networks, The symbols represent the simulation results, and the solid linesshow the corresponding analytical predictions.

    • 无标度网络(scale free network, SF)是指服从于$P(k) = c{k^{ - \lambda }}$分布的随机网络, 它的度分布生成函数和余度分布生成函数可以分别近似为[12]:

      ${G_0}(x) = \sum\limits_{{k_{\min }}}^{{k_{\max }}} {\left[ {{{\left( {\frac{{{k_{\min }}}}{k}} \right)}^{\lambda - 1}} - {{\left( {\frac{{{k_{\min }}}}{{k + 1}}} \right)}^{\lambda - 1}}} \right]} {x^k},$

      ${G_1}(x) = {{\sum\limits_{{k_{\min }}}^{{k_{\max }}} {k\left[ {{{\left( {\frac{{{k_{\min }}}}{k}} \right)}^{\lambda - 1}} - {{\left( {\frac{{{k_{\min }}}}{{k + 1}}} \right)}^{\lambda - 1}}} \right]} {x^{k - 1}}}/{\left\langle k \right\rangle }},$

      将两个生成函数代入(7)式可求出巨分量. 图8给出了不同$\gamma $取值的SF-SF相依网络逾渗仿真结果.

      图  8  不同$\gamma $取值的SF-SF相依网络逾渗, 每个网络节点数$N = 200000$, 平均度$\left\langle k \right\rangle = 6$, $\lambda = 2.7$, $\tilde P(10) = 1$, 空心标记为仿真值, 实线为逾渗方程数值解 (a) 巨分量${\mu _\infty }$$p$对应关系; (b) 级联失效迭代次数

      Figure 8.  The results of the percolation of SF-SF interdependent networks for different $\gamma $, each network has 200000 nodes, average degree is 6, $\lambda = 2.7$, $\tilde P(10) = 1$. The symbols represent the simulation results, and the solid linesshow the corresponding analytical predictions. (a) The size ofthe giant component ${\mu _\infty }$ versus $p$; (b) number of iterations.

    • 上一节中针对不同的$\gamma $值分别对RR-RR, ER-ER和SF-SF三种相依网络进行了逾渗仿真, 对仿真结果的分析如下.

      1) 对于三种相依网络, 随着$\gamma $取值增大网络鲁棒性逐渐提高. $\gamma $值表示对相依节点失效的容忍程度, 较大$\gamma $意味着即使某节点的较多依赖节点失效, 该节点仍正常工作.

      2) 通过观察图3, 图5以及图8的仿真结果可以看出, 在本文选取的$\gamma $值范围内, 三种相依网络皆不存在二阶相变, 这与理论分析的结果吻合.

      3) 图4给出了不同$\gamma $值ER-ER相依网络的相变点的数值解, 其中$\gamma = 1$时网络的相变点与单个ER网络的相变点相同, 这说明$\gamma = 1$解耦合了两个相依网络, 节点之间不再存在相互依存关系.

      4) 图6结果表明在相同$\gamma $值的情况下, 随着依赖群平均规模的增大网络鲁棒性整体呈上升趋势. 根据(5)式可知, 保持$\gamma $值不变, 增大某节点依赖群规模可以使失效组合增多从而降低该节点相依失效的概率.

      5) 图7中相变点曲线呈阶梯状, 主要因为(5)式中对$\tilde k\gamma $进行了向下取整操作, 所以在$\gamma $的某取值区间内${p_{\rm{c}}}$值保持不变. 从图中还可以看出, 随着依赖群规模增大, ${p_{\rm{c}}}$呈整体下降趋势, 意味网络的鲁棒性得到提高.

      根据本文理论分析与仿真结果可知, 可从两个方面提高多依赖相依网络鲁棒性:

      1) 提高失效容忍度$\gamma $, 即增加被依赖节点的相互可替代性, 保证即使某节点的依赖节点只有少量存活, 仍可以支撑该节点的正常运行;

      2) 增加依赖节点的数量, 若某节点存在更多的依赖节点, 则在相同$\gamma $值的情况下存活节点组合更多, 从而提高该节点存活的概率.

    • 相依网络的鲁棒性正在逐渐引起人们的重视, 现实网络中节点往往会依赖于多个节点, 按照传统相依网络逾渗理论, 多依赖性通常会降低网络鲁棒性, 但现实网络并未因此变得更脆弱. 为了更好地描述现实网络中的这种现象, 提出了一种相依网络的条件依赖群逾渗模型, 该模型允许在部分被依赖节点失效情况下依赖节点仍正常工作. 本文在逾渗模型的基础上, 利用生成函数理论[25]给出了上述具有任意度分布模型的巨分量方程, 通过对三种相依网络模拟仿真可看出方程的数值解与模拟值相吻合, 验证了理论的有效性. 虽然理论分析发现对于任意依赖度分布的相依网络模型, 无论$\gamma $取任何值($\gamma = 1$除外)都不存在二阶逾渗相变, 但仿真结果仍表明随着$\gamma $取值增大网络鲁棒性会逐渐提高. 此外, 对比不同依赖度分布的仿真, 在相同$\gamma $值的情况下, 随着依赖节点的增多, 网络鲁棒性也会相应地提升. 本文的研究结果对提高现实世界相依系统鲁棒性具有一定的科学指导意义, 同时也为后续具有多依赖关系的相依网络研究提供了借鉴.

参考文献 (25)

目录

    /

    返回文章
    返回