Identifying optimal targets of network attack by belief propagation

Abstract

For a network formed by nodes and undirected links between pairs of nodes, the network optimal attack problem aims at deleting a minimum number of target nodes to break the network down into many small components. This problem is intrinsically related to the feedback vertex set problem that was successfully tackled by spin glass theory and an associated belief propagation-guided decimation (BPD) algorithm [H.-J. Zhou, Eur. Phys. J. B 86 (2013) 455]. In the present work we apply the BPD alrogithm (which has approximately linear time complexity) to the network optimal attack problem, and demonstrate that it has much better performance than a recently proposed Collective Information algorithm [F. Morone and H. A. Makse, Nature 524 (2015) 63--68] for different types of random networks and real-world network instances. The BPD-guided attack scheme often induces an abrupt collapse of the whole network, which may make it very difficult to defend.

Final version (9 pages, including 5 figures and 1 table). Figure 3 is updated and contains more information than that of the accepted PRE paper

References in corpus (22)

• Statistical mechanics of complex networks
• Error and attack tolerance of complex networks
• Epidemic spreading in scale-free networks
• Network robustness and fragility: Percolation on random graphs
• Breakdown of the Internet under intentional attack
• Influence maximization in complex networks through optimal percolation
• Universal Behavior of Load Distribution in Scale-free Networks
• Hyperbolic Geometry of Complex Networks
• Spectral redemption: clustering sparse networks
• Random graphs with clustering
• Graph Evolution: Densification and Shrinking Diameters
• Robust network community detection using balanced propagation
• Containing epidemic outbreaks by message-passing techniques
• Immunization and targeted destruction of networks using explosive percolation
• Avoiding a Spanning Cluster in Percolation Models
• Loops of any size and Hamilton cycles in random scale-free networks
• Spin glass approach to the feedback vertex set problem
• Optimizing spread dynamics on graphs by message passing
• Minimal contagious sets in random regular graphs
• Circuits in random graphs: from local trees to global loops
• An algorithm for counting circuits: application to real-world and random graphs
• Solving the undirected feedback vertex set problem by local search

Cited by in corpus (36)

• Robustness and resilience of complex networks
• Network dismantling
• Generalized Network Dismantling
• Fast and simple decycling and dismantling of networks
• Optimal percolation on multiplex networks
• Optimal Deployment of Resources for Maximizing Impact in Spreading Processes
• Efficient collective influence maximization in cascading processes with first-order transitions
• Fundamental difference between superblockers and superspreaders in networks
• A message-passing approach to epidemic tracing and mitigation with apps
• A loop enhancement strategy for network robustness
• Underestimated cost of targeted attacks on complex networks
• On Minimal Sets to Destroy the $k$-Core in Random Networks
• Optimal percolation in correlated multilayer networks with overlap
• Network clustering and community detection using modulus of families of loops
• A new design principle of robust onion-like networks self-organized in growth
• Competition, Collaboration, and Optimization in Multiple Interacting Spreading Processes
• Influence Maximization for Fixed Heterogeneous Thresholds
• Dismantling Complex Networks by a Neural Model Trained from Tiny Networks
• Minimum Long-Loop Feedback Vertex Set and Network Dismantling
• Cycle-tree guided attack of random K-core: Spin glass model and efficient message-passing algorithm
• Fragmenting networks by targeting collective influencers at a mesoscopic level
• Critical behaviors of high-degree adaptive and collective-influence percolation
• Dismantling Efficiency and Network Fractality
• Spin glass phase transitions in the random feedback vertex set problem
• Centralities in complex networks
• Maximally flexible solutions of a random $K$-satisfiability formula
• Universal vulnerability in strong modular networks with various degree distributions between inequality and equality
• Spin-glass model for the C-dismantling problem
• Vulnerable Connectivity Caused by Local Communities in Spatial Networks
• Feedback arcs and node hierarchy in directed networks
• Detecting and modelling real percolation and phase transitions of information on social media
• Optimal shattering of complex networks
• K-core attack, equilibrium K-core, and kinetically constrained spin system
• Effective Self-Healing Networks against Attacks or Disasters in Resource Allocation Control
• Dismantle a network efficiently during the entire process by a compound algorithm
• Ensemble approach for generalized network dismantling