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}$.

对基于不同对应图的 bootstrap percolation process 进行分析，证明无论初始感染病毒节点数目是多少，只要充分小于一个与节点数大小同阶的参数，感染病毒会以相当于节点数大小的线性比例蔓延。

幂律随机图中的自举渗流

Bootstrap percolation in power-law random graphs

Consider any random graph model where potential edges appear independently,
with possibly different probabilities, and assume that the minimum expected
degree is omega(ln n). We prove that the adjacency matrix and the Laplacian of
that random graph are concentrated around the corresponding matrices of the
weighted graph whose edge weights are the probabilities in the random model.
While this may seem surprising, we will see that this matrix concentration
phenomenon is a generalization of known results about the Er\"{o}s-R\'{e}nyi
model. In particular, we will argue that matrix concentration is implicit the
theory of quasi-random graph properties.
We present two main applications of the main result. In bond percolation over
a graph G, we show that the Laplacian of the random subgraph is typically very
close to the Laplacian of G. As a corollary, we improve upon a bound for the
spectral gap due to Chung and Horn that was derived via much more complicated
methods.
In inhomogeneous random graphs, there are points X_1,...,X_n uniformly
distributed on the interval [0,1] and each pair is connected with probability p
kappa(X_i,X_j). We show that if \ln n/n<< p<< 1 and kappa is bounded, then the
adjacency matrix of the random graph is close to an integral operator defined
in terms of kappa.
Our main proof tool is a new concentration inequality for matrix martingales
that generalizes Freedman's inequality for the standard scalar setting.

在随机图中，将边权值视为概率，如果最小期望度数为 ω(ln n)，则随机图的邻接矩阵和拉普拉斯矩阵集中于边权为概率的加权图，应用于债券渗透和不均匀随机图问题中，通过引入矩阵 concenetration 和集中不等式得到新的结论。