Definition
A random geometric graph (RGG) is a probabilistic graph model in which vertices are placed at random locations in a metric space—most commonly the unit square $[0,1]^2$ equipped with the Euclidean distance, or the unit torus to avoid boundary effects. Two vertices are joined by an undirected edge if and only if the distance between them does not exceed a prescribed connection radius $r>0$. Formally, let $X_1,\dots ,X_n$ be independent and identically distributed random points in the space; the random geometric graph $G(n,r)$ has vertex set ${1,\dots ,n}$ and edge set
$$ E={{i,j}: |X_i-X_j|\le r}. $$
Alternative constructions use a homogeneous Poisson point process of intensity $\lambda$ on $\mathbb{R}^d$; the resulting graph is often denoted $G(\lambda,r)$.
Typical parameter regimes
- Sparse regime: $r = o!\big((\log n / n)^{1/d}\big)$; the graph consists of many small components.
- Connectivity threshold: In dimension $d\ge 2$, the critical radius for asymptotic almost sure (a.a.s.) connectivity is
$$ r_c = \Big(\frac{\log n + (d-1)\log\log n + c_n}{\alpha_d n}\Big)^{1/d}, $$
where $\alpha_d$ is the volume of the unit ball in $\mathbb{R}^d$ and $c_n$ is bounded. (Penrose, 2003)
- Dense regime: $r$ fixed and independent of $n$; the graph exhibits a giant component and non‑trivial clustering.
Key properties
| Property | Typical result (as $n\to\infty$) |
|---|---|
| Degree distribution | Approximately Poisson with mean $\mu = n \alpha_d r^d$ for fixed $r$ and large $n$. |
| Clustering coefficient | Bounded away from zero; scales roughly as the volume of the intersection of two radius‑$r$ balls. |
| Diameter | In the connected regime, the graph diameter scales as $\Theta!\big(\frac{1}{r}\big)$. |
| Percolation | For the Poisson model on $\mathbb{R}^d$, there exists a critical radius $r_{\mathrm{perc}}$ above which an infinite component appears almost surely. |
| Spectral gap | Grows with $r$; in the dense regime the normalized Laplacian eigenvalues concentrate. |
Variants and extensions
- Soft random geometric graph: Edge probability is a decreasing function $f(|X_i-X_j|)$ rather than a hard threshold; e.g., $f(d)=\exp(-\beta d)$.
- k‑nearest‑neighbour graph: Each vertex connects to its $k$ closest points; the resulting graph is always of bounded degree.
- Higher‑dimensional and non‑Euclidean spaces: Models have been studied on manifolds, hyperbolic spaces, and on the surface of a sphere.
- Dynamic RGGs: Vertices move according to a stochastic motion model (e.g., random waypoint) while edges are updated in real time.
Applications
- Wireless and sensor networks: Nodes correspond to communication devices; the connection radius reflects transmission range. Connectivity and coverage analyses rely on RGG theory.
- Ad‑hoc routing protocols: Performance metrics such as latency and robustness are derived from geometric graph properties.
- Epidemiology: Spatial spread of contagion can be modeled by a random geometric contact network.
- Computational geometry and topology: RGGs underpin Vietoris–Rips complexes used in persistent homology.
- Distributed algorithms: Consensus and averaging algorithms are studied on RGGs to assess convergence rates under spatial constraints.
Historical notes
The random geometric graph originated with E. N. Gilbert’s 1961 paper “Random Plane Networks” (J. Math. Phys.). Comprehensive treatment was later provided by M. D. Penrose in the monograph Random Geometric Graphs (Oxford University Press, 2003).
References (selected)
- Gilbert, E. N. (1961). Random plane networks. Journal of the Society for Industrial and Applied Mathematics, 9(4), 533–543.
- Penrose, M. D. (2003). Random Geometric Graphs. Oxford University Press.
- Balister, P., Bollobás, B., Sarkar, A., & Walters, M. (2005). Connectivity of random k‑nearest‑neighbour graphs. Advances in Applied Probability, 37(1), 1–24.
- Dousse, O., Baccelli, F., & Thiran, P. (2005). Impact of interferences on connectivity in ad hoc networks. IEEE/ACM Transactions on Networking, 13(2), 425–436.
The information above reflects the current state of scholarly understanding of random geometric graphs as of the knowledge cutoff date.
