A large deviation approach to super-critical bootstrap percolation on the random graph Gn, p

STOCHASTIC PROCESSES AND THEIR APPLICATIONS

卷:129

Article

Torrisi, Giovanni Luca¹  Garetto, Michele²  Leonardi, Emilio³ 

[1] CNR, Ist Applicaz Calcolo, Rome, Italy

[2] Univ Torino, Dipartimento Informat, Turin, Italy

[3] Politecn Torino, Dipartimento Elettron, Turin, Italy

关键词: Bootstrap percolation;    Large deviations;    Random graphs;   

DOI  :  10.1016/j.spa.2018.06.006

来源: Elsevier

【 摘 要 】

We consider the Erdos-Renyi random graph G(n,p) and we analyze the simple irreversible epidemic process on the graph, known in the literature as bootstrap percolation. We give a quantitative version of some results by Janson et al. (2012), providing a fine asymptotic analysis of the final size A(n)* of active nodes, under a suitable super-critical regime. More specifically, we establish large deviation principles for the sequence of random variables {n-A(n)*/f(n)}(n >= 1) with explicit rate functions and allowing the scaling function f to vary in the widest possible range. (C) 2018 Elsevier B.V. All rights reserved.

【 授权许可】

Free