Explosion and distances in scale-free percolation

Abstract

We investigate the weighted scale-free percolation (SFPW) model on ${\mathbb{Z}}^d$. In the SFPW model, the vertices of ${\mathbb{Z}}^d$ are assigned i.i.d. weights $(W_x{)}_{x\in {\mathbb{Z}}^d}$, following a power-law distribution with tail exponent $\tau >1$. Conditioned on the collection of weights, the edges $(x,y{)}_{x,y\in {\mathbb{Z}}^d}$ are present independently with probability that a Poisson random variable with parameter $\lambda W_x{W}_y/(\Vert x-y\Vert {)}^{\alpha }$ is at least one, for some $\alpha ,\lambda >0$, and where $\Vert \cdot \Vert$ denotes the Euclidean distance. After the graph is constructed this way, we assign independent and identically distributed (i.i.d.) random edge lengths from distribution $L$ to all existing edges in the graph. The focus of the paper is to determine when is the obtained model \emph{explosive}, that is, when it is possible to reach infinitely many vertices in finite time from a vertex. We show that explosion happens precisely for those edge length distributions that produce explosive branching processes with infinite mean power law offspring distributions. For non-explosive edge-length distributions, when $\gamma \in (1,2)$, we characterise the asymptotic behaviour of the time it takes to reach the first vertex that is graph distance $n$ away. For $\gamma >2$, we show that the number of vertices reachable by time $t$ from the origin grows at most exponentially, thus explosion is never possible. For the non-explosive edge-length distributions, when $\gamma \in (1,2)$, we further determine the first order asymptotics of distances when $\gamma \in (1,2)$. As a corollary we obtain a sharp upper and lower bound for graph distances, closing a gap between a lower and upper bound on graph distances in Deijfen Hofstad `13 when $\gamma \in (1,2),\tau >2$.

arXiv comment40 pages. We fixed some typos, and shortened the paper

References in corpus (11)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• The diameter of the world wide web
• Sustaining the Internet with Hyperbolic Mapping
• Structures in supercritical scale-free percolation
• Average Distance in a General Class of Scale-Free Networks with Underlying Geometry
• Bootstrap percolation on geometric inhomogeneous random graphs
• Power-law relations in random networks with communities
• First Passage Percolation on Inhomogeneous Random Graphs
• Explosive Crump-Mode-Jagers branching processes

Cited by in corpus (4)

• Bootstrap percolation on geometric inhomogeneous random graphs
• Existence of Small Separators Depends on Geometry for Geometric Inhomogeneous Random Graphs
• Stopping explosion by penalising transmission to hubs in scale-free spatial random graphs
• Graph distances in scale-free percolation: the logarithmic case