Bootstrap percolation in power-law random graphs

Hamed Amini, Nikolaos Fountoulakis

Published 2011-11-05, updated 2013-08-14Version 2

A bootstrap percolation process on a graph $G$ is an "infection" process which evolves in rounds. Initially, there is a subset of infected nodes and in each subsequent round each uninfected node which has at least $r$ infected neighbours becomes infected and remains so forever. The parameter $r\geq 2$ is fixed. Such processes have been used as models for the spread of ideas or trends within a network of individuals. We analyse bootstrap percolation process in the case where the underlying graph is an inhomogeneous random graph, which exhibits a power-law degree distribution, and initially there are $a(n)$ randomly infected nodes. The main focus of this paper is the number of vertices that will have been infected by the end of the process. The main result of this work is that if the degree sequence of the random graph follows a power law with exponent $\beta$, where $2 < \beta < 3$, then a sublinear number of initially infected vertices is enough to spread the infection over a linear fraction of the nodes of the random graph, with high probability. More specifically, we determine explicitly a critical function $a_c(n)$ such that $a_c(n)=o(n)$ with the following property. Assuming that $n$ is the number of vertices of the underlying random graph, if $a(n) \ll a_c(n)$, then the process does not evolve at all, with high probability as $n$ grows, whereas if $a(n)\gg a_c(n)$, then there is a constant $\eps>0$ such that, with high probability, the final set of infected vertices has size at least $\eps n$. It turns out that when the maximum degree is $o(n^{1/(\beta -1)})$, then $a_c(n)$ depends also on $r$. But when the maximum degree is $\Theta (n^{1/(\beta -1)})$, then $a_c (n)=n^{\beta -2 \over \beta -1}$.