2016/09/28 by Nikolaos Fountoulakis, Mihyun Kang, Fountoulakis, Nikolaos +4
Mathematics · Physics and Astronomy · #05C80 #60K37 #82B26 #82B43 #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.1609.08892
openalex publication_date 2016/09/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A bootstrap percolation process on a graph with infection threshold r\≥ 1\nis a dissemination process that evolves in time steps. The process begins with\na subset of infected vertices and in each subsequent step every uninfected\nvertex that has at least r infected neighbours becomes infected and remains\nso forever.\n Critical phenomena in bootstrap percolation processes were originally\nobserved by Aizenman and Lebowitz in the late 1980s as finite-volume phase\ntransitions in \ℤd that are caused by the accumulation of small\nlocal islands of infected vertices. They were also observed in the case of\ndense (homogeneous) random graphs by Janson, L uczak, Turova and Valier\n(2012). In this paper, we consider the class of inhomogeneous random graphs\nknown as the Chung-Lu model: each vertex is equipped with a positive weight and\neach pair of vertices appears as an edge with probability proportional to the\nproduct of the weights. In particular, we focus on the sparse regime, where the\nnumber of edges is proportional to the number of vertices.\n The main results of this paper determine those weight sequences for which a\ncritical phenomenon occurs: there is a critical density of vertices that are\ninfected at the beginning of the process, above which a small (sublinear) set\nof infected vertices creates an avalanche of infections that in turn leads to\nan outbreak. We show that this occurs essentially only when the tail of the\nweight distribution dominates a power law with exponent 3 and we determine the\ncritical density in this case.\n