#### 期刊菜单

Study on Cascading Failure Robustness Based on a New Strategy
DOI: 10.12677/MOS.2024.131074, PDF, HTML, XML, 下载: 121  浏览: 156

Abstract: Considering that retaining the neighbor node with the highest similarity can help reduce the nega-tive impact of the failed node on network performance and improve robustness, a new strategy is proposed to retain the neighbor node with the greatest similarity to the failed node during the cas-cading failure process. On the basis of the new strategy, the BA scale-free network, ER random net-work and WS small-world network are simulated, and the robustness of the new strategy and the original strategy are compared. The simulation results show that the robustness of the network in-creases with the increase of the capacity parameter β. The new strategy can effectively improve the robustness of the network, and the effect is more obvious on the BA scale-free network, which veri-fies the feasibility of the strategy.

1. 引言

2. 级联失效模型

2.1. 共邻节点相似度

1) 共同邻居相似度(Common Neighbors Similarity)

$CN\left(i,j\right)=|N\left(i\right)\cap N\left(j\right)|$ (1)

2) 所有邻居相似度(Total Neighbors Similarity)

$TN\left(i,j\right)=|N\left(i\right)\cup N\left(j\right)|$ (2)

3) Jaccard相似度(Jaccard Similarity)

Jaccard相似性系数是衡量两个节点的共同邻居节点占它们总邻居节点的比例，这是一个更广泛使用的相似性度量。如果将两个节点i和j的邻居分别作为两个集合 $N\left(i\right)$$N\left(j\right)$ ，式(3)就可以作为顶点的Jaccard 相似度指标，其相似度是通过邻居来衡量的。

$J\left(x,y\right)=\frac{CN\left(i,j\right)}{TN\left(i,j\right)}$ (3)

Figure 1. Schematic diagram of BA network

2.2. 级联失效模型

2.2.1. 初始负载的定义

${L}_{i}^{0}=a\ast {\left({k}_{i}\right)}^{\alpha }$ (4)

2.2.2. 容量设置及负载再分配策略

${C}_{i}=\left(1+\beta \right){L}_{i}^{0}$ (5)

$\prod j=\frac{{C}_{j}}{\underset{j\in {\Gamma }_{i}}{\sum }{C}_{j}}$ (6)

$\Delta {L}_{ij}={L}_{i}^{0}\ast \frac{{C}_{j}}{\underset{j\in {\Gamma }_{i}}{\sum }{C}_{j}}$ (7)

${L}_{i}^{0}+\Delta {L}_{ij}>{C}_{j}$ 时，节点j将失效，网络继续对失效的节点进行负载分配，直到任意节点的容量大于负载时，网络的负载失效才停止。网络的负载重分配的示意图如图2所示。

Figure 2. Schematic diagram of load distribution process

2.2.3. 保留相似度最高的邻居节点的分配策略

1) 选择随机攻击的方式，并将攻击比例q设置为0.1；

2) 根据式(3)计算失效节点与其各邻居节点之间的相似度，并将相似度从高到低进行排序，找出相似度最大的邻居节点；

3) 如果失效节点有两个以上的邻居节点，并且在进行负载分配时会使得相似度最大的邻居节点失效，那么将该节点从邻居节点的集合中删除，且分配 ${C}_{j}-{L}_{j}^{0}$ 的负载使得该节点达到饱和状态，后续的负载将不会分配给该节点；

4) 剩余邻居节点按照负载再分配策略进行负载的分配，直至网络达到稳定状态；

5) 计算网络的鲁棒性。

2.3. 级联失效过程

Figure 3. Schematic diagram of cascading failure process

2.4. 网络鲁棒性测量指标

$G=\frac{{N}^{\prime }}{N}$ (8)

2.5. 网络种类

1) BA网络

BA网络(Barabási-Albert网络)由Albert-László Barabási与Réka Albert提出。BA网络模型被用来解释复杂网络的无标度性。常用 $G\left(N,m\right)$ 表示，其中N表示网络中的节点数，m表示新节点与网络中已经存在的m个不同的旧节点连接，生成m条新边。从网络度分布来看，多数节点的度比较小，少数的几个节点具有很大的节点度。它的算法如下：

① 增长：网络从 ${m}_{0}$ 个节点开始，并在每个相等的时间间隔增加一个新节点。新节点与网络中已经存在的 $m\left(m\le {m}_{0}\right)$ 个不同的旧节点连接，生成m条新边。

② 优先连接：一个新节点与一个已经存在的节点i 相连接的概率为 $P\left({k}_{i}\right)$${k}_{i}$ 为节点i的度，如下式：

$P\left({k}_{i}\right)=\frac{{k}_{i}}{\underset{j}{\sum }{k}_{j}}$ (9)

2) ER网络

ER网络(Erdős-Rényi网络)是由数学家Paul Erdős和Alfréd Rény [23] 于1959年提出的一种随机图模型，用于研究随机性连接的网络结构。ER网络通常用G(N, p)表示，其中N表示网络中的节点数，p表示任意一对节点之间建立连接的概率。对于每对节点，以概率p相互连接，以概率 $1-p$ 不连接。ER网络的连接性是随机的，因此具有均匀性，每个节点在连接上没有明显的优势。这与一些无标度网络模型，如BA网络，形成鲜明对比。

3) WS网络

WS小世界网络(Watts-Strogatz小世界网络)是由Duncan J. Watts和Steven Strogatz [24] 于1998年提出的一种复杂网络模型，通常用 $G\left(N,m,p\right)$ 表示。WS小世界网络的生成过程包括两个关键步骤。首先，所有节点按照规则排列在一个环形结构上，每个节点与其相邻节点连接。然后，随机地选择每个节点，以一定的概率p，断开与其相邻节点的连接，并重新连接到环上的其他节点，这个过程称为“重连”。这个概率p控制了网络中的随机性程度。

3. 数值模拟

Figure 4. Variation of BA network robustness with α

Figure 5. Variation of ER network robustness with α

Figure 6. Robustness change before and after the new policy is used in BA network

Figure 7. Robustness changes before and after the new policy is used in ER networks

Figure 8. Robustness changes before and after the new policy is used in the WS network

4. 结论

 [1] Barabási, A.L. and Albert, R. (1999) Emergence of Scaling in Random Networks. Science, 286, 509-512. https://doi.org/10.1126/science.286.5439.509 [2] Barabási, A.L., Albert, R. and Jeong, H. (1999) Mean-Field Theory for Scale-Free Random Networks. Physica A: Statistical Mechanics and Its Applications, 272, 173-187. https://doi.org/10.1016/S0378-4371(99)00291-5 [3] Peng, P., Cheng, S., Chen, J., et al. (2018) A Fine-Grained Perspective on the Robustness of Global Cargo Ship Transportation Networks. Journal of Geographical Sciences, 28, 881-889. https://doi.org/10.1007/s11442-018-1511-z [4] Hou, G.Y., Jin, C., Xu, Z.D., et al. (2019) Exploring Evolutionary Features of Directed Weighted Hazard Network in the Subway Construction. Chinese Physics B, 28, 399-407. https://doi.org/10.1088/1674-1056/28/3/038901 [5] Buscarino, A., Fortuna, L. and Frasca, M. (2018) Special Issue on Complexity in Engineering. Nonlinear Dynamics, 92, 1-2. https://doi.org/10.1007/s11071-018-4140-2 [6] Kinney, R., Crucitti, P., Albert, R. and Latora, V. (2005) Model-ing Cascading Failures in the North American Power Grid. The European Physical Journal B, 46, 101-107. https://doi.org/10.1140/epjb/e2005-00237-9 [7] Chen, D., Shi, D.D. and Pan, G.J. (2019) Correlation between the Electrical Transport Performance and the Communicability Sequence Entropy in Complex Networks. Acta Physica Sinica, 68, Article ID: 118901. https://doi.org/10.7498/aps.68.20190230 [8] Motter, A.E. and Lai, Y.C. (2002) Cascade-Based Attacks on Com-plex Networks. Physical Review E, 66, Article ID: 065102. https://doi.org/10.1103/PhysRevE.66.065102 [9] Zhu, Q., Zhu, Z., Qi, Y., et al. (2018) Optimization of Cascading Failure on Complex Network Based on NNIA. Physica A: Statistical Mechanics & Its Applications, 501, 42-51. https://doi.org/10.1016/j.physa.2018.02.138 [10] Xu, S., Xia, Y. and Ouyang, M. (2020) Effect of Resource Allocation to the Recovery of Scale-Free Networks during Cascading Failures. Physica A: Statistical Mechanics and Its Applications, 540, Article ID: 123157. https://doi.org/10.1016/j.physa.2019.123157 [11] Hao, Y., Jia, L. and Wang, Y. (2019) Robustness of Weighted Networks with the Harmonic Closeness against Cascading Failures. Physica A: Statistical Mechanics and Its Applications, 541, Article ID: 123373. https://doi.org/10.1016/j.physa.2019.123373 [12] Qi, X., Yang, G. and Liu, L. (2020) Robustness Analysis of the Networks in Cascading Failures with Controllable Parameters. Physica A: Statistical Mechanics and Its Applications, 539, Article ID: 122870. https://doi.org/10.1016/j.physa.2019.122870 [13] Wang, J.W. and Rong, L.L. (2009) A Model for Cascading Fail-ures in Scale-Free Networks with a Breakdown Probability. Physica A: Statistical Mechanics and Its Applications, 388, 1289-1298. https://doi.org/10.1016/j.physa.2008.12.067 [14] Wang, J.W., Rong, L.L. and Wang, D. (2010) Model for Cas-cading Failures on Complex Networks Based on Local Characteristics of Node. Journal of Management Sciences in China, 13, 9. [15] Liu, J., Xiong, Q.Y., Shi, X., et al. (2015) Load-Redistribution Strategy Based on Time-Varying Load against Cascading Failure of Complex Network. Chinese Physics B, 24, Article ID: 076401. https://doi.org/10.1088/1674-1056/24/7/076401 [16] 唐亮, 焦鹏, 李纪康, 等. 带恢复策略的复杂网络级联失效机理及鲁棒性研究[J]. 控制与决策, 2018, 33(10): 1841-1850. [17] Duan, D.L., Ling, X.D., Wu, X.Y., et al. (2014) Critical Thresholds for Scale-Free Networks against Cascading Failures. Physica A: Statistical Mechanics and Its Applications, 416, 252-258. https://doi.org/10.1016/j.physa.2014.08.040 [18] 郝羽成, 李成兵, 魏磊. 考虑节点过载的复杂网络级联失效模型[J]. 系统工程与电子技术, 2018, 40(10): 2282-2287. [19] 刘苗苗, 郭景峰, 马晓阳, 等. 基于共邻节点相似度的加权网络社区发现方法[J]. 四川大学学报(自然科学版), 2018, 55(1): 89-98. [20] 付立东, 郝伟, 李丹, 等. 基于共邻节点相似度的社区划分算法[J]. 计算机应用, 2019, 39(7): 2024-2029. [21] 李从东, 原智峰, 邓原, 等. 面向级联失效的复杂网络动态增边策略[J]. 计算机应用研究, 2016, 33(8): 2324-2327, 2338. [22] Liu, J. (2001) Improving Robustness of Complex Networks by a New Capacity Allocation Strategy. Chi-nese Physics B, 30, Article ID: 016401. https://doi.org/10.1088/1674-1056/abb3f1 [23] Erdős, P. and Rényi, A. (1960) On the Evolution of Random Graphs. Publication of the Mathematical Institute of the Hungarian Academy of Sciences, 5, 17-60. [24] Watts, D.J. and Strogatz, S.H. (1998) Collective Dynamics of ‘Small-World’ Networks. Nature, 393, 440-442. https://doi.org/10.1038/30918