Computer Engineering and Applications ›› 2022, Vol. 58 ›› Issue (9): 127-135.DOI: 10.3778/j.issn.1002-8331.2010-0370

• Network, Communication and Security • Previous Articles     Next Articles

Multi-Parameter Hybrid Power Iterative Collapse Strategy for Interdependent Networks

FU Hao, LIU Sanyang, BAI Yiguang   

  1. School of Mathematics and Statistics, Xidian University, Xi’an 710126, China
  • Online:2022-05-01 Published:2022-05-01



  1. 西安电子科技大学 数学与统计学院,西安 710126

Abstract: Exploring the optimal collapse strategy of complex networks is an important subject in network science research. Compared with the single-layer network, the optimal collapse of the multi-layer coupling network has become a new research direction. The traditional algorithms mostly focus on the study of high-centrality nodes, and a single-centrality measure often leads to deviations in the evaluation of the importance of nodes. The present paper combines two typical physical methods(the mass diffusion(MD) and the heat conduction(HC)) for the first time, and proposes a new power iterative algorithm(PIA), which utilizes network characteristics to sort nodes and can better find the important nodes in the network. Meanwhile, it can ensure a lower computational complexity and a great running efficiency. Finally, the cascading failure is used to analyze the removal effect of relevant important nodes. Extensive experiments demonstrate that compared with the existing IEP algorithm and other state-of-the-art algorithms, the proposed PIA can collapse the network faster in various types of real-world/synthetic two-layer networks.

Key words: complex network, network collapse, power iteration, node sorting, cascading failure

摘要: 探寻复杂网络的最优瓦解策略是网络科学研究中的重要课题。相比于单层网络,更为普遍的多层耦合网络的最优瓦解成为新的研究方向。传统算法大多集中在研究高中心性节点,而单一的中心性测度往往会导致对节点重要性的评估出现偏差。首次结合质量扩散(MD)和热传导(HC)两种经典物理方法,提出了一种新的基于幂次迭代的算法(PIA),该方法利用网络特征进行节点排序,能够更好地找到网络中的重要节点。同时能保证一个较低的计算复杂度,具有很好的运行效率。利用级联失效分析相关重要节点的移除效果。实验表明,相比于现有的IEP算法和其他经典算法,所提的PIA算法在各种类型的人工双层网络和现实网络模拟中都能够使得网络瓦解得更快。

关键词: 复杂网络, 网络瓦解, 幂次迭代, 节点排序, 级联失效