Four universal growth regimes in degree-dependent first passage percolation on spatial random graphs

Abstract

One-dependent first passage percolation is a spreading process on a graph where the transmission time through each edge depends on the direct surroundings of the edge. In particular, the classical i.i.d. transmission time Lxy is multiplied by (WxWy)μ, a polynomial of the expected degrees Wx,Wy of the endpoints of the edge xy, which we call the penalty function. Beyond the Markov case, we also allow any distribution for Lxy with regularly varying distribution near 0. We then run this process on three spatial scale-free random graph models: finite and infinite Geometric Inhomogeneous Random Graphs, including Hyperbolic Random Graphs, and Scale-Free Percolation. In these spatial models, the connection probability between two vertices depends on their spatial distance and on their expected degrees.

We show that as the penalty function, that is, μ increases, the transmission time between two far away vertices sweeps through four universal phases: explosive (with tight transmission times), polylogarithmic, polynomial but strictly sublinear, and linear in the Euclidean distance. The strictly polynomial growth phase is a new phenomenon that so far was extremely rare in spatial graph models. All four growth phases are robust in the model parameters and are not restricted to phase boundaries. Further, the transition points between the phases depend nontrivially on the main model parameters: the tail of the degree distribution, a long-range parameter governing the presence of long edges, and the behaviour of the distribution L near 0. In this paper we develop new methods to prove the upper bounds in all sub-explosive phases. Our companion paper complements these results by providing matching lower bounds in the polynomial and linear regimes.