Local limits of spatial inhomogeneous random graphs

DOI10.1017/APR.2022.61MaRDI QIDQ6068844zbMATH OpenOpenAlexFDO

Authors Remco van der Hofstad, Pim Van der Hoorn

Publication date 15 December 2023

Published in Advances in Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2107.08733

zbMATH Keywords

graph distanceslocal convergencerandom graphsspatial graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Nonlinear processes (e.g., (G)-Brownian motion, (G)-Lévy processes) (60G65) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: Consider a set of $n$ vertices, where each vertex has a location in $mathbb{R}^d$ that is sampled uniformly from the unit cube in $mathbb{R}^d$, and a weight associated to it. Construct a random graph by placing edges independently for each vertex pair with a probability that is a function of the distance between the locations, and the vertex weights. Under appropriate integrability assumptions on the edge probabilities that imply sparseness of the model, after appropriately blowing up the locations, we prove that the local limit of this random graph sequence is the (countably) infinite random graph on $mathbb{R}^d$ with vertex locations given by a homogeneous Poisson point process, having weights which are i.i.d. copies of limiting vertex weights. Our setup covers many sparse geometric random graph models from the literature, including Geometric Inhomogeneous Random Graphs (GIRGs), Hyperbolic Random Graphs, Continuum Scale-Free Percolation and Weight-dependent Random Connection Models. We prove that the limiting degree distribution is mixed Poisson, and the typical degree sequence is uniformly integrable, and obtain convergence results on various measures of clustering in our graphs as a consequence of local convergence. Finally, as a by-product of our argument, we prove a doubly logarithmic lower bound on typical distances in this general setting.

Recommendations

• Local limits of spatial Gibbs random graphs
• A local limit theorem for the critical random graph
• Localization in random geometric graphs with too many edges
• On limits of sparse random graphs
• Local convergence of random planar graphs
• Infinite Locally Random Graphs
• Continuum limit of critical inhomogeneous random graphs
• Limit theory of sparse random geometric graphs in high dimensions
• Limits of local algorithms over sparse random graphs
• Novel scaling limits for critical inhomogeneous random graphs

Cites work

• Chemical distance in geometric random graphs with long edges and scale-free degree distribution
• Clustering in a hyperbolic model of complex networks
• Connected components in random graphs with given expected degree sequences
• Distance in random graphs with infinite mean degrees
• Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs
• Geometric inhomogeneous random graphs
• scientific article; zbMATH DE number 2042286 (Why is no real title available?)
• Lectures on the Poisson Process
• Random Geometric Graphs
• Random graphs and complex networks. Volume 1
• Random measures, theory and applications
• Random Plane Networks
• Recurrence of distributional limits of finite planar graphs
• Recurrence versus transience for weight-dependent random connection models
• Sampling geometric inhomogeneous random graphs in linear time
• Scale-free percolation
• Scale-free percolation in continuous space: quenched degree and clustering coefficient
• Scale-free percolation in continuum space
• Structures in supercritical scale-free percolation
• The average distances in random graphs with given expected degrees
• The Mean Values of Certain Dirichlet Series, II
• The phase transition in inhomogeneous random graphs

Cited in

(9)

• The local limit of random sorting networks
• Scaling of the clustering function in spatial inhomogeneous random graphs
• Condensation in scale-free geometric graphs with excess edges
• Local limit of the random degree constrained process
• Average distance in a general class of scale-free networks
• Limit theorems under heavy-tailed scenario in the age-dependent random connection models
• Finiteness of the percolation threshold for inhomogeneous long-range models in one dimension
• Cluster-size decay in supercritical kernel-based spatial random graphs
• Optimal subgraphs in geometric scale-free random graphs

This page was built for publication: Local limits of spatial inhomogeneous random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6068844)