Generalized Network Dismantling

Abstract

Finding the set of nodes, which removed or (de)activated can stop the spread of (dis)information, contain an epidemic or disrupt the functioning of a corrupt/criminal organization is still one of the key challenges in network science. In this paper, we introduce the generalized network dismantling problem, which aims to find the set of nodes that, when removed from a network, results in a network fragmentation into subcritical network components at minimum cost. For unit costs, our formulation becomes equivalent to the standard network dismantling problem. Our non-unit cost generalization allows for the inclusion of topological cost functions related to node centrality and non-topological features such as the price, protection level or even social value of a node. In order to solve this optimization problem, we propose a method, which is based on the spectral properties of a novel node-weighted Laplacian operator. The proposed method is applicable to large-scale networks with millions of nodes. It outperforms current state-of-the-art methods and opens new directions in understanding the vulnerability and robustness of complex systems.

arXiv comment6 pages, 5 figures

References in corpus (23)

• Emergence of scaling in random networks
• Error and attack tolerance of complex networks
• Catastrophic cascade of failures in interdependent networks
• Critical phenomena in complex networks
• Breakdown of the Internet under intentional attack
• Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
• Influence maximization in complex networks through optimal percolation
• Vital nodes identification in complex networks
• Mitigation of Malicious Attacks on Networks
• Network dismantling
• Vertex overload breakdown in evolving networks
• Edge overload breakdown in evolving networks
• 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
• Articulation Points in Complex Networks
• Identification of Patient Zero in Static and Temporal Networks - Robustness and Limitations
• The dynamical structure of political corruption networks
• Spin glass approach to the feedback vertex set problem
• Underestimated cost of targeted attacks on complex networks
• First-principles multiway spectral partitioning of graphs
• Simulating SIR processes on networks using weighted shortest paths
• Optimal cost for strengthening or destroying a given network

Cited by in corpus (19)

• Robustness and resilience of complex networks
• Machine learning dismantling and early-warning signals of disintegration in complex systems
• Structural Robustness of Complex Networks: A Survey of A Posteriori Measures
• Coordinated Inauthentic Behavior and Information Spreading on Twitter
• The web of federal crimes in Brazil: topology, weaknesses, and control
• Unraveling the effects of multiscale network entanglement on disintegration of empirical systems
• A Complex Networks Approach to Find Latent Clusters of Terrorist Groups
• Targeted influence maximization in complex networks
• Deep-learning-aided dismantling of interdependent networks
• Dismantling Complex Networks by a Neural Model Trained from Tiny Networks
• Minimum Long-Loop Feedback Vertex Set and Network Dismantling
• Critical behaviors of high-degree adaptive and collective-influence percolation
• Evolutionary dynamics of organised crime and terrorist networks
• Statistical analysis of edges and bredges in configuration model networks
• Bounding robustness in complex networks under topological changes through majorization techniques
• Structural roles and gender disparities in corruption networks
• Recovering the Graph Underlying Networked Dynamical Systems under Partial Observability: A Deep Learning Approach
• Optimal shattering of complex networks
• Ensemble approach for generalized network dismantling