Finite Percolation at a Multiple of the Threshold

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)$suchthat$\displaystyle \lim_{N\to \infty}(q-q_c(N)) =0$,andyet$\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\mathrm{/}\tau }$, while for $0<\rho <1$ the scaling is at most $\sim N^{\frac{2-\tau}{\tau}}$;here,themaximumdegreeofanynode,$k_{max}$, has been assumed to scale as N^{1/\tau}$. In general, our approach yields that for large $N$, $\rho \gg 1$, $2\le \tau <3$, and $k_{max}\sim N^{1\mathrm{/}\tau }$, the largest connected component scales as $\sim \rho^{1/(3-\tau)}N^{1-1/\tau}$.Thus, for any fixed but large N, we recover, and make it precise, a recent result that computed a scaling behavior of $q^{1\mathrm{/}(3-\tau )}$ 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.