Our website is made possible by displaying online advertisements to our visitors.
Please consider supporting us by disabling your ad blocker.
Random geometric graph
| Part of a series on | ||||
| Network science | ||||
|---|---|---|---|---|
| Network types | ||||
| Graphs | ||||
|
||||
| Models | ||||
|
||||
| ||||
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.
Random geometric graphs resemble real human social networks in a number of ways. For instance, they spontaneously demonstrate community structure - clusters of nodes with high modularity. Other random graph generation algorithms, such as those generated using the Erdős–Rényi model or Barabási–Albert (BA) model do not create this type of structure. Additionally, random geometric graphs display degree assortativity according to their spatial dimension:[1] "popular" nodes (those with many links) are particularly likely to be linked to other popular nodes.
Percolation theory on the random geometric graph (the study of its global connectivity) is sometimes called the Gilbert disk model[2] after the work of Edgar Gilbert, who introduced these graphs and percolation in them in a 1961 paper.[3] A real-world application of RGGs is the modeling of ad hoc networks.[4] Furthermore they are used to perform benchmarks for graph algorithms.
- ^ Antonioni, Alberto; Tomassini, Marco (28 September 2012). "Degree correlations in random geometric graphs". Physical Review E. 86 (3): 037101. arXiv:1207.2573. Bibcode:2012PhRvE..86c7101A. doi:10.1103/PhysRevE.86.037101. PMID 23031054. S2CID 14750415.
- ^ Bobrowski, Omer; Kahle, Matthew (2018). "Topology of random geometric complexes: a survey". Journal of Applied and Computational Topology. 1 (3–4): 331–364. arXiv:1409.4734. doi:10.1007/s41468-017-0010-0. MR 3975557.
- ^ Gilbert, Edgar N (1961). "Random Plane Networks". Journal of the Society for Industrial and Applied Mathematics. 9 (4): 533–543. doi:10.1137/0109045.
- ^ Nekovee, Maziar (28 June 2007). "Worm epidemics in wireless ad hoc networks". New Journal of Physics. 9 (6): 189. arXiv:0707.2293. Bibcode:2007NJPh....9..189N. doi:10.1088/1367-2630/9/6/189. S2CID 203944.
Previous Page Next Page
