Majority bootstrap percolation on the random graph G(n,p)

By Svante Janson, Tomasz Luczak, Tatyana S. Turova, Thomas Vallier. 2010

92 citations recorded by the source corpus.

Majority bootstrap percolation on the random graph $G_{n,p}$ is a process of spread of "activation" on a given realisation of the graph with a given number of initially active nodes. At each step those vertices which have more active neighbours than inactive neighbours become active as well. We study the size $A^*$ of the final active set. The parameters of the model are, besides $n$ (tending to $\infty$), the size $A(0)=A_0(n)$ of the initially active set and the probability $p=p(n)$ of the edges in the graph. We prove that the process cannot percolate for $A(0) = o(n)$. We study the process for $A(0) = \theta n$ and every range of $p$ and show that the model exhibits different behaviours for different ranges of $p$. For very small $p \ll \frac{1}{n}$, the activation does not spread significantly. For large $p \gg \frac{1}{n}$ then we see a phase transition at $A(0) \simeq \frac{1}{2}n$. In the case $p= \frac{c}{n}$, the activation propagates to a significantly larger part of the graph but (the process does not percolate) a positive part of the graph remains inactive.

Subfields: Condensed Matter Physics, Mathematical Physics, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/7a53f7307c653f4638ebdba636b775fc256a015a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Condensed Matter Physics

In Mathematical Physics

In Statistical and Nonlinear Physics

Citations in the corpus

RESILIENCE TO CONTAGION IN FINANCIAL NETWORKS (2011, background): “ 2 is xed.). 4 very simple models of difusions which have been studied on a variety of graphs, such as trees [8], grids [26, 7], hypercubes [6], as well as on several distributions of random graphs [2, 3, 5, 31, 9]. Another important result of our work {and probably the most important from the regu”
Recent advances in percolation theory and its applications (2015, result): “hown that a giant cluster of size O(n) emerges, with high probability, above a certain critical sublinear number of the initially infected nodes. This behavior is in sharp contrast with that observed [231, 235, 236] on an Erd}os-Renyi random graph in which there will be no evolution when the number ”
The sharp threshold for bootstrap percolation in all dimensions (2010, methodology): “ral other graphs, such as high dimensional tori [4, 5, 7], innite trees [8, 11, 21], the random regular graph [9, 34], ‘locally tree-like’ regular graphs [5], and the Erd}os-Renyi random graph G n;p[35]. Some of the techniques from these papers (and those mentioned earlier) have been used to prove r”