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

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.

arXiv comment48 pages, 5 figures

References in corpus (16)

• Emergence of scaling in random networks
• The phase transition in inhomogeneous random graphs
• On the scaling of the chemical distance in long-range percolation models
• Diameters in preferential attachment models
• Spatial preferential attachment networks: Power laws and clustering coefficients
• On chemical distances and shape theorems in percolation models with long-range correlations
• On the internal distance in the interlacement set
• Large deviations for the chemical distance in supercritical Bernoulli percolation
• Recurrence versus Transience for Weight-Dependent Random Connection Models
• The age-dependent random connection model
• Average Distance in a General Class of Scale-Free Networks with Underlying Geometry
• Distances in critical long range percolation
• Percolation phase transition in weight-dependent random connection models
• Sharp asymptotic for the chemical distance in long-range percolation
• Ellipses Percolation
• Euclidean and chemical distances in ellipses percolation