Sách Bootstrap Percolation and Diffusion in Random Graphs with Given Vertex Degrees

Abstract
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 θ : N → N and α : N → [0, 1].
At the beginning of the process, each node v of degree dv becomes active with
probability α(dv ) 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 θ(dv) of its neighbors are active.
In the case where α(d) = α and θ(d) = θ, for each d ∈ 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 → ∞ . This is done via analysis of the process on the
multigraph counterpart of the graph model.