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

Abstract

Kinetically constrained spin systems are toy models of supercooled liquids and amorphous solids. In this Perspective, we revisit the prototypical Fredrickson-Andersen (FA) kinetically constrained model from the viewpoint of K-core combinatorial optimization. Each kinetic cluster of the FA system, containing all the mutually visitable microscopic occupation configurations, is exactly the solution space of a specific instance of the K-core attack problem. The whole set of different jammed occupation patterns of the FA system is the configuration space of an equilibrium K-core problem. Based on recent theoretical results achieved on the K-core attack and equilibrium K-core problems, we discuss the thermodynamic spin glass phase transitions and the maximum occupation density of the fully unfrozen FA kinetic cluster, and the minimum occupation density and extreme vulnerability of the partially frozen (jammed) kinetic clusters. The equivalence between K-core attack and the fully unfrozen FA kinetic cluster also implies a new way of sampling K-core attack solutions.

arXiv comment14 pages, manuscript under review

References in corpus (52)

• Influence maximization in complex networks through optimal percolation
• Vital nodes identification in complex networks
• The Bethe lattice spin glass revisited
• Glassy dynamics of kinetically constrained models
• k-core organization of complex networks
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Network dismantling
• Lattice Glass Models
• Identifying optimal targets of network attack by belief propagation
• Reconstruction on trees and spin glass transition
• Fast and simple decycling and dismantling of networks
• Glass models on Bethe lattices
• Ergodicity and large deviations in physical systems with stochastic dynamics
• Growing timescales and lengthscales characterizing vibrations of amorphous solids
• A first-order phase transition at the random close packing of hard spheres
• Heterogeneous-k-core versus Bootstrap Percolation on Complex 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
• Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
• $k$-core percolation on complex networks: Comparing random, localized and targeted attacks
• Tricritical point in heterogeneous k-core percolation
• Vertex cover problem studied by cavity method: Analytics and population dynamics
• Large deviations of cascade processes on graphs
• Rethinking mean-field glassy dynamics and its relation with the energy landscape: the awkward case of the spherical mixed p-spin model
• Distance-d covering problems in scale-free networks with degree correlations
• Minimal contagious sets in random regular graphs
• Statistical Mechanics of the Minimum Dominating Set Problem
• Clarification of the Bootstrap Percolation Paradox
• A review on shear jamming
• A loop enhancement strategy for network robustness
• The jamming transition is a k-core percolation transition
• Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
• The nature of hypergraph $k$-core percolation problems
• The fate of the bootstrap percolation hybrid critical point in finite dimension
• Solving the undirected feedback vertex set problem by local search
• Universality class for bootstrap percolation with $m=3$ on the cubic lattice
• On Minimal Sets to Destroy the $k$-Core in Random Networks
• Statistical physics of hard combinatorial optimization: The vertex cover problem
• On the relation between kinetically constrained models of glass dynamics and the random first-order transition theory
• Threshold value of three dimensional bootstrap percolation
• Critical behaviors and universality classes of percolation phase transitions on two-dimensional square lattice
• Minimum Long-Loop Feedback Vertex Set and Network Dismantling
• Cycle-tree guided attack of random K-core: Spin glass model and efficient message-passing algorithm
• Entropy Inflection and Invisible Low-Energy States: Defensive Alliance Example
• Spin glass phase transitions in the random feedback vertex set problem
• Hierarchical cycle-tree packing model for $K$-core attack problem
• Dynamic Gardner crossover in a simple structural glass
• The Random-Diluted Triangular Plaquette Model: study of phase transitions in a Kinetically Constrained Model
• Vulnerability and Resilience of Social Engagement: Equilibrium Theory
• Jamming in confined geometry: Criticality of the jamming transition and implications of structural relaxation in confined supercooled liquids