Explosion in weighted Hyperbolic Random Graphs and Geometric Inhomogeneous Random Graphs

Abstract

In this paper we study weighted distances in scale-free spatial network models: hyperbolic random graphs (HRG), geometric inhomogeneous random graphs (GIRG) and scale-free percolation (SFP). In HRGs, $n=\Theta ({\mathrm{e}}^{R/2})$ vertices are sampled independently from the hyperbolic disk with radius $R$ and two vertices are connected either when they are within hyperbolic distance $R$, or independently with a probability depending on the hyperbolic distance. In GIRGs and SFP, each vertex is given an independent weight and location from an underlying measured metric space and ${\mathbb{Z}}^d$, respectively, and two vertices are connected independently with a probability that is a function of their distance and weights. We assign i.i.d. weights to the edges of the random graphs and study the weighted distance between two uniformly chosen vertices. In SFP, we study the weighted distance from the origin of vertex-sequences with norm tending to infinity. In particular, we study the case when the parameters are so that the degree distribution in the graph follows a power law with exponent $\tau \in (2,3)$ (infinite variance), and the edge-weight distribution is such that it produces an explosive age-dependent branching process with power-law offspring distribution. We show that in all three models, typical distances within the giant/infinite component converge in distribution, solving an open question in [Explosion and distances in scale-free percolation (2017)]. The main tools of our proof are to couple the models to infinite versions, to follow the shortest paths to infinity and to connect these paths using weight-dependent percolation on the graphs: delete edges attached to vertices with higher weight with higher probability. We realise this using the edge-weights: only short edges connected to high weight vertices will stay, yielding arbitrarily short upper bounds for the connections.

arXiv comment49 pages, 4 figures

References in corpus (28)

• 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
• Evolution of networks
• Why social networks are different from other types of networks
• Hyperbolic Geometry of Complex Networks
• The complex network of global cargo ship movements
• The phase transition in inhomogeneous random graphs
• Random graphs with clustering
• Sustaining the Internet with Hyperbolic Mapping
• Generating simple random graphs with prescribed degree distribution
• Clustering in complex networks. I. General formalism
• On the scaling of the chemical distance in long-range percolation models
• Diameters in preferential attachment models
• Distances in random graphs with finite variance degrees
• Spatial preferential attachment networks: Power laws and clustering coefficients
• First passage percolation on random graphs with finite mean degrees
• Structures in supercritical scale-free percolation
• The diameter of KPKVB random graphs
• Average Distance in a General Class of Scale-Free Networks with Underlying Geometry
• Bootstrap percolation on geometric inhomogeneous random graphs
• Short paths for first passage percolation on the complete graph
• First Passage Percolation on Inhomogeneous Random Graphs
• Weighted distances in scale-free configuration models
• Explosive Crump-Mode-Jagers branching processes
• Long paths in first passage percolation on the complete graph II. Global branching dynamics
• First passage percolation on random graphs with infinite variance degrees

Cited by in corpus (10)

• Small worlds and clustering in spatial networks
• Recurrence versus Transience for Weight-Dependent Random Connection Models
• Detecting hyperbolic geometry in networks: why triangles are not enough
• Weighted distances in scale-free preferential attachment models
• Scaling of the clustering function in spatial inhomogeneous random graphs
• Finiteness of the percolation threshold for inhomogeneous long-range models in one dimension
• Stopping explosion by penalising transmission to hubs in scale-free spatial random graphs
• Scale-free percolation in continuum space: quenched degree and clustering coefficient
• Non-Uniqueness Phase in Hyperbolic Marked Random Connection Models using the Spherical Transform
• Cover and Hitting Times of Hyperbolic Random Graphs