A new centrality measure based on neighbor loop structure for network dismantling

Abstract

Nearly all real-world networks are complex networks and usually are in danger of collapse. Therefore, it is crucial to exploit and understand the mechanisms of network attacks and provide better protection for network functionalities. Network dismantling aims to find the smallest set of nodes such that after their removal the network is broken into connected components of sub-extensive size. To overcome the limitations and drawbacks of existing network dismantling methods, this paper focuses on network dismantling problem and proposes a neighbor-loop structure based centrality metric, NL, which achieves a balance between computational efficiency and evaluation accuracy. In addition, we design a novel method combining NL-based nodes-removing, greedy tree-breaking and reinsertion. Moreover, we compare five baseline methods with our algorithm on ten widely used real-world networks and three types of model networks including Erdös-Rényi random networks, Watts-Strogatz small-world networks and Barabási-Albert scale-free networks with different network generation parameters. Experimental results demonstrate that our proposed method outperforms most peer methods by obtaining a minimal set of targeted attack nodes. Furthermore, the insights gained from this study may be of assistance to future practical research into real-world networks.

Keywords

• Complex networks
• Network dismantling
• Centrality measure