Connectivity of 1d random geometric graphs

Abstract

A 1d random geometric graph (1d RGG) is built by joining a random sample of $n$ points from an interval of the real line with probability $p$. We count the number of $k$-hop paths between two vertices of the graph in the case where the space is the 1d interval $[0,1]$. We show how the $k$-hop path count between two vertices at Euclidean distance $|x-y|$ is in bijection with the volume enclosed by a uniformly random $d$-dimensional lattice path joining the corners of a $(k-1)$-dimensional hyperrectangular lattice. We are able to provide the probability generating function and distribution of this $k$-hop path count as a sum over lattice paths, incorporating the idea of restricted integer partitions with limited number of parts. We therefore demonstrate and describe an important link between spatial random graphs, and lattice path combinatorics, where the $d$-dimensional lattice paths correspond to spatial permutations of the geometric points on the line.

arXiv comment27 pages, 11 figures

References in corpus (15)

• Network Geometry
• Clustering implies geometry in networks
• Network Geometry and Complexity
• One-dimensional long-range percolation: a numerical study
• The Meta Distribution of the SIR in Linear Motorway VANETs
• Temporal Correlation of Interference in Bounded Mobile Ad Hoc Networks with Blockage
• The shape of shortest paths in random spatial networks
• Exact solution of a one-dimensional continuum percolation model
• Connectivity in One-Dimensional Soft Random Geometric Graphs
• Limit theory of isolated and extreme points in hyperbolic random geometric graphs
• Network connectivity in non-convex domains with reflections
• Network connectivity through small openings
• Euclidean Matchings in Ultra-Dense Networks
• Counting Geodesic Paths in 1D VANETs
• Sparse power-law network model for reliable statistical predictions based on sampled data