Hierarchical cycle-tree packing model for $K$-core attack problem

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 ({\tt 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.

arXiv comment25 pages, 8 figures

References in corpus (25)

• Identification of influential spreaders in complex networks
• k-core organization of complex networks
• Network dismantling
• Fast and simple decycling and dismantling of networks
• k-Core percolation on multiplex networks
• Facilitated spin models on Bethe lattice: bootstrap percolation, mode-coupling transition and glassy dynamics
• Spin glass approach to the feedback vertex set problem
• Optimizing spread dynamics on graphs by message passing
• Inducing Effect on the Percolation Transition in Complex Networks
• Efficient collective influence maximization in cascading processes with first-order transitions
• Critical dynamics of the k-core pruning process
• Large deviations of cascade processes on graphs
• Minimal contagious sets in random regular graphs
• Solvable Models of Supercooled Liquids in Three Dimensions
• The fate of the bootstrap percolation hybrid critical point in finite dimension
• On Minimal Sets to Destroy the $k$-Core in Random Networks
• Cycle-tree guided attack of random K-core: Spin glass model and efficient message-passing algorithm
• Random node reinforcement and $K$-core structure of complex networks
• Optimal segmentation of directed graph and the minimum number of feedback arcs
• Generalized $k$-core pruning process on directed networks
• A spin glass approach to the directed feedback vertex set problem
• Vulnerability and Resilience of Social Engagement: Equilibrium Theory
• COREATTACK: Breaking Up the Core Structure of Graphs
• Minimum Connected Dominating Set and Backbone of a Random Graph
• Optimal Disruption of Complex Networks

Cited by in corpus (1)

• K-core attack, equilibrium K-core, and kinetically constrained spin system