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

DOI10.1007/S10955-023-03210-7zbMATH Open1529.05142arXiv2303.01007MaRDI QIDQ6140935FDOQ6140935

Authors: Jianwen Zhou, Haijun Zhou 

Publication date: 2 January 2024

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

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.

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

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

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)

Cites Work

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