Cycle-tree guided attack of random K-core: Spin glass model and efficient message-passing algorithm
arXiv:2110.05940 · doi:10.1007/s11433-021-1845-6
Abstract
The K-core of a graph is the maximal subgraph within which each vertex is connected to at least K other vertices. It is a fundamental network concept for understanding threshold cascading processes with a discontinuous percolation transition. A minimum attack set contains the smallest number of vertices whose removal induces complete collapse of the K-core. Here we tackle this prototypical optimal initial-condition problem from the spin-glass perspective of cycle-tree maximum packing and propose a cycle-tree guided attack (CTGA) message-passing algorithm. The good performance and time efficiency of CTGA are verified on the regular random and Erdös-Rényi random graph ensembles. Our central idea of transforming a long-range correlated dynamical process to static structural patterns may also be instructive to other hard optimization and control problems.
arXiv commentA label in Figure 3(b) was corrected
References in corpus (24)
- Identification of influential spreaders in complex networks
- k-core organization of complex networks
- Control Principles of Complex Networks
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- Network dismantling
- Bootstrap Percolation on Complex Networks
- Identifying optimal targets of network attack by belief propagation
- Fast and simple decycling and dismantling of networks
- The k-core as a predictor of structural collapse in mutualistic ecosystems
- Spin glass approach to the feedback vertex set problem
- Optimizing spread dynamics on graphs by message passing
- -core percolation on complex networks: Comparing random, localized and targeted attacks
- Efficient collective influence maximization in cascading processes with first-order transitions
- Large deviations of cascade processes on graphs
- A message-passing approach for threshold models of behavior in networks
- Minimal contagious sets in random regular graphs
- The fate of the bootstrap percolation hybrid critical point in finite dimension
- On Minimal Sets to Destroy the -Core in Random Networks
- Disconnected glass-glass transitions and swallowtail bifurcations in microscopic spin models with facilitated dynamics
- Minimum Long-Loop Feedback Vertex Set and Network Dismantling
- Optimal segmentation of directed graph and the minimum number of feedback arcs
- Generalized -core pruning process on directed networks
- Vulnerability and Resilience of Social Engagement: Equilibrium Theory
- A spin glass approach to the directed feedback vertex set problem