Random geometric graph

From Wikipedia, the free encyclopedia
Jump to: navigation, search
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[edit]

  • 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)2 as the embedding space.

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

References[edit]

  1. ^ Nekovee, Maziar (28 June 2007). "Worm epidemics in wireless ad hoc networks". New Journal of Physics. 9 (6): 189–189. arXiv:0707.2293Freely accessible. doi:10.1088/1367-2630/9/6/189. 
  • Penrose, Mathew: Random Geometric Graphs (Oxford Studies in Probability, 5), 2003.