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

Abstract

We study the critical behavior for percolation on inhomogeneous random networks on $n$ vertices, where the weights of the vertices follow a power-law distribution with exponent $\tau \in (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\to \infty$. We identify the critical window for a host of 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 $\tau \in (3,4)$ and $\tau >4$. Precisely, for edge-retention probabilities ${\pi }_n=\lambda n^{-(3-\tau )/2}$, there is an explicitly computable ${\lambda }_c>0$ such that the critical window is of the form $\lambda \in (0,{\lambda }_c),$ where the largest clusters have size of order $n^{\beta }$ with $\beta =({\tau }^2-4\tau +5)/[2(\tau -1)]\in [\sqrt{2}-1,\frac{1}{2})$ and have non-degenerate scaling limits, while in the supercritical regime $\lambda >{\lambda }_c$, a unique `tiny giant' component of size $\sqrt{n}$ emerges. For $\lambda \in (0,{\lambda }_c),$ the scaling limit of the maximum component sizes can be described in terms of components of a one-dimensional inhomogeneous percolation model on ${\mathbb{Z}}_{+}$ studied in a seminal work by Durrett and Kesten. For $\lambda >{\lambda }_c$, we prove that the sudden emergence of the tiny giant is caused by a phase transition inside a smaller core of vertices of weight $\Omega (\sqrt{n})$.

46 pages, 1 figure

References in corpus (5)

• Critical phenomena in complex networks
• Limits of multiplicative inhomogeneous random graphs and Lévy trees: Limit theorems
• Counting triangles in power-law uniform random graphs
• The augmented multiplicative coalescent and critical dynamic random graph models
• Barely supercritical percolation on Poissonian scale-free networks