BOOTSTRAP PERCOLATION ON THE RANDOM GRAPH Gn,p

• 成果类型: Article
• 署名作者: Janson, Svante; Luczak, Tomasz; Turova, Tatyana; Vallier, Thomas
• 署名单位: Uppsala University; Adam Mickiewicz University; Lund University; University of Helsinki
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/11-AAP822
• 发表日期: 2012
• 页码: 1989-2047
• 关键词: epidemic model; final-size; threshold; networks

摘要

Bootstrap percolation on the random graph C-n,C-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 >= 2 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 infinity), the size a = a(n) of the initially active set and the probability p = p(n) of the edges in the graph. We show that the model exhibits a sharp phase transition: depending on the parameters of the model, the final size of activation with a high probability is either n - o(n) or it is o(n). We provide a complete description of the phase diagram on the space of the parameters of the model. In particular, we find the phase transition and compute the asymptotics (in probability) for A*; we also prove a central limit theorem for A* in some ranges. Furthermore, we provide the asymptotics for the number of steps until the process stops.