Cluster-size decay in supercritical kernel-based spatial random graphs

Abstract

We consider a large class of spatially-embedded random graphs that includes among others long-range percolation, continuum scale-free percolation and the age-dependent random connection model. We assume that the model is supercritical: there is an infinite component. We identify the stretch-exponent $\hat{I}\P \in (0,1)$ of the decay of the cluster-size distribution. That is, with $|\mathcal{C}(0)|$ denoting the number of vertices in the component of the vertex at $0\in {\mathbb{R}}^d$, we prove \[ \mathbb{P}(k< |\mathcal{C}(0)|<\infty)=\exp\big(-Θ(k^ζ)\big), \qquad \text{as }k\to\infty. \] The value of $\hat{I}\P$ undergoes several phase transitions with respect to three main model parameters: the Euclidean dimension $d$, the power-law tail exponent $\ddot{I}„$ of the degree distribution and a long-range parameter $\hat{I}\pm$ governing the presence of long edges in Euclidean space. In this paper we present the proof for the region in the phase diagram where the model is a generalization of continuum scale-free percolation and/or hyperbolic random graphs: $\hat{I}\P$ in this regime depends both on $\ddot{I}„,\hat{I}\pm$. We also prove that the second-largest component in a box of volume $n$ is of size $\hat{I}˜((\log n{)}^{1/\hat{I}\P })$ with high probability. We develop a deterministic algorithm, the cover expansion, as new methodology. This algorithm enables us to prevent too large components that may be de-localized or locally dense in space.

74 pages, 3 figures. Fixed typos, to appear in Annals of Probability