Hierarchical cycle-tree packing model for optimal K-core attack

DOI10.1007/S10955-023-03210-7MaRDI QIDQ6140935zbMATH OpenFDO

Authors Jianwen Zhou, Haijun Zhou

Publication date 2 January 2024

Published in Journal of Statistical Physics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2303.01007

zbMATH Keywords

cavity methodirreversible dynamicsoptimal initial condition\(K\)-core attackcycle-tree packing model

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30)

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.

Recommendations

• Building large \(k\)-cores from sparse graphs
• Minimum k‐cores and the k‐core polytope
• Targeted \(k\)-node collapse problem: towards understanding the robustness of local \(k\)-core structure
• Generalized \(k\)-cores of networks under attack with limited knowledge
• Core forging and local limit theorems for the \(k\)-core of random graphs

Cites work

• A spin glass approach to the directed feedback vertex set problem
• Analytical solution to the \(k\)-core pruning process
• Contagious sets in expanders
• Decycling numbers of random regular graphs
• Generalized \(k\)-core pruning process on directed networks
• Information, Physics, and Computation
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Minimal contagious sets in random regular graphs
• New bounds for contagious sets
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• Optimal segmentation of directed graph and the minimum number of feedback arcs
• Optimizing spread dynamics on graphs by message passing
• Reducibility among combinatorial problems
• Spin Glass approach to the feedback vertex set problem
• \(k\)-core architecture and \(k\)-core percolation on complex networks

Cited in

(1)

• Minimum connected dominating set and backbone of a random graph

This page was built for publication: Hierarchical cycle-tree packing model for optimal \(K\)-core attack

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6140935)