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 (7)

• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• A message passing approach for general epidemic models
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• The zero-patient problem with noisy observations
• Solving the undirected feedback vertex set problem by local search
• Metastable behavior for bootstrap percolation on regular trees

Cited by in corpus (3)

• Statistical Mechanics of the Minimum Dominating Set Problem
• A cavity approach to optimization and inverse dynamical problems
• Dismantle a network efficiently during the entire process by a compound algorithm