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

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.
This article is issued from Wikipedia - version of the Wednesday, October 07, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.