Hierarchical cycle-tree packing model for $K$-core attack problem
Authors:
Preprint
Abstract
The $K$-core of a graph is the unique maximum subgraph within which each vertex connects to at least $K$ other vertices. The $K$-core optimal attack problem asks to construct a minimum-sized set of vertices whose removal results in the complete collapse of the $K$-core. In this paper, we construct a hierarchical cycle-tree packing model which converts a long-range correlated $K$-core pruning process into static patterns and analyze this model through the replica-symmetric (RS) cavity method of statistical physics. The cycle-tree guided attack (CTGA) message-passing algorithm exhibits superior performance on random regular and Erdos-Renyi graphs. It provides new upper bounds on the minimal cardinality of the $K$-core attack set. The model of this work may be extended to construct optimal initial conditions for other irreversible dynamical processes.
Keywords
All Related Versions
This publication has 29 references indexed in Scilit:
- Cycle-tree guided attack of random K-core: Spin glass model and efficient message-passing algorithmScience China Physics, Mechanics & Astronomy, 2022
- Optimal Segmentation of Directed Graph and the Minimum Number of Feedback ArcsJournal of Statistical Physics, 2017
- Minimal Contagious Sets in Random Regular GraphsJournal of Statistical Physics, 2014
- New bounds for contagious setsDiscrete Mathematics, 2012
- Irreversible -threshold processes: Graph-theoretical threshold models of the spread of disease and of opinionDiscrete Applied Mathematics, 2009
- Peeling the yeast protein networkProteomics, 2005
- Decycling numbers of random regular graphsRandom Structures & Algorithms, 2002
- Network structure and minimum degreeSocial Networks, 1983
- Application of percolation theory to 2D‐3D heisenberg ferromagnetsPhysica Status Solidi (b), 1975
- Reducibility among Combinatorial Problems1972