Minimal contagious sets in random regular graphs
From MaRDI portal
Publication:2350108
DOI10.1007/s10955-014-1136-2zbMath1318.82038arXiv1407.7361OpenAlexW2033389241MaRDI QIDQ2350108
Guilhem Semerjian, Alberto Guggiola
Publication date: 18 June 2015
Published in: Journal of Statistical Physics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1407.7361
Random graphs (graph-theoretic aspects) (05C80) Approximation methods and heuristics in mathematical programming (90C59) Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics (82C20) Time-dependent percolation in statistical mechanics (82C43)
Related Items
Statistical mechanics of the minimum dominating set problem ⋮ Minimum degree conditions for small percolating sets in bootstrap percolation ⋮ Hierarchical cycle-tree packing model for optimal \(K\)-core attack ⋮ Threshold behavior of bootstrap percolation ⋮ The large deviations of the whitening process in random constraint satisfaction problems ⋮ A spin glass approach to the directed feedback vertex set problem ⋮ Whom to befriend to influence people ⋮ On the spread of influence in graphs ⋮ Efficient Network Dismantling via Node Explosive Percolation* ⋮ Large deviations for subcritical bootstrap percolation on the Erdős-Rényi graph
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Matchings on infinite graphs
- Combinatorial model and bounds for target set selection
- New bounds for contagious sets
- Diffusion and cascading behavior in random networks
- Achlioptas process phase transitions are continuous
- Bootstrap percolation on the random graph \(G_{n,p}\)
- Reconstruction on trees and spin glass transition
- Minimal percolating sets in bootstrap percolation
- Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
- Metastable behavior for bootstrap percolation on regular trees
- On the independence and chromatic numbers of random regular graphs
- Sharp metastability threshold for two-dimensional bootstrap percolation
- Bounds for diluted mean-fields spin glass models
- Replica bounds for optimization problems and diluted spin systems
- Broken replica symmetry bounds in the mean field spin glass model
- The cavity method at zero temperature
- Complex networks: structure and dynamics
- Maximum independent sets on random regular graphs
- Pairs of SAT-assignments in random Boolean formulæ
- The Parisi formula
- The Mathematics of Infectious Diseases
- SIR epidemics on random graphs with a fixed degree sequence
- Optimizing spread dynamics on graphs by message passing
- Bootstrap percolation on the random regular graph
- Maximum Percolation Time in Two-Dimensional Bootstrap Percolation
- Dynamical Processes on Complex Networks
- Information, Physics, and Computation
- Metastability effects in bootstrap percolation
- Decycling graphs
- The Structure and Function of Complex Networks
- Instability of one-step replica-symmetry-broken phase in satisfiability problems
- Factor graphs and the sum-product algorithm
- Decycling numbers of random regular graphs
- The Sherrington-Kirkpatrick Model
- The number of matchings in random graphs
- Law of large numbers for the SIR epidemic on a random graph with given degrees
- Rumors in a Network: Who's the Culprit?
- Contagious Sets in Expanders
- On belief propagation guided decimation for random k-SAT
- Gibbs states and the set of solutions of random constraint satisfaction problems
- The sharp threshold for bootstrap percolation in all dimensions
- The freezing threshold for k-colourings of a random graph
- Maximum acyclic and fragmented sets in regular graphs
- Going after the k-SAT threshold
- Replica bounds for diluted non-Poissonian spin systems
- Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
- On the solution-space geometry of random constraint satisfaction problems
- Explosive Percolation in Random Networks
- Spin Glass approach to the feedback vertex set problem