-
近年来,针对复杂网络的研究[1-4]多以单一的复杂网络为主,而现实生活中不会存在绝对孤立的网络。如某一系统发生故障,可能会引发相关系统的故障,从而反过来引发自身故障,导致严重后果[5-6]。2010年,文献[7]在Nature上发表的关于相依网络的研究,将人们对于提高相依网络鲁棒性研究推向新高潮。文献[8]研究了两个网络之间的耦合强度变化对于渗流相变的影响,进而提高了网络的鲁棒性。文献[9]研究了网络的鲁棒性与网络的耦合强度,以及子网络耦合边之间的影响。文献[10]发现当网络受攻击的节点为耦合节点时,网络更易发生级联失效。文献[11]发现相依网络存在网间相似性(inter- similarity),并提出两种高网间相似性的相互依存网络构建方法。另外,一些学者也对如何提高相依网络的鲁棒性进行了研究[12-17]。但在不改变原网络功能的基础上,改善网络的拓扑结构,提高网络的鲁棒性方面的研究仍然较少,如对已有网络进行适当加边来提高网络的鲁棒性。文献[18]针对单一网络提出了低极性加边策略LPS,通过加边,提高网络度分布均匀性,改善了网络的鲁棒性。文献[19]根据相依节点的度数差异,将子网络内度数差较小的节点进行连接,以此提高网络的鲁棒性。但这些策略大多针对单一网络或子网络内部进行研究,而未考虑相依网络中相依节点的特殊性。
本文受此启发,根据相依节点的特殊性,以及部分相依与一对一全相依时网络的差异性,得出两种新型加边策略:1)低相对介数内加边策略${\text{(BA}} - {\text{BB)}}$;2)低相对介数耦合加边策略$({\text{BA}} - {\text{XY}})$。与上述文献中常用的3种加边策略进行对比分析,仿真结果表明:对于部分相依网络,${\text{BA}} - {\text{BB}}$策略能更好地改善网络的鲁棒性,且相依比例越小,效果越好;对于一对一全相依的网络,${\text{BA}} - {\text{XY}}$策略能更好地改善网络鲁棒性。
-
本文根据文献[20]的研究成果,对边负载容量动态模型进行改进,将其应用于节点上。节点$i$的容量${C_i}$一般正比于其初始负荷${L_i}$,即:
$${C_{{A_i}}} = (1 + \beta ){L_{{A_i}}}, \;\;{C_{{B_i}}} = (1 + \beta ){L_{{B_i}}}$$ (1) $${L_{{A_i}}} = k_{{A_i}}^\alpha ,\;\;{L_{{B_i}}} = k_{{B_i}}^\alpha $$ (2) 式中,$\beta $为容忍系数,$\beta $越大,网络抵挡级联故障的能力越强;${L_{{A_i}}}$和${L_{{B_i}}}$分别表示子网络$A$以及$B$中节点$i$的度值;$\alpha $为可变参数,用于调节节点的初始负载的强度;若子网络$A$中的一个节点$i$发生故障,则发生故障的节点$i$的负载需要分配给其周边节点,且发生故障失效的节点$i$的邻接节点$j$需要承担的负载$\mathop {\Delta L}\nolimits_{\mathop A\nolimits_j \mathop A\nolimits_i } $的值与它本身的负载值成比例,即:
$$\Delta {L_{{A_j}{A_i}}} = {L_{{A_i}}}{L_{{A_j}}}/\sum\nolimits_{{A_a} \in \mathit{\Gamma } {A_i}} {{L_{{A_a}}}} $$ (3) 式中,${\mathit{\Gamma } _{{A_i}}}$表示与该节点相邻的邻居节点的集合。
相互耦合的网络与单个网络之间存在一定的差别,据此,本文提出相对介数${\text{BB}}$,即:
$${\text{B}}{{\text{B}}_A}_{_i} = B_{{A_i}}^\theta * B_{{B_i}}^\gamma , \;\;{\text{B}}{{\text{B}}_B}_{_i} = B_{{B_i}}^\theta * B_{{A_i}}^\gamma $$ (4) 式中,${B_{{A_i}}}$表示子网络$A$中节点$i$的介数;${B_{{B_i}}}$表示子网络$B$中节点$i$的介数。节点${A_i}$和${B_i}$为两个耦合的节点;$\theta $和$\gamma $为可选的变量参数,改变$\theta $和$\gamma $的值,使其更接近网络的相依特性。
当某一子网络中节点$i$没有相依节点,那么定义它的相对介数为:
$${\text{B}}{{\text{B}}_i} = nB_i^m$$ (5) 式中,${B_i}$位节点$i$的介数;$m,n$是可选择的参数。
-
定义相依网络进行随机攻击的节点比例是$p$,定义$G$为网络受到攻击发生级联失效后,未发生故障而失效节点占网络总节点的比例,即:
$$G = ({N'_A} + {N'_B})/({N_A} + {N_B})$$ (6) 式中,${N_A}$和${N_B}$分别表示级联失效前子网络中的节点数目;${N'_A}$和${N'_B}$分别表示网络发生级联失效故障后,两个子网络中节点数目。
此外,定义${p_c}$表示耦合网络不全面崩溃时,能够承受的相对最大受攻击节点比例,当攻击比例大于该值时,网络的鲁棒性相对稳定;${p_c}$越大,表明网络的鲁棒性越好。
-
本文采用两种网络模型,一种为部分耦合网络模型,子网络$A$和子网络$B$含有相同数目的节点,$F$表示相依网络的耦合比例。在子网络中分别选取一定比例$F$的网络节点,将它们进行随机的一对一耦合。图 1是两个相互独立的网络构成的相依网络示意图。其中,$\{ A1,A2,A3,A4\} $为子网络$A$中的节点,$\{ B1,B2,B3,B4\} $为子网络$B$中的节点,实线为节点发生故障后网络间连接的线,虚线为节点发生故障后网络断开的线,黑色圆圈表示为未发生故障的有效节点,白色圆圈表示该节点发生了故障而失效。系统初始状态如图 1a所示,假设$A$网络中的$A2$节点受到攻击后发生故障失效,它的负载应按照一定比例分配给与之相邻的节点$A1$、$A3$,与之相耦合的$B2$也立即发生故障,则与$A2$和$B2$相连的边也随之发生故障变成虚线,如图 1b所示。假设节点在进行负载重新分配后,$A{\text{1}}$、$A{\text{3}}$和$B1$、$B3$的负载都没有超出其负载的容量。检查剩余的节点是否处于最大联通片中,$A1$和$B1$两个节点因为不在网络的最大连通片中,从而发生失效,$A{\text{3}}$、$A4$和$B3$、$B4$节点处在网络的最大连通片中,因此未发生故障。最终网络达到一个平衡点,如图 1c所示。
另一种为文献[8]提出的一对一全耦网络模型,即子网络$A$的每一个节点与子网络$B$中的每一个节点随机一对一相连,同时其级联失效的过程与部分耦合网络失效过程类似。
-
本文选择${\text{BA}}$无标度网络来作为子网络,依次构建节点部分耦合和一对一全耦合的相依网络模型来研究加边策略对于网络鲁棒性的影响,其中子网络$A$与子网络$B$的参数为:${N_A} = {N_B}$,平均度$ < k > $。考虑成本约束,本文提出加边比例${f_a}$,即:
$${f_a} = M'/({M_A} + {M_B})$$ (7) 式中,$M'$表示加边数目;${M_A}$表示子网络$A$的所有边的数目;${M_B}$表示子网络$B$的所有边的数目。同时本文选取$\theta = \gamma = 0.5$,$m = 1$,$n = 0.5$进行研究。
-
为了探索复杂网络抵御级联失效的鲁棒性与采用不同加边策略和不同加边数目的关系,本文通过MATLAB平台进行了仿真研究,其中子网络的参数取值为${N_A} = {N_B} = 200$、$\alpha = 2.5$、$\beta = 1$,相依比例参数依次取$F = $0.3、0.5、0.6、0.7,加边比例参数取${f_a} = $40%、80%。图 2是在不同条件下,网络鲁棒性参数$G$与攻击比例$p$的关系图,其中黑色虚线BA-BA为未采用加边策略时网络鲁棒性。
由图 2可知,在网络耦合比例一致的情况下,随着网络加边比例的增加,耦合网络所能承受的最大攻击比例${p_c}$值也随着增大,即网络的鲁棒性与其呈正比,且采用${\text{BA}} - {\text{BB}}$策略进行改良的网络所能承受的最大攻击比例${p_c}$值一直大于另外两种策略。对于进行部分耦合的相依网络,当对于网络进行加边的比例一定的时候,随着相依比例的增加,网络发生级联失效的概率增加,但是采用${\text{BA}} - {\text{BB}}$策略进行改进的网络,其鲁棒性参数$G$和${p_c}$值也一直优于其他两种策略。
综合以上分析可知,对于部分耦合的相依网络,当网络的拓扑结构一定时,采用本文的策略,即低相对介数内加边策略${\text{BA}} - {\text{BB}}$能够更加有效地提高网络的鲁棒性。
为了进一步探索不同加边策略与网络鲁棒性的关系,本文选择了当攻击比例是0.2时,不同耦合比例的网络,其面对级联失效的鲁棒性与$\alpha $之间的关系。由图 3可以看出,随着$\alpha $的变化,网络的抵御级联失效的鲁棒性呈上升的趋势。当网络的耦合比例$F = 0.3$和0.5时,在$ - 5 < \alpha < 5$的变化区间上,${\text{BA}} - {\text{BB}}$策略对于网络鲁棒性的改善普遍好于${\text{BA}} - {\text{XY}}$策略,尤其是在$ - 1 < \alpha < 1$时,${\text{BA}} - {\text{BB}}$策略对于网络的改善明显优于${\text{BA}} - {\text{XY}}$策略。由图 3c、3d可见,当选取的网络的耦合比例相对较大时,随着$\alpha $值的不断变化,采用不同的加边策略会对网络的鲁棒性产生一定的波动。当网络的耦合比例$F = 0.6$和0.7,$ - 5 < \alpha < - 1$时,${\text{BA}} - {\text{XY}}$的加边效果却好于${\text{BA}} - {\text{BB}}$的,而当$ - 5 < \alpha < - 1$时,网络节点的异质性较低,这对于选取更优的加边方式来改善网络具有重要意义。将图 3的4幅图进行对比可见,当${\text{0}} < \alpha < 5$,随着网络的耦合比例的不断增加,在${\text{BA}} - {\text{BB}}$策略下,网络抵御级联失效的鲁棒性一直处于更优的状态,且相对比较稳定。
-
为了进一步研究不同耦合方式对于网络鲁棒性的影响,本节选用子网络参数为:${N_A} = {N_B} = 200$,$ < k > \approx 4$,$\alpha = 0.5$,$\beta = 1.5$,研究其在加边比例${f_a}$为20%、40%、60%、80%时,网络鲁棒性随着攻击比例$p$的变化情况。
图 4为不同加边比例下,加边策略对网络的鲁棒性$G$的影响,其中黑色虚线BA-BA为未采用加边策略时网络鲁棒性。由图 4可见,随着网络加边比例的不断增加,网络抵御级联失效的鲁棒性也随之不断增加,采用加边策略后,网络所能承受的最大攻击比例${p_c}$也随之增加。其次,当采用4种不同加边比例时,采用${\text{BA}} - {\text{BB}}$和${\text{BA}} - {\text{XY}}$策略对于网络抵御级联失效的鲁棒性的改善都优于${\text{BA}} - {\text{K}}$策略。同时,与部分耦合的相依网络研究时情况不同,采用${\text{BA}} - {\text{XY}}$策略的网络相比于采用${\text{BA}} - {\text{BB}}$策略的网络,其网络的鲁棒性更优。这也进一步证明,不同耦合方式下的相依网络对于网络加边策略的合理选取具有很大影响。
图 5为不同加边比例与加边策略下,负载参数α对网络鲁棒性G的影响。当$ - 5 < \alpha < 1$时,在不同的加边方式下,网络抵御级联失效的鲁棒性与$\alpha $的值总体呈正比例关系,且采用${\text{BA}} - {\text{XY}}$加边策略对于网络鲁棒性改善效果明显优于${\text{BA}} - K$和${\text{BA}} - {\text{BB}}$策略;对比图 5a、5c和5b、5d,可以发现,当$1 < \alpha < 5$时,随着攻击比例的增大,网络的鲁棒性波动也逐渐增大,而当$ - 5 < \alpha < 1$时,网络的鲁棒性总体处于相对平稳状态;纵观图 5的4幅图,可以发现当$ - 1 < \alpha < 1$,3种不同的加边策略都呈现显著的提升。这也进一步证明了网络的负载参数$\alpha $能很大程度上影响网络加边策略的优劣。
图 6为不同加边策略对网络鲁棒性G的影响,其中虚线BA-BA为未采用加边策略时网络鲁棒性。当网络加边比例${f_a} = 20\% $时,攻击比例$p$不论采取何值,采用${\text{BA}} - {\text{XY}}$策略的网络抵御级联失效的鲁棒性都优于${\text{BA}} - {\text{LIDD}}$策略。而由图 6b可以发现,在加边比例${f_a} = 40\% $情况下,攻击比例$p > 0.5$时,采用${\text{BA}} - {\text{XY}}$策略的网络抵御级联失效的鲁棒性,明显优于${\text{BA}} - {\text{LIDD}}$策略。这是由于本文提出的${\text{BA}} - {\text{XY}}$加边策略充分综合了一对一全相依情况下相依网络具有的特殊性,以及相依网络中耦合节点的特点,进而可以有效地改善网络的鲁棒性。
Research of the Link Addition Strategies for Improving the Robustness of Interdependent Networks
-
摘要: 网络结构对于网络的鲁棒性能具有一定影响。该文针对不同耦合方式的相依网络,研究了网络鲁棒性与加边策略之间的关系。对采用部分耦合和一对一全耦合的相依网络模型,分别提出了低相对介数内加边策略和低相对介数耦合加边策略,并将其与已有的几种策略进行仿真对比,仿真结果表明了该文所提策略的有效性。此外,进一步探究了负载参数对于加边策略的影响。研究发现,随着负载参数的不断增加,采用加边策略后,网络鲁棒性普遍提高,但选取不同的负载参数,可能会导致某一种加边策略无效。因此,综合考虑负载参数、选取适当的加边策略,能够更好地提高网络抵御级联失效的鲁棒性。研究成果对于有效使用资源,优化相依网络的拓扑结构,提高相依网络抵御级联失效的鲁棒性具有一定的指导作用。Abstract: Different network structures have some influence on the robustness of the network. In view of the different interdependent network structures, the influence of different edge adding strategies on network robust performances are studied. For partial coupling and one-to-one full-coupled networks, different adding edge strategies, i.e. the internal link additional strategy of low relative betweenness and the coupling link additional strategy of low relative betweenness, are proposed respectively and compared with several existing link addition strategies. The simulation results show the effectiveness of the proposed strategies. In addition, the effects of load parameters on link addition strategies are further studied. Simulation results show that with the increase of load parameters, the robustness of the added network is increasing. However, different load parameters may lead to failure of a link additional strategy. Therefore, it is better to improve the robustness of the network by fully considering the value of load parameters and selecting the appropriate adding method. The research results can provide a guidance on how to allocate limited resources to optimize topology of interdependent networks and improve the robustness of interdependent networks
-
Key words:
- interdependent network /
- link addition strategy /
- robustness /
- topology
-
[1] JUN L, QING Y X, XIN S, et al. Load-redistribution strategy based on time-varying load against cascading failure of complex network[J]. Chinese Physics B, 2015, 24(7):076401. doi: 10.1088/1674-1056/24/7/076401 [2] HU P, FAN W, MEI S. Identifying node importance in complex networks[J]. Physica A:Statistical Mechanics and Its Applications, 2015, 429:169-176. doi: 10.1016/j.physa.2015.02.002 [3] QIAN Y, WANG B, XUE Y, et al. A simulation of the cascading failure of a complex network model by considering the characteristics of road traffic conditions[J]. Nonlinear Dynamics, 2015, 80(1-2):413-420. doi: 10.1007/s11071-014-1878-z [4] HONG S, LV C, ZHAO T, et al. Cascading failure analysis and restoration strategy in an interdependent network[J]. Journal of Physics A:Mathematical and Theoretical, 2016, 49(19):195101. doi: 10.1088/1751-8113/49/19/195101 [5] VESPIGNANI A. Complex networks:the fragility of interdependency[J]. Nature, 2010, 464(7291):984-985. doi: 10.1038/464984a [6] BOBBIO A, BONANNI G, CIANCAMERLA E, et al. Unavailability of critical SCADA commun ication links interconnecting a power gridand a Telco network[J]. Reliability Engineering & System Safety, 2010, 95(12):1345-1357. https://www.sciencedirect.com/science/article/pii/S0951832010001456 [7] BULDYREV S V, PARSHANI R, PAUL G, et al. Catastrophic cascade of failures in inter dependent networks[J]. Nature, 2010, 464(7291):1025-1028. doi: 10.1038/nature08932 [8] PARSHANI R. Interdependent networks:Reducing the coupling strength leads to a change from a first to second order percolation transition[J]. Physical Review Letters, 2010, 105(4):113-113. doi: 10.1103-PhysRevLett.105.048701/ [9] 陈世明, 邹小群, 吕辉, 等.面向级联失效的相依网络鲁棒性研究[J].物理学报, 2014, 63(2):257-264. http://d.old.wanfangdata.com.cn/Periodical/wlxb201402057 CHEN Shi-ming, ZOU Xiao-qun, LÜ Hui, et al. Researchon robustness of interdependent network for suppressing cascading failure[J]. Acta Phys Sin, 2014, 63(2):257-264. http://d.old.wanfangdata.com.cn/Periodical/wlxb201402057 [10] LIU R R, JIA C X, ZHANG J L, et al. Robustness of interdependent networks under several intentional attack strategies[J]. Journal of University of Shanghai for Science and Technology, 2012, 34(3):235-239. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=shlgdxxb201203004 [11] DU Y, GAO C, HU Y, et al. A new method of identifying influential nodes in complex networks based on TOPSIS[J]. Physica A:Statistical Mechanics & Its Applications, 2014, 399(4):57-69. https://www.sciencedirect.com/science/article/pii/S0378437113011552 [12] HUANG X, GAO J, BULDYREV S V, et al. Robustness of interdependent networks under targeted attack[J]. Physical Review E Statistic al Nonlinear & Soft Matter Physics, 2011, 83(2):778-804. https://arxiv.org/abs/1010.2160 [13] DONG G G, GAO J X, DU R J, et al. Robustness of network of networks under targeted attack[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2013, 87(5):936-938. http://d.old.wanfangdata.com.cn/OAPaper/oai_arXiv.org_1209.4897 [14] SHAO J, BULDYREV S V, HAVLIN S, et al. Cascade of failures in coupled network systems with multiple support-dependence relations[J]. Physical Review E, 2011, 83(3):1127-1134. doi: 10.1103-PhysRevE.83.036116/ [15] SCHNEIDER C M, YAZDANI N, ARAÚJO N A, et al. Towards designing robust coupled networks[J]. Physics, 2013, 3(24):1969. http://d.old.wanfangdata.com.cn/OAPaper/oai_arXiv.org_1106.3234 [16] 陈世明, 吕辉, 徐青刚, 等.基于度的正/负相关相依网络模型及其鲁棒性研究[J].物理学报, 2015(4):359-369. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=wlxb201504052 CHEN Shi-ming, LÜ Hui, XU Qing-gang, et al. The model of interdependent network based on positive/negative correlation of the degree and its robustness study[J]. Acta Phys Sin, 2015(4):359-369. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=wlxb201504052 [17] WANG J, JIANG C, QIAN J. Robustness of interdependent networks with different link patterns against cascading failures[J]. Physica A:Statistical Mechanics & Its Applications, 2014, 393(1):535-541. doi: 10.1016/j.physa.2013.08.031 [18] CAO X B, HONG C, DU W B, et al. Improving the network robustness against cascading failures by adding links[J]. Chaos Solitons & Fractals, 2013, 57(4):35-40. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=1e9bef1dc4d237e10147157fd61a8862 [19] JI X P, WANG B, LIU D, et al. Improving interdependent networks robustness by adding connectivity links[J]. Physica A:Statistical Mechanics and Its Applications, 2016, 444:9-19. doi: 10.1016/j.physa.2015.10.010 [20] 陈世明, 庞少鹏, 邹小群, 等.面向级联失效的加权网络负载容量非线性模型鲁棒性优化[J].控制与决策, 2013, 28(7):1041-1045. http://d.old.wanfangdata.com.cn/Periodical/kzyjc201307015 CHEN Shi-ming, PANG Shao-peng, ZOU Xiao-qun, et al. Robustness optimization of load-capacity nonlinear model in weighted network for cascading failure[J]. Control and Decision, 2013, 28(7):1041-1045. http://d.old.wanfangdata.com.cn/Periodical/kzyjc201307015 [21] JIANG Z Y, LIANG M G, ZHANG S, et al. An efficient bandwidth allocation strategy for scale-free networks[J]. International Journal of Modern Physics C, 2012, 23(10):1250065. doi: 10.1142/S0129183112500659 [22] BEYGELZIMER A, GRINSTEIN G, LINSKER R, et al. Improving network robustness by edge modification[J]. Physica A:Statistical Mechan ics & Its Applications, 2005, 357(3):593-612. doi: 10.1016-j.physa.2005.03.040/