Finite Percolation at a Multiple of the Threshold

Abstract

Bond percolation on infinite heavy-tailed power-law random networks lacks a proper phase transition; or one may say, there is a phase transition at {\em zero percolation probability}. Nevertheless, a finite size percolation threshold $q_c(N)$, where $N$ is the network size, can be defined. For such heavy-tailed networks, one can choose a percolation probability $q(N)=\rho q_c(N)$ such that $\underset{N\to \infty }{\lim }(q-q_c(N))=0$, and yet $\rho$ is arbitrarily large (such a scenario does not exist for networks with non-zero percolation threshold). We find that the critical behavior of random power-law networks is best described in terms of $\rho$ as the order parameter, rather than $q$. This paper makes the notion of the phase transition of the size of the largest connected component at $\rho =1$ precise. In particular, using a generating function based approach, we show that for $\rho >1$, and the power-law exponent, $2\le \tau <3$, the largest connected component scales as $\sim N^{1-1/\tau }$, while for $0<\rho <1$ the scaling is at most $\sim N^{\frac{2-\tau }{\tau }}$; here, the maximum degree of any node, $k_{max}$, has been assumed to scale as N^{1/τ}$.Ingeneral,ourapproachyieldsthatforlarge$N$,$ρ\gg 1$,$2\leq τ<3$,and$k_{max} \sim N^{1/τ}$,thelargestconnectedcomponentscalesas$\sim ρ^{1/(3-τ)}N^{1-1/τ}$.Thus,foranyfixedbutlargeN,werecover,andmakeitprecise,arecentresultthatcomputedascalingbehaviorof$q^{1/(3-τ)}$for"small$q$". We also provide large-scale simulation results validating some of these scaling predictions, and discuss applications of these scaling results to supporting efficient unstructured queries in peer-to-peer networks.