ID: 1502.01490

Bootstrap percolation on a graph with random and local connections

February 5, 2015

View on ArXiv
Tatyana Turova, Thomas Vallier
Mathematics
Probability

Let $G_{n,p}^1$ be a superposition of the random graph $G_{n,p}$ and a one-dimensional lattice: the $n$ vertices are set to be on a ring with fixed edges between the consecutive vertices, and with random independent edges given with probability $p$ between any pair of vertices. Bootstrap percolation on a random graph 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 not been active but have at least $r \geq 2$ active neighbours become active as well. We study the size of the final active set in the limit when $n\rightarrow \infty $. The parameters of the model are $n$, the size $A_0=A_0(n)$ of the initially active set and the probability $p=p(n)$ of the edges in the graph. Bootstrap percolation process on $G_{n,p}$ was studied earlier. Here we show that the addition of $n$ local connections to the graph $G_{n,p}$ leads to a more narrow critical window for the phase transition, preserving however, the critical scaling of parameters known for the model on $G_{n,p}$. We discover a range of parameters which yields percolation on $G_{n,p}^1$ but not on $G_{n,p}$.

Similar papers 1

Bootstrap percolation on the random graph $G_{n,p}$

December 16, 2010

93% Match
Svante Janson, Tomasz Łuczak, ... , Vallier Thomas
Probability
Combinatorics

Bootstrap percolation on the random graph $G_{n,p}$ is a process of spread of "activation" on a given realization of the graph with a given number of initially active nodes. At each step those vertices which have not been active but have at least $r\geq2$ active neighbors become active as well. We study the size $A^*$ of the final active set. The parameters of the model are, besides $r$ (fixed) and $n$ (tending to $\infty$), the size $a=a(n)$ of the initially active set and t...

Find SimilarView on arXiv

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

March 24, 2015

92% Match
Sigurdur Örn Stefánsson, Thomas Vallier
Probability

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 probabili...

Find SimilarView on arXiv

Bootstrap Percolation on Random Geometric Graphs

January 13, 2012

90% Match
Milan Bradonjić, Iraj Saniee
Probability
Discrete Mathematics

Bootstrap percolation has been used effectively to model phenomena as diverse as emergence of magnetism in materials, spread of infection, diffusion of software viruses in computer networks, adoption of new technologies, and emergence of collective action and cultural fads in human societies. It is defined on an (arbitrary) network of interacting agents whose state is determined by the state of their neighbors according to a threshold rule. In a typical setting, bootstrap per...

Find SimilarView on arXiv

A modified bootstrap percolation on a random graph coupled with a lattice

July 29, 2015

89% Match
Svante Janson, Robert Kozma, ... , Sokolov Yury
Combinatorics
Probability

In this paper a random graph model $G_{\mathbb{Z}^2_N,p_d}$ is introduced, which is a combination of fixed torus grid edges in $(\mathbb{Z}/N \mathbb{Z})^2$ and some additional random ones. The random edges are called long, and the probability of having a long edge between vertices $u,v\in(\mathbb{Z}/N \mathbb{Z})^2$ with graph distance $d$ on the torus grid is $p_d=c/Nd$, where $c$ is some constant. We show that, {\em whp}, the diameter $D(G_{\mathbb{Z}^2_N,p_d})=\Theta (\lo...

Find SimilarView on arXiv

The large connectivity limit of bootstrap percolation

November 6, 2014

89% Match
Giorgio Parisi, Mauro Sellitto
Statistical Mechanics

Bootstrap percolation provides an emblematic instance of phase behavior characterised by an abrupt transition with diverging critical fluctuations. This unusual hybrid situation generally occurs in particle systems in which the occupation probability of a site depends on the state of its neighbours through a certain threshold parameter. In this paper we investigate the phase behavior of the bootstrap percolation on the regular random graph in the limit in which the threshold ...

Find SimilarView on arXiv

Bootstrap percolation on the stochastic block model

January 31, 2022

88% Match
Giovanni Luca Torrisi, Michele Garetto, Emilio Leonardi
Probability
Performance

We analyze the bootstrap percolation process on the stochastic block model (SBM), a natural extension of the Erd\H{o}s--R\'{e}nyi random graph that incorporates the community structure observed in many real systems. In the SBM, nodes are partitioned into two 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 the system parameters, we prove t...

Find SimilarView on arXiv

A large deviation approach to super-critical bootstrap percolation on the random graph $G_{n,p}$

February 6, 2018

88% Match
Giovanni Luca Torrisi, Michele Garetto, Emilio Leonardi
Probability
Performance

We consider the Erd\"{o}s--R\'{e}nyi random graph $G_{n,p}$ and we analyze the simple irreversible epidemic process on the graph, known in the literature as bootstrap percolation. We give a quantitative version of some results by Janson et al. (2012), providing a fine asymptotic analysis of the final size $A_n^*$ of active nodes, under a suitable super-critical regime. More specifically, we establish large deviation principles for the sequence of random variables $\{\frac{n- ...

Find SimilarView on arXiv

The time of graph bootstrap percolation

March 4, 2015

88% Match
Karen Gunderson, Sebastian Koch, Michał Przykucki
Probability
Combinatorics

Graph bootstrap percolation, introduced by Bollob\'as in 1968, is a cellular automaton defined as follows. Given a "small" graph $H$ and a "large" graph $G = G_0 \subseteq K_n$, in consecutive steps we obtain $G_{t+1}$ from $G_t$ by adding to it all new edges $e$ such that $G_t \cup e$ contains a new copy of $H$. We say that $G$ percolates if for some $t \geq 0$, we have $G_t = K_n$. For $H = K_r$, the question about the size of the smallest percolating graphs was independe...

Find SimilarView on arXiv

Bootstrap percolation on G(n,p) revisited

May 10, 2016

88% Match
Mihyun Kang, Tamás Makai
Combinatorics

Bootstrap percolation on a graph with infection threshold $r\in \mathbb{N}$ is an infection process, which starts from a set of initially infected vertices and in each step every vertex with at least $r$ infected neighbours becomes infected. We consider bootstrap percolation on the binomial random graph $G(n,p)$, which was investigated among others by Janson, \L uczak, Turova and Valier (2012). We improve their results by strengthening the probability bounds for the number of...

Find SimilarView on arXiv

Bootstrap Percolation on the Binomial Random $k$-uniform Hypergraph

March 19, 2024

88% Match
Mihyun Kang, Christoph Koch, Tamás Makai
Probability

We investigate the behaviour of $r$-neighbourhood bootstrap percolation on the binomial $k$-uniform random hypergraph $H_k(n,p)$ for given integers $k\geq 2$ and $r\geq 2$. In $r$-neighbourhood bootstrap percolation, infection spreads through the hypergraph, starting from a set of initially infected vertices, and in each subsequent step of the process every vertex with at least $r$ infected neighbours becomes infected. For our analysis the set of initially infected vertices i...

Find SimilarView on arXiv