Chemical distance in geometric random graphs with long edges and scale-free degree distribution

DOI10.1007/S00220-022-04445-3MaRDI QIDQ2676455zbMATH OpenOpenAlexWikidataFDO

Authors Peter Gracar, Arne Grauer, Peter Mörters

Publication date 27 September 2022

Published in Communications in Mathematical Physics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

asymptotic shapechemical distancefirst-passage percolationinfinite clusterPercolationrandom environment

Mathematics Subject Classification ID

Distance in graphs (05C12) Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Percolation (82B43)

Abstract: We study geometric random graphs defined on the points of a Poisson process in $d$-dimensional space, which additionally carry independent random marks. Edges are established at random using the marks of the endpoints and the distance between points in a flexible way. Our framework includes the soft Boolean model (where marks play the role of radii of balls centred in the vertices), a version of spatial preferential attachment (where marks play the role of birth times), and a whole range of other graph models with scale-free degree distributions and edges spanning large distances. In this versatile framework we give sharp criteria for absence of ultrasmallness of the graphs and in the ultrasmall regime establish a limit theorem for the chemical distance of two points. Other than in the mean-field scale-free network models the boundary of the ultrasmall regime depends not only on the power-law exponent of the degree distribution but also on the spatial embedding of the graph, quantified by the rate of decay of the probability of an edge connecting typical points in terms of their spatial distance.

Recommendations

• Ultra-small scale-free geometric networks
• From heavy-tailed Boolean models to scale-free Gilbert graphs
• Graph distances in scale-free percolation: the logarithmic case
• Typical distances in a geometric model for complex networks
• Percolation phase transition in weight-dependent random connection models

Cites work

• A note on the phase transition for independent alignment percolation
• Asymptotic shape for the chemical distance and first-passage percolation on the infinite Bernoulli cluster
• Diameters in preferential attachment models
• Distances and large deviations in the spatial preferential attachment model
• Distances in random graphs with finite mean and infinite variance degrees
• Ellipses percolation
• Emergence of Scaling in Random Networks
• From heavy-tailed Boolean models to scale-free Gilbert graphs
• Large deviations for the chemical distance in supercritical Bernoulli percolation
• Lectures on the Poisson Process
• On a conditionally Poissonian graph process
• On chemical distances and shape theorems in percolation models with long-range correlations
• On the chemical distance for supercritical Bernoulli percolation
• On the internal distance in the interlacement set
• On the scaling of the chemical distance in long-range percolation models
• Percolation phase transition in weight-dependent random connection models
• Recurrence versus transience for weight-dependent random connection models
• Robustness of scale-free spatial networks
• Scale-free percolation
• Scale-free percolation in continuum space
• Sharp asymptotic for the chemical distance in long-range percolation
• Spatial preferential attachment networks: power laws and clustering coefficients
• The age-dependent random connection model
• The diameter of long-range percolation clusters on finite cycles
• The phase transition in inhomogeneous random graphs
• The supercritical phase of percolation is well behaved
• Typical distances in ultrasmall random networks

Cited in

(10)

• Recurrence versus transience for weight-dependent random connection models
• Ultra-small scale-free geometric networks
• The emergence of a giant component in one-dimensional inhomogeneous networks with long-range effects
• Local limits of spatial inhomogeneous random graphs
• Recurrence and transience of symmetric random walks with long-range jumps
• Four universal growth regimes in degree-dependent first passage percolation on spatial random graphs
• All spatial random graphs with weak long-range effects have chemical distance comparable to Euclidean distance
• Average distance in a general class of scale-free networks
• Finiteness of the percolation threshold for inhomogeneous long-range models in one dimension
• Cluster-size decay in supercritical kernel-based spatial random graphs

This page was built for publication: Chemical distance in geometric random graphs with long edges and scale-free degree distribution

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