Minimal contagious sets in random regular graphs
From MaRDI portal
Abstract: The bootstrap percolation (or threshold model) is a dynamic process modelling the propagation of an epidemic on a graph, where inactive vertices become active if their number of active neighbours reach some threshold. We study an optimization problem related to it, namely the determination of the minimal number of active sites in an initial configuration that leads to the activation of the whole graph under this dynamics, with and without a constraint on the time needed for the complete activation. This problem encompasses in special cases many extremal characteristics of graphs like their independence, decycling or domination number, and can also be seen as a packing problem of repulsive particles. We use the cavity method (including the effects of replica symmetry breaking), an heuristic technique of statistical mechanics many predictions of which have been confirmed rigorously in the recent years. We have obtained in this way several quantitative conjectures on the size of minimal contagious sets in large random regular graphs, the most striking being that 5-regular random graph with a threshold of activation of 3 (resp. 6-regular with threshold 4) have contagious sets containing a fraction 1/6 (resp. 1/4) of the total number of vertices. Equivalently these numbers are the minimal fraction of vertices that have to be removed from a 5-regular (resp. 6-regular) random graph to destroy its 3-core. We also investigated Survey Propagation like algorithmic procedures for solving this optimization problem on single instances of random regular graphs.
Recommendations
Cites work
- Achlioptas process phase transitions are continuous
- Bootstrap percolation on the random graph \(G_{n,p}\)
- Bootstrap percolation on the random regular graph
- Bounds for diluted mean-fields spin glass models
- Broken replica symmetry bounds in the mean field spin glass model
- Combinatorial model and bounds for target set selection
- Complex networks: structure and dynamics
- Contagious sets in expanders
- Decycling graphs
- Decycling numbers of random regular graphs
- Diffusion and cascading behavior in random networks
- Dynamical Processes on Complex Networks
- Explosive percolation in random networks
- Factor graphs and the sum-product algorithm
- Gibbs states and the set of solutions of random constraint satisfaction problems
- Going after the k-SAT threshold
- scientific article; zbMATH DE number 6474901 (Why is no real title available?)
- scientific article; zbMATH DE number 5764908 (Why is no real title available?)
- Information, Physics, and Computation
- Instability of one-step replica-symmetry-broken phase in satisfiability problems
- Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
- Law of large numbers for the SIR epidemic on a random graph with given degrees
- Matchings on infinite graphs
- Maximum acyclic and fragmented sets in regular graphs
- Maximum independent sets on random regular graphs
- Maximum Percolation Time in Two-Dimensional Bootstrap Percolation
- Metastability effects in bootstrap percolation
- Metastable behavior for bootstrap percolation on regular trees
- Minimal percolating sets in bootstrap percolation
- New bounds for contagious sets
- On belief propagation guided decimation for random k-SAT
- On the independence and chromatic numbers of random regular graphs
- On the solution-space geometry of random constraint satisfaction problems
- Optimizing spread dynamics on graphs by message passing
- Pairs of SAT-assignments in random Boolean formulæ
- Reconstruction on trees and spin glass transition
- Replica bounds for diluted non-Poissonian spin systems
- Replica bounds for optimization problems and diluted spin systems
- Rumors in a Network: Who's the Culprit?
- Sharp metastability threshold for two-dimensional bootstrap percolation
- SIR epidemics on random graphs with a fixed degree sequence
- Spin Glass approach to the feedback vertex set problem
- The cavity method at zero temperature
- The condensation phase transition in random graph coloring
- The freezing threshold for \(k\)-colourings of a random graph
- The mathematics of infectious diseases
- The number of matchings in random graphs
- The Parisi formula
- The sharp threshold for bootstrap percolation in all dimensions
- The Sherrington-Kirkpatrick model
- The Structure and Function of Complex Networks
Cited in
(12)- A note on general epidemic region for infinite regular graphs
- On the spread of influence in graphs
- Large deviations for subcritical bootstrap percolation on the Erdős-Rényi graph
- Minimum degree conditions for small percolating sets in bootstrap percolation
- 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
- Efficient network dismantling via node explosive percolation
- Hierarchical cycle-tree packing model for optimal K-core attack
- On dissemination thresholds in regular and irregular graph classes
- Minimum lethal sets in grids and tori under 3-neighbour bootstrap percolation
- Statistical mechanics of the minimum dominating set problem
This page was built for publication: Minimal contagious sets in random regular graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2350108)
