Multiscale genesis of a tiny giant for percolation on scale-free random graphs

We study the critical behavior for percolation on inhomogeneous random networks on n vertices, where the weights of the vertices follow a powerlaw distribution with exponent τ ∈ (2, 3). Such networks, often referred to as scale-free networks, exhibit critical behavior when the percolation probability tends to zero at an appropriate rate, as n→∞. We identify the critical window for several scale-free random graph models, such as the Norros–Reittu model, Chung–Lu model and generalized random graphs. Surprisingly, there exists a finite time inside the critical window, after which we see a sudden emergence of a “tiny” giant component. This is a novel behavior, which is in contrast with the critical behavior in other known universality classes with τ ∈ (3, 4) and τ >4. Precisely, for edge-retention probabilities πn = λn−(3−τ)/2, there is an explicitly computable λc? 0 such that the critical window is of the form λ ∈ (0,λc), where the largest clusters have size of order nβ with β = (τ 2 −4τ + 5)/[2(τ − 1)] ∈ [√2 − 1, 1 2 ) and have nondegenerate scaling limits, while in the supercritical regime λ > λc, a unique “tiny giant” component of size Θ(√n) emerges, and its size concentrates. For λ ∈ (0,λc), the scaling limit of the maximum component sizes can be described in terms of components of a one-dimensional inhomogeneous percolation model on Z+ studied in a seminal work by Durrett and Kesten (In A Tribute to Paul Erd˝os (1990) 161–176 Cambridge Univ. Press). For λ? λc, we use a relation to general inhomogeneous random graphs, as studied by Bollobás, Janson and Riordan (Random Structures Algorithms 31 (2007) 3–122), to prove that the sudden emergence of the tiny giant is caused by a phase transition inside a smaller core of vertices of weight of order at least √n.