Bootstrap percolation on a graph with random and local connections

We analyze the bootstrap percolation process on the stochastic block model (SBM), a natural extension of the Erd\"{o}s--R\'{e}nyi random graph that allows representing the "community structure" observed in many real systems. In the SBM, nodes are partitioned into subsets, which represent different communities, and pairs of nodes are independently connected with a probability that depends on the communities they belong to. Under mild assumptions on system parameters, we prove ...

In the random $r$-neighbour bootstrap percolation process on a graph $G$, a set of initially infected vertices is chosen at random by retaining each vertex of $G$ independently with probability $p\in (0,1)$, and "healthy" vertices get infected in subsequent rounds if they have at least $r$ infected neighbours. A graph $G$ \emph{percolates} if every vertex becomes eventually infected. A central problem in this process is to determine the critical probability $p_c(G,r)$, at whi...

In this paper we study the strict majority bootstrap percolation process on graphs. Vertices may be active or passive. Initially, active vertices are chosen independently with probability p. Each passive vertex becomes active if at least half of its neighbors are active (and thereafter never changes its state). If at the end of the process all vertices become active then we say that the initial set of active vertices percolates on the graph. We address the problem of finding ...

The theme of this paper is the analysis of bootstrap percolation processes on random graphs generated by preferential attachment. This is a class of infection processes where vertices have two states: they are either infected or susceptible. At each round every susceptible vertex which has at least $r\geq 2$ infected neighbours becomes infected and remains so forever. Assume that initially $a(t)$ vertices are randomly infected, where $t$ is the total number of vertices of the...

Majority bootstrap percolation on a graph $G$ is an epidemic process defined in the following manner. Firstly, an initially infected set of vertices is selected. Then step by step the vertices that have more infected than non-infected neighbours are infected. We say that percolation occurs if eventually all vertices in $G$ become infected. In this paper we study majority bootstrap percolation on the Erd\H{o}s-R\'enyi random graph $G(n,p)$ above the connectivity threshold. P...

In the $r$-neighbour bootstrap process on a graph $G$, vertices are infected (in each time step) if they have at least $r$ already-infected neighbours. Motivated by its close connections to models from statistical physics, such as the Ising model of ferromagnetism, and kinetically constrained spin models of the liquid-glass transition, the most extensively-studied case is the two-neighbour bootstrap process on the two-dimensional grid $[n]^2$. Around 15 years ago, in a major ...

In majority bootstrap percolation on a graph G, an infection spreads according to the following deterministic rule: if at least half of the neighbours of a vertex v are already infected, then v is also infected, and infected vertices remain infected forever. Percolation occurs if eventually every vertex is infected. The elements of the set of initially infected vertices, A \subset V(G), are normally chosen independently at random, each with probability p, say. This process ...

Graph bootstrap percolation is a deterministic cellular automaton which was introduced by Bollob\'as in 1968, and is defined as follows. Given a graph $H$, and a set $G \subset E(K_n)$ of initially `infected' edges, we infect, at each time step, a new edge $e$ if there is a copy of $H$ in $K_n$ such that $e$ is the only not-yet infected edge of $H$. We say that $G$ percolates in the $H$-bootstrap process if eventually every edge of $K_n$ is infected. The extremal questions fo...

We consider bootstrap percolation on uncorrelated complex networks. We obtain the phase diagram for this process with respect to two parameters: $f$, the fraction of vertices initially activated, and $p$, the fraction of undamaged vertices in the graph. We observe two transitions: the giant active component appears continuously at a first threshold. There may also be a second, discontinuous, hybrid transition at a higher threshold. Avalanches of activations increase in size a...

In r-neighbour bootstrap percolation on a graph G, a (typically random) set A of initially 'infected' vertices spreads by infecting (at each time step) vertices with at least r already-infected neighbours. This process may be viewed as a monotone version of the Glauber dynamics of the Ising model, and has been extensively studied on the d-dimensional grid $[n]^d$. The elements of the set A are usually chosen independently, with some density p, and the main question is to dete...