Immunization and targeted destruction of networks using explosive percolation

Abstract

A new method (`explosive immunization' (EI)) is proposed for immunization and targeted destruction of networks. It combines the explosive percolation (EP) paradigm with the idea of maintaining a fragmented distribution of clusters. The ability of each node to block the spread of an infection (or to prevent the existence of a large cluster of connected nodes) is estimated by a score. The algorithm proceeds by first identifying low score nodes that should not be vaccinated/destroyed, analogously to the links selected in EP if they do not lead to large clusters. As in EP, this is done by selecting the worst node (weakest blocker) from a finite set of randomly chosen `candidates'. Tests on several real-world and model networks suggest that the method is more efficient and faster than any existing immunization strategy. Due to the latter property it can deal with very large networks.

9 pages, 9 figures. Supplemental material included as appendices

References in corpus (8)

• Explosive Synchronization Transitions in Scale-free Networks
• Recent advances in percolation theory and its applications
• Dynamics of jamming transitions in complex networks
• Explosive first-order transition to synchrony in networked chaotic oscillators
• Enhancing network robustness for malicious attacks
• Efficient local strategies for vaccination and network attack
• Prominent effect of soil network heterogeneity on microbial invasion
• Complexity and anisotropy in host morphology make populations safer against epidemic outbreaks

Cited by in corpus (30)

• Robustness and resilience of complex networks
• Explosive Phenomena in Complex Networks
• Fast and simple decycling and dismantling of networks
• Machine learning dismantling and early-warning signals of disintegration in complex systems
• Optimal percolation on multiplex networks
• Optimal resource diffusion for suppressing disease spreading in multiplex networks
• Fundamental difference between superblockers and superspreaders in networks
• Systematic comparison between methods for the detection of influential spreaders in complex networks
• Optimal Allocation of Resources for Suppressing Epidemic Spreading on Networks
• Universal mechanism for hybrid percolation transitions
• Influence maximization on temporal networks
• Prediction and mitigation of nonlocal cascading failures using graph neural networks
• Targeted influence maximization in complex networks
• Ranking influential spreaders is an ill-defined problem
• Optimal percolation in correlated multilayer networks with overlap
• Rapid decay in the relative efficiency of quarantine to halt epidemics in networks
• Deep-learning-aided dismantling of interdependent networks
• Minimum Long-Loop Feedback Vertex Set and Network Dismantling
• Critical behaviors of high-degree adaptive and collective-influence percolation
• Non-Markovian random walks characterize network robustness to nonlocal cascades
• Dismantling Efficiency and Network Fractality
• Impact of network characteristics on network reconstruction
• Spin-glass model for the C-dismantling problem
• Emergence of biconnected clusters in explosive percolation
• Detecting and modelling real percolation and phase transitions of information on social media
• Modeling resource consumption in the US air transportation system via minimum-cost percolation
• Analytical approach to network inference: Investigating degree distribution
• Effective vaccination strategy using graph neural network ansatz
• Abrupt transition of the efficient vaccination strategy in a population with heterogeneous fatality rates
• Dismantle a network efficiently during the entire process by a compound algorithm