Underestimated cost of targeted attacks on complex networks

Abstract

The robustness of complex networks under targeted attacks is deeply connected to the resilience of complex systems, i.e., the ability to make appropriate responses to the attacks. In this article, we investigated the state-of-the-art targeted node attack algorithms and demonstrate that they become very inefficient when the cost of the attack is taken into consideration. In this paper, we made explicit assumption that the cost of removing a node is proportional to the number of adjacent links that are removed, i.e., higher degree nodes have higher cost. Finally, for the case when it is possible to attack links, we propose a simple and efficient edge removal strategy named Hierarchical Power Iterative Normalized cut (HPI-Ncut).The results on real and artificial networks show that the HPI-Ncut algorithm outperforms all the node removal and link removal attack algorithms when the cost of the attack is taken into consideration. In addition, we show that on sparse networks, the complexity of this hierarchical power iteration edge removal algorithm is only $O(n{\log }^{2+\epsilon }(n))$.

arXiv comment14 pages, 7 figures

References in corpus (29)

• Emergence of scaling in random networks
• The structure and function of complex networks
• Error and attack tolerance of complex networks
• Catastrophic cascade of failures in interdependent networks
• Epidemic processes in complex networks
• Identification of influential spreaders in complex networks
• Network robustness and fragility: Percolation on random graphs
• Resilience of the Internet to random breakdowns
• Attack vulnerability of complex networks
• Breakdown of the Internet under intentional attack
• Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
• Immunization of complex networks
• Influence maximization in complex networks through optimal percolation
• Vital nodes identification in complex networks
• Mitigation of Malicious Attacks on Networks
• Network dismantling
• Optimization of Network Robustness to Waves of Targeted and Random Attack
• Identifying optimal targets of network attack by belief propagation
• Fast and simple decycling and dismantling of networks
• Containing epidemic outbreaks by message-passing techniques
• The Role of Social Networks in Information Diffusion
• Articulation Points in Complex Networks
• Bridgeness: A Local Index on Edge Significance in Maintaining Global Connectivity
• Spin glass approach to the feedback vertex set problem
• Complex networks vulnerability to module-based attacks
• Impact of embedding on predictability of failure-recovery dynamics in networks
• The cost of attack in competing networks
• First-principles multiway spectral partitioning of graphs
• Optimal cost for strengthening or destroying a given network

Cited by in corpus (3)

• Generalized Network Dismantling
• The web of federal crimes in Brazil: topology, weaknesses, and control
• Ensemble approach for generalized network dismantling