Bootstrap percolation and diffusion in random graphs with given vertex degrees

Hamed Amini

The electronic journal of combinatorics, Tome 17 (2010)

Résumé

We consider diffusion in random graphs with given vertex degrees. Our diffusion model can be viewed as a variant of a cellular automaton growth process: assume that each node can be in one of the two possible states, inactive or active. The parameters of the model are two given functions $\theta: {\Bbb N} \rightarrow {\Bbb N}$ and $\alpha:{\Bbb N} \rightarrow [0,1]$. At the beginning of the process, each node $v$ of degree $d_v$ becomes active with probability $\alpha(d_v)$ independently of the other vertices. Presence of the active vertices triggers a percolation process: if a node $v$ is active, it remains active forever. And if it is inactive, it will become active when at least $\theta(d_v)$ of its neighbors are active. In the case where $\alpha(d) =\alpha$ and $\theta(d) =\theta$, for each $d \in {\Bbb N}$, our diffusion model is equivalent to what is called bootstrap percolation. The main result of this paper is a theorem which enables us to find the final proportion of the active vertices in the asymptotic case, i.e., when $n \rightarrow \infty$. This is done via analysis of the process on the multigraph counterpart of the graph model.

Détail

DOI : 10.37236/297

Classification : 05C80