Random geometric graph

Example of Random Geometric Graph on a flat 2-d closed square [0, 1] with N=256 vertices and connectivity threshold r=0.1.

In graph theory, a random geometric graph (RGG) is the mathematically simplest spatial network, namely an undirected graph constructed by randomly placing N nodes in some metric space (according to a specified probability distribution) and connecting two nodes by a link if and only if their distance is in a given range, e.g. smaller than a certain neighborhood radius, r.

A real-world application of RGGs is the modeling of ad hoc networks.^[1]

Examples

• In 1 dimension, one can study RGGs on a line of unit length (open boundary condition) or on a circle of unit circumference.
• In 2 dimensions, an RGG can be constructed by choosing a flat unit square [0, 1] (see figure) or a torus of unit circumferences [0, 1)² as the embedding space.

The simplest choice for the node distribution is to sprinkle them uniformly and independently in the embedding space.

References

1. Nekovee, Maziar (28 June 2007). "Worm epidemics in wireless ad hoc networks". New Journal of Physics 9 (6): 189–189. doi:10.1088/1367-2630/9/6/189. Retrieved 27 June 2014.

• Penrose, Mathew: Random Geometric Graphs (Oxford Studies in Probability, 5), 2003.