Back to Search
Start Over
Hierarchical Cycle-Tree Packing Model for Optimal K-Core Attack.
- Source :
-
Journal of Statistical Physics . Dec2023, Vol. 190 Issue 12, p1-24. 24p. - Publication Year :
- 2023
-
Abstract
- The K-core of a graph is the unique maximum subgraph within which each vertex connects to K or more other vertices. The optimal K-core attack problem asks to delete the minimum number of vertices from the K-core to induce its complete collapse. A hierarchical cycle-tree packing model is introduced here for this challenging combinatorial optimization problem. We convert the temporally long-range correlated K-core pruning dynamics into locally tree-like static patterns and analyze this model through the replica-symmetric cavity method of statistical physics. A set of coarse-grained belief propagation equations are derived to predict single vertex marginal probabilities efficiently. The associated hierarchical cycle-tree guided attack (hCTGA) algorithm is able to construct nearly optimal attack solutions for regular random graphs and Erdös-Rényi random graphs. Our cycle-tree packing model may also be helpful for constructing optimal initial conditions for other irreversible dynamical processes on sparse random graphs. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00224715
- Volume :
- 190
- Issue :
- 12
- Database :
- Academic Search Index
- Journal :
- Journal of Statistical Physics
- Publication Type :
- Academic Journal
- Accession number :
- 174190960
- Full Text :
- https://doi.org/10.1007/s10955-023-03210-7