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)2 as the embedding space.
The simplest choice for the node distribution is to sprinkle them uniformly and independently in the embedding space.
References
- ↑ Nekovee, Maziar (28 June 2007). "Worm epidemics in wireless ad hoc networks". New Journal of Physics. 9 (6): 189–189. arXiv:0707.2293
. doi:10.1088/1367-2630/9/6/189.
- Penrose, Mathew: Random Geometric Graphs (Oxford Studies in Probability, 5), 2003.
| Network science | ||||
|---|---|---|---|---|
| Network types | ||||
| Graphs | ||||
|
||||
| Models | ||||
|
||||
| ||||
|
||||
This article is issued from Wikipedia - version of the 7/13/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.