Minimal contagious sets in random regular graphs

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.

45 pages, 24 figures, minor corrections in v2

References in corpus (38)

• The structure and function of complex networks
• Evolution of networks
• The Bethe lattice spin glass revisited
• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• The structural glass transition and the entropy of the metastable states
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Locating the Source of Diffusion in Large-Scale Networks
• A message passing approach for general epidemic models
• Inferring the origin of an epidemic with a dynamic message-passing algorithm
• Bayesian inference of epidemics on networks via Belief Propagation
• Lattice Glass Models
• On the nature of the low-temperature phase in discontinuous mean-field spin glasses
• Bootstrap percolation on the random graph $G_{n,p}$
• Reconstruction on trees and spin glass transition
• The number of matchings in random graphs
• Glass models on Bethe lattices
• Containing epidemic outbreaks by message-passing techniques
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• Replica bounds for diluted non-Poissonian spin systems
• Spin glass approach to the feedback vertex set problem
• Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
• Optimizing spread dynamics on graphs by message passing
• Achlioptas process phase transitions are continuous
• The asymptotic $k$-SAT threshold
• On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms
• Pairs of SAT Assignment in Random Boolean Formulae
• Large deviations of cascade processes on graphs
• A message-passing approach for threshold models of behavior in networks
• The condensation phase transition in random graph coloring
• The hard-core model on random graphs revisited
• The zero-patient problem with noisy observations
• Minimizing energy below the glass thresholds
• Maximum independent sets on random regular graphs
• Solving the undirected feedback vertex set problem by local search
• On belief propagation guided decimation for random k-SAT
• Metastable behavior for bootstrap percolation on regular trees

Cited by in corpus (23)

• Network dismantling
• Identifying optimal targets of network attack by belief propagation
• Fast and simple decycling and dismantling of networks
• Optimal Deployment of Resources for Maximizing Impact in Spreading Processes
• Efficient collective influence maximization in cascading processes with first-order transitions
• Statistical Mechanics of the Minimum Dominating Set Problem
• The large deviations of the whitening process in random constraint satisfaction problems
• On Minimal Sets to Destroy the $k$-Core in Random Networks
• Competition, Collaboration, and Optimization in Multiple Interacting Spreading Processes
• Cycle-tree guided attack of random K-core: Spin glass model and efficient message-passing algorithm
• Large deviations for subcritical bootstrap percolation on the random graph
• Spin glass phase transitions in the random feedback vertex set problem
• Hierarchical cycle-tree packing model for $K$-core attack problem
• Spin-glass model for the C-dismantling problem
• A spin glass approach to the directed feedback vertex set problem
• Feedback arcs and node hierarchy in directed networks
• K-core attack, equilibrium K-core, and kinetically constrained spin system
• A cavity approach to optimization and inverse dynamical problems
• On the Decycling Number of $4$-regular Random Graphs
• Locality approach to the bootstrap percolation paradox
• Minority Takeover in Majority Dynamics: Searching for Rare Initializations via the History Passing Algorithm
• Dismantle a network efficiently during the entire process by a compound algorithm
• Time-Bounded Influence Diffusion with Incentives