-
随着社会和科技的发展,现实中各事物的联系越来越多,这些联系都可以用网络系统来描述。随着这些关系变得错综复杂,逐渐产生了两个甚至多个系统之间的联系,形成相互依存网络。为衡量相互依存网络在级联失效过程中的鲁棒性,需要一个能准确衡量鲁棒性的测度指标。目前大部分网络鲁棒性研究都直接采用攻击后最大连通子图比例作为鲁棒性指标,该指标虽能较合理反映网络鲁棒性,但在实际应用时也因适用性和准确性的问题而常被诟病。此外,目前大多数鲁棒性指标都是针对单一网络,专门针对相互依存网络鲁棒性评价指标的探讨却较少。因此,有必要对常用鲁棒性指标进行准确性和适用性的探讨,并对相互依存网络的特点进行分析,提出新的相互依存网络鲁棒性指标。
本文对几个常用的具有代表性的鲁棒性指标进行分析,针对一般相依网络级联失效过程,提出了最大连通子图相对效能比的鲁棒性度量指标。通过相互依存网络级联失效模型的攻击实验表明,相比于现有常用指标,该指标能更准确地衡量相依网络在级联失效过程中的鲁棒性变化,在大规模的网络中具有明显优势,可适用于相依网络中基于仿真的鲁棒性分析。
-
为了使研究更具代表性,同时降低研究的复杂性,本文只考虑由两个网络构成的相依网络,且根据一对一相依关系来构建相依网络模型。
根据复杂网络理论,相依网络一般用基于图论的数学模型来表示[16]。单个网络用图
$G(V,E)$ 来表示,其中V是图中所有节点的集合,E是图中所有边的集合。对于两层相依网络,其子网络分为网络A和网络B,分别记为${G_A}({V_A},{{{E}}_A})$ 和${G_B}({V_B},{{{E}}_B})$ 。为了描述相依网络中网络间的相依关系,需额外构建矩阵来表示网络间节点相依边的邻接矩阵。则相依网络可以表示为${G_{AB}}({G_A},{G_B},{{{E}}_{AB}},{{{E}}_{BA}})$ ,其中${{{E}}_{AB}}$ 、${{{E}}_{BA}}$ 是网络A与网络B之间相依关系的邻接矩阵,设两个网络的节点数分别为${N_A} = m,{N_B} = n$ ,则以${{{E}}_{AB}}$ 为例可表示为规模$m \times n$ 的矩阵:$${{E}_{AB}}{\rm{ = }}\left[ {\begin{array}{*{20}{c}} {{e_{1,1}}}&{{e_{1,2}}}& \cdots &{{e_{1,n}}} \\ {{e_{2,1}}}&{{e_{2,2}}}& \cdots &{{e_{2,n}}} \\ \vdots & \vdots & {} & \vdots \\ {{e_{m,1}}}&{{e_{m,2}}}& \cdots &{{e_{m,n}}} \end{array}} \right]$$ 式中,
${e_{i,j}}$ 表示网络A中节点i与网络B中节点j的相依关系,若存在相依关系,${e_{i,j}} = 1$ ,否则${e_{i,j}} = 0$ 。本文研究一对一相依网络,则网络模型可以在上述表达式的基础上做一些简化处理。首先,一对一相依网络具有对称性,其两个子网络的节点数相同,即
${N_A} = {N_B}$ 。其次,设${N_A} = {N_B} = N$ ,则一对一相依网络的相依关系邻接矩阵${{{E}}_{AB}}$ 、${{{E}}_{BA}}$ 的规模都是$N \times N$ ,并且满足${{{E}}_{AB}} = {{E}}_{BA}^{\rm{T}}$ 。因此一对一相依网络模型可以简化为${G_{AB}}({G_A},{G_B},{{{E}}_{AB}})$ 。 -
级联失效是复杂网络中的一种典型的故障传播模式。网络中,在一个或部分节点因故障失效后,会通过相依关系使相依节点发生失效,进而引发其他节点接连失效,产生级联效应,最终导致网络大面积崩溃甚至完全崩溃。本文采用一般相依网络级联故障模型,根据此模型可以得出节点失效的情况如下:1) 节点受到随机或蓄意的直接攻击影响而失效;2) 一个节点的失效导致与其相依的节点失去了相依关系而失效;3) 随着节点的失效导致网络中一些节点脱离了最大连通子图,失去了与网络大部分节点的联系,导致这些节点即使没有被直接攻击也会失效。
相依网络级联失效过程如下:
1) 攻击相依网络中的一个或一定比例的节点,由于网络的相依性,与该节点相依的节点也会失效(之后任何节点失效时都伴随其相依节点失效)。
2) 检查剩余网络,如果有节点脱离了最大连通子图,该节点也视为失效。
3) 如果在步骤2)中有节点失效,则重复步骤2),否则级联失效结束。
上述过程如图1所示,其中,相依网络由网络A和网络B构成。假设对节点A5进行攻击,使A5失效,从网络A中移除与A5相连的边,则与其相依的节点B5因失去了相依关系而失效,从网络B中移除与B5相连的连接边,此时网络达到阶段1的状态。随后,随着A5的失效,节点A6脱离了网络A的最大连通分量成为孤立节点,导致其与其他节点失去联系而失效,对应地其相依节点B6失效。同理节点B4成为孤立节点而失效,其相依节点A4失效。经过以上级联失效后最终形成阶段2的稳定状态。
-
在基于仿真的鲁棒性分析中,网络在受到攻击后,主要关注的是其拓扑结构和连通性的变化。当前研究中最常用的最大连通子图比例和网络效能比指标也是基于这一思想。本文针对相依网络,在最大连通子图比例和网络效能比的基础上,考虑相依网络每个子网络在攻击前后相对于整个网络的连通性,提出了新的基于最大连通子图相对效能比的相互依存网络鲁棒性指标,来衡量相依网络级联失效过程中网络鲁棒性变化状况。
-
定义1 攻击后网络最大连通子图比例F
攻击后网络最大连通子图比例是目前复杂网络鲁棒性研究中最常用的指标,指攻击后网络中最大连通子图的节点数量与整个网络中全部节点数量的比值:
$$F = \frac{{N'}}{N}$$ 式中,
$N'$ 表示网络受攻击后最大连通子图中的剩余节点数量;$N$ 表示整个网络中全部节点的数量。该指标反映了网络遭受攻击后的拓扑结构的变化。定义2 网络效能比EM
网络效能是一个量化节点间连通性和通信效率的鲁棒性指标,为网络中任意两个节点间最短路径距离的倒数的平均值。由于节点间最短路径又称为测地线,因此网络效能也可以称为反测地线距离[7]。对网络效能E的定义如下:
$$E = \frac{1}{{N(N - 1)}}\sum\limits_{i \ne j \in V} {\frac{1}{{{d_{ij}}}}} $$ 式中,
${d_{ij}}$ 为节点i和j间的最短路径长度,若不存在通路,则$\dfrac{1}{{{d_{ij}}}} = 0$ 。为了便于对比网络攻击前后的效果,需要将网络效能做归一化处理,形成网络效能比指标EM(efficiency measurement-ratio),按下式计算:$${\rm{EM}} = \frac{{{E_c}}}{{{E_i}}}$$ 式中,
${E_i}$ 和${E_c}$ 分别为攻击前和攻击后的网络效率。按照性质可知,网络效能比EM越大,则网络鲁棒性越好。 -
级联失效过程中,网络中任意节点在失效时,并非将该节点从网络中完全移除,而是使其失去所有连接边,以孤立节点的形式存在于网络中。根据这一点可知,设
$N$ 表示整个网络中全部节点的数量,$N'$ 表示网络受攻击后最大连通子图中的节点数量,则网络在攻击前后$N$ 是不变的,而$N'$ 逐渐减少,若攻击后网络完全崩溃,则网络中所有节点均为孤立节点,不存在最大连通子图,即$N' = 0$ 。根据级联失效模型和渗流理论可知,只有当节点在最大连通子图中时,才能够保持正常运作,而节点脱离了最大连通子图时,会因失去与网络大部分节点的联系而失去正常工作的能力导致失效[16]。而网络效能始终以整个网络的角度来衡量网络的连通性,这会将已经失效的孤立节点也一并纳入衡量,无法准确得知最大连通子图在级联失效过程中的变化情况。因此,本文结合级联失效过程中网络全局和最大连通子图的变化情况,给出最大连通子图相对效能LRE (largest-component relative efficiency)的定义,并进一步提出最大连通子图相对效能比LREM (largest-component relative efficiency measurement-ratio)。对于一个网络n中的最大连通子图,其网络效能
$E'$ 表示为:$${E'_n} = \frac{1}{{{{N'}_n}({{N'}_n} - 1)}}\sum\limits_{i \ne j \in {{V'}_n}} {\frac{1}{{{d_{ij}}}}} $$ 式中,
${V'_n}$ 为网络n中最大连通子图的节点集合,若${N'_n} < 2$ 时,${E'_n} = 0$ 。考虑到指标需要度量网络整体的鲁棒性而不是只对最大连通子图进行度量,设定最大连通子图的效能相对于整个网络要乘上最大连通子图比例的权重,则得出在网络n受到攻击后,最大连通子图相对效能LRE的定义如下:$$ {\rm{LR}}{{\rm{E}}}_{n}={F}_{n} {{E}^{\prime }}_{n}=\frac{1}{{N}_{n}({{N}^{\prime }}_{n}-1)}{\displaystyle \sum _{i\ne j\in {{V}^{\prime }}_{n}}\frac{1}{{d}_{ij}}}$$ 由上式可知,在网络攻击前,
${N'_n} = {N_n}$ ,此时LRE退化为网络效能。对于两层相依网络,综合考虑网络A和网络B的LRE后取平均值,则定义相依网络的LRE为:$${\rm{LRE}}{\rm{ = }}\frac{1}{2}({\rm{LR}}{{\rm{E}}_A} + {\rm{LR}}{{\rm{E}}_B})$$ 和网络效能同理,为了对比攻击前后的效果,对LRE进行归一化处理,形成最大连通子图相对效能比LREM指标,按以下公式计算:
$${\rm{LREM}} = \frac{{{\rm{LR}}{{\rm{E}}_c}}}{{{\rm{LR}}{{\rm{E}}_i}}}$$ 式中,
${\rm{LR}}{{\rm{E}}_i}$ 和${\rm{LR}}{{\rm{E}}_c}$ 分别为攻击前和攻击后的LRE值。与EM同理,LREM越大,表示网络鲁棒性就越强。
Robustness Analysis of Interdependent Networks Based on the Largest-Component Relative Efficiency
-
摘要: 目前鲁棒性指标的研究主要针对单一网络,而对相依网络的探究较少。为此,该文对鲁棒性研究中几个常用的鲁棒性指标进行探究,针对相依网络级联失效过程,提出了基于最大连通子图相对效能的鲁棒性度量指标,并通过仿真实验验证其合理性。结果表明,相比现有常用指标,该指标能更准确地衡量相依网络在级联失效过程中的鲁棒性变化,可适用于大规模相依网络中基于仿真的鲁棒性分析。Abstract: The research on robustness indicators is mainly focused on single network, but less on interdependent networks. This paper explores some commonly used robustness indicators. Aiming at the cascading failure of interdependent networks, a new robustness indicator based on the largest-component relative efficiency is proposed. With the simulation for rationality verification, the results show that the indicator proposed in this paper is more accurate to measure the robustness variations of the interdependent networks in the cascading failure process than those are commonly used at present, and it can be applied to simulation-based robustness analysis for large-scale interdependent networks.
-
Key words:
- cascading failure /
- complex network /
- interdependent network /
- robustness
-
[1] ALBERT R, JEONG H, BARABASI A L. Error and attack tolerance of complex networks[J]. Nature, 2000, 406(6794): 378. doi: 10.1038/35019019 [2] 吴俊, 谭索怡, 谭跃进, 等. 基于自然连通度的复杂网络抗毁性分析[J]. 复杂系统与复杂性科学, 2014, 11(1): 77-86. WU Jun, TAN Suo-yi, TAN Yue-jin, et al. Analysis of invulnerability in complex networks based on natural connectivity[J]. Complex Systems and Complexity Science, 2014, 11(1): 77-86. [3] 王班, 马润年, 王刚. 基于自然连通度的复杂网络抗毁性研究[J]. 计算机仿真, 2015, 32(8): 315-318. WANG Ban, MA Run-nian, WANG Gang. Research on invulnerability of complex networks based on Natural Connectivity[J]. Computer Simulation, 2015, 32(8): 315-318. [4] 彭观胜. 基于自然连通度的复杂网络抗毁性优化研究[D]. 长沙: 国防科学技术大学, 2015. PENG Guan-sheng. Optimizing complex network topology for robustness based on natural connectivity[D]. Changsha: National University of Defense Technology, 2015. [5] 冯慧芳, 李彩虹. 基于复杂网络的车载自组织网络抗毁性分析[J]. 计算机应用, 2016, 36(7): 1789-1792. FENG Hui-fang, LI Cai-hong. Invulnerability analysis of vehicular ad hoc network based on complex network[J]. Journal of Computer Application, 2016, 36(7): 1789-1792. [6] ZHU K L, LU Y L, YANG G Z. Study on invulnerability of the Internet based on MapReduce[C]//The 6th International Conference on Instrumentation & Measurement, Computer, Communication and Control (IMCCC). Harbin: IEEE, 2016: 526-531. [7] 孙成雨, 申卯兴, 史向峰. 网络抗毁性的点韧性度指标计算方法研究[J]. 计算机应用研究, 2017(7): 1997-2000. doi: 10.3969/j.issn.1001-3695.2017.07.017 SUN Cheng-yu, SHEN Mao-xing, SHI Xiang-feng. Study of computing method to node tenacity index for network invulnerability[J]. Application Research of Computers, 2017(7): 1997-2000. doi: 10.3969/j.issn.1001-3695.2017.07.017 [8] 张昕, 郭阳. 复杂网络中的一种介度熵抗毁性度量方法[J]. 计算机工程与应用, 2020, 56(12): 105-111. ZHANG Xin, GUO Yang. Betweenness-degree entropy invulnerability measurement method in complex networks[J]. Computer Engineering and Applications, 2020, 56(12): 105-111. [9] 董璊. 复杂网络结构特性及其鲁棒性研究[D]. 兰州: 兰州理工大学, 2019. DONG Men. Research on complex network structure characteristics and its Robustness[D]. Lanzhou: Lanzhou University of Technology, 2019. [10] GIAN P C, ALESSANDRA C. Bounding robustness in complex networks under topological changes through majorization techniques[J]. The European Physical Journal B: Condensed Matter and Complex Systems, 2020, 93(6): 114. doi: 10.1140/epjb/e2020-100563-2 [11] BULDYREV S V, PARSHANI R, PAUL G, et al. Catastrophic cascade of failures in interdependent networks[J]. Nature, 2010, 464(7291): 1025-1028. doi: 10.1038/nature08932 [12] CHENG Z, CAO J. Cascade of failures in interdependent networks coupled by different type networks[J]. Physica A: Statistical Mechanics and Its Applications, 2015, 430: 193-200. doi: 10.1016/j.physa.2015.02.090 [13] WANG J, LI Y, ZHENG Q. Cascading load model in interdependent networks with coupled strength[J]. Physica A: Statistical Mechanics and Its Applications, 2015, 430: 242-253. doi: 10.1016/j.physa.2015.02.072 [14] 陈世明, 邹小群, 吕辉, 等. 面向级联失效的相依网络鲁棒性研究[J]. 物理学报, 2014, 63(2): 432-441. CHEN Shi-Ming, ZOU Xiao-Qun, LÜ Hui, et al. Research on robustness of interdependent network for suppressing cascading failure[J]. Acta Phys Sin, 2014, 63(2): 432-441. [15] 李从东, 李文博, 曹策俊, 等. 面向级联故障的相依网络鲁棒性分析[J]. 系统仿真学报, 2019(3): 538-548. LI Cong-dong, LI Wen-bo, CAO Ce-jun, et al. Robustness analysis of interdependent networks for cascading failure[J]. Journal of System Simulation, 2019(3): 538-548. [16] 万皓. 相依网络在不同相依方式下级联故障的鲁棒性研究[D]. 南昌: 华东交通大学, 2017. WAN Hao. Research on robustness of interdependent networks in different interdependent model on cascading failure[D]. Nanchang: East China Jiaotong University, 2017. [17] 韩伟涛, 伊鹏, 马海龙, 等. 异质弱相依网络鲁棒性研究[J]. 物理学报, 2019, 68(18): 222-229. HAN Wei-tao, YI Peng, MA Hai-long, et al. Robustness of interdependent networks with heterogeneous weak inter-layer links[J]. Acta Phys Sin, 2019, 68(18): 222-229. [18] ZHANG H, ZHOU J, ZOU Y, et al. Asymmetric interdependent networks with multiple-dependence relation[J]. Physical Review E, 2020, 101(2): 022314. [19] BARABASI A L, ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509-512. doi: 10.1126/science.286.5439.509 [20] WATTS D J, STROGATZ S H. Collective dynamics of “small-world” networks[J]. Nature, 1998, 393(6684): 440-442. doi: 10.1038/30918