View source for Random geometric graph

{{Short description|In graph theory, the mathematically simplest spatial network}}
{{Network Science}}In [[graph theory]], a '''random geometric graph''' ('''RGG''') is the mathematically simplest [[spatial network]], namely an [[undirected graph]] constructed by randomly placing ''N'' [[Node (graph theory)|nodes]] in some [[metric space]] (according to a specified probability distribution) and connecting two nodes by a [[Link (geometry)|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 (networks)|modularity]]. Other random graph generation algorithms, such as those generated using the [[Erdős–Rényi model]] or [[Barabási–Albert model|Barabási–Albert (BA) model]] do not create this type of structure. Additionally, random geometric graphs display degree [[assortativity]] according to their spatial dimension:<ref>{{cite journal|last1=Antonioni|first1=Alberto|last2=Tomassini|first2=Marco|date=28 September 2012|title=Degree correlations in random geometric graphs|journal=Physical Review E|volume=86|issue=3|pages=037101|arxiv=1207.2573|doi=10.1103/PhysRevE.86.037101|pmid=23031054|bibcode=2012PhRvE..86c7101A|s2cid=14750415}}</ref> "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'''<ref>{{cite journal
 | last1 = Bobrowski | first1 = Omer
 | last2 = Kahle | first2 = Matthew
 | doi = 10.1007/s41468-017-0010-0
 | issue = 3-4
 | journal = Journal of Applied and Computational Topology
 | mr = 3975557
 | pages = 331–364
 | title = Topology of random geometric complexes: a survey
 | volume = 1
 | year = 2018| arxiv = 1409.4734
 }}</ref> after the work of [[Edgar Gilbert]], who introduced these graphs and percolation in them in a 1961 paper.<ref>{{cite journal|last1=Gilbert|first1=Edgar N|title=Random Plane Networks|journal=Journal of the Society for Industrial and Applied Mathematics|date=1961|volume=9|issue=4|pages=533–543|doi=10.1137/0109045}}</ref> A real-world application of RGGs is the modeling of [[Mobile ad hoc network|ad hoc networks]].<ref>{{cite journal|last1=Nekovee|first1=Maziar|date=28 June 2007|title=Worm epidemics in wireless ad hoc networks|journal=New Journal of Physics|volume=9|issue=6|pages=189|arxiv=0707.2293|bibcode=2007NJPh....9..189N|doi=10.1088/1367-2630/9/6/189|s2cid=203944}}</ref> Furthermore they are used to perform [[Benchmark (computing)|benchmarks]] for graph algorithms.

== Definition ==
[[File:Random_Geometric_Graph.gif|alt=|thumb|300x300px|The generation of a random geometric graph for different connectivity parameters r.]]
In the following, let  {{math|1=''G'' = (''V'', ''E'')}} denote an undirected [[Graph (discrete mathematics)|Graph]] with a set of vertices {{Math|V}} and a set of edges {{Nowrap begin}}{{Math|E ⊆ V × V}}{{Nowrap end}}. The set sizes are denoted by {{Math|1={{abs|''V''}} = n}} and {{Math|1={{abs|''E''}} = m}}. Additionally, if not noted otherwise, the [[metric space]] {{closed-open|0,1}}{{Math|<sup>d</sup>}} with the [[euclidean distance]] is considered, i.e. for any points <math>x, y \in [0, 1)^d</math> the euclidean distance of x and y is defined as

: <math>d(x, y) = ||x - y||_2 = \sqrt{\sum_{i=1}^d (x_{i} - y_{i})^2}</math>.

A '''random geometric graph (RGG)''' is an undirected [[Geometric graph theory|geometric graph]] with nodes randomly sampled from the [[Uniform distribution (continuous)|uniform distribution]] of the underlying space {{closed-open|0,1}}{{Math|<sup>d</sup>}}.<ref>{{Cite book|title=Random geometric graphs|last=Penrose, Mathew.|date=2003|publisher=Oxford University Press|isbn=0198506260|location=Oxford|oclc=51316118}}</ref> Two vertices {{Math|p, q ∈ V}} are connected if, and only if, their distance is less than a previously specified parameter {{Math|r ∈ (0,1)}}, excluding any [[Loop (graph theory)|loops]]. Thus, the parameters {{Math|r}} and {{Math|n}} fully characterize a RGG.

== Algorithms ==

=== Naive algorithm ===
The naive approach is to calculate the distance of every vertex to every other vertex. As there are <math display="inline">\frac{n(n-1)}{2}</math> possible connections that are checked, the time complexity of the naive algorithm is <math display="inline">\Theta(n^2)</math>. The samples are generated by using a [[Random number generation|random number generator]] (RNG) on <math>[0, 1)^d</math>. Practically, one can implement this using d random number generators on <math>[0, 1)</math>, one RNG for every dimension.

==== Pseudocode ====
 ''V'' := generateSamples(''n'')  ''// Generates n samples in the unit cube.''
 '''for each''' ''p'' ∈ ''V'' '''do'''
     '''for each''' ''q'' ∈ ''V''\{p} '''do'''
         '''if''' distance(''p'', ''q'') ≤ ''r'' '''then'''
             addConnection(''p'', ''q'') ''// Add the edge (p, q) to the edge data structure.''
         '''end if'''
     '''end for'''
 '''end for'''

As this algorithm is not [[Scalability|scalable]] (every vertex needs information of every other vertex), Holtgrewe et al. and Funke et al. have introduced new algorithms for this problem.

=== Distributed algorithms ===

==== Holtgrewe et al. ====
This algorithm, which was proposed by Holtgrewe et al., was the first distributed RGG generator algorithm for dimension 2.<ref name=":0"/> It partitions the unit square into equal sized cells with side length of at least <math>r</math>. For a given number <math>P = p^2</math> of processors, each processor is assigned <math display="inline">{k \over p} \times {k \over p}</math> cells, where <math display="inline">k = \left \lfloor {1/r} \right \rfloor.</math> For simplicity, <math display="inline">P</math> is assumed to be a square number, but this can be generalized to any number of processors. Each processor then generates <math display="inline">\frac{n}{P}</math> vertices, which are then distributed to their respective owners. Then the vertices are sorted by the cell number they fall into, for example with [[Quicksort]]. Next, each processor then sends their adjacent processors the information about the vertices in the border cells, such that each processing unit can calculate the edges in their partition independent of the other units. The expected running time is <math display="inline">O(\frac{n}{P}\log{\frac{n}{P}})</math>. An upper bound for the communication cost of this algorithm is given by <math>T_{all-to-all}(n/P, P) + T_{all-to-all}(1, P) + T_{point-to-point}(n/(k\cdot{P}) + 2)</math>, where <math>T_{all-to-all}(l, c)</math> denotes the time for an all-to-all communication with messages of length {{var|l}} bits to {{var|c}} communication partners. <math>T_{point-to-point}(l)</math> is the time taken for a point-to-point communication for a message of length {{var|l}} bits.

Since this algorithm is not communication free, Funke et al. proposed<ref name=":0">{{Cite arXiv|last1=von Looz|first1=Moritz|last2=Strash|first2=Darren|last3=Schulz|first3=Christian|last4=Penschuck|first4=Manuel|last5=Sanders|first5=Peter|last6=Meyer|first6=Ulrich|last7=Lamm|first7=Sebastian|last8=Funke|first8=Daniel|date=2017-10-20|title=Communication-free Massively Distributed Graph Generation|class=cs.DC|language=en|eprint=1710.07565v3}}</ref> a scalable distributed RGG generator for higher dimensions, which works without any communication between the processing units.

==== Funke et al. ====
The approach used in this algorithm<ref name=":0" /> is similar to the approach in Holtgrewe: Partition the unit cube into equal sized chunks with side length of at least {{var|r}}. So in {{var|d}} = 2 this will be squares, in {{var|d}} = 3 this will be cubes. As there can only fit at most <math display="inline">{\left \lfloor {1/r} \right \rfloor}</math> chunks per dimension, the number of chunks is capped at <math display="inline">{\left \lfloor {1/r} \right \rfloor}^d</math>. As before, each processor is assigned <math display="inline">{\left \lfloor {1/r} \right \rfloor}^d \over P</math> chunks, for which it generates the vertices. To achieve a communication free process, each processor then generates the same vertices in the adjacent chunks by exploiting pseudorandomization of [[Random seed|seeded]] [[hash function]]s. This way, each processor calculates the same vertices and there is no need for exchanging vertex information.

For dimension 3, Funke et al. showed that the expected running time is <math display="inline">O(\frac{m+n}{P} + \log{P})</math>, without any cost for communication between processing units.

== Properties ==

=== Isolated vertices and connectivity ===
The probability that a single vertex is isolated in a RGG is <math display="inline">(1- \pi r^2)^{n-1}</math>.<ref>{{Cite arXiv|last1=Perez|first1=Xavier|last2=Mitsche|first2=Dieter|last3=Diaz|first3=Josep|date=2007-02-13|title=Dynamic Random Geometric Graphs|language=en|eprint=cs/0702074}}</ref> Let <math display="inline">X</math> be the random variable counting how many vertices are isolated. Then the expected value of <math display="inline">X</math> is <math display="inline">E(X) = n(1- \pi r^2)^{n-1} = ne^{-\pi r^2 n}-O(r^4n)</math>. The term <math display="inline">\mu = ne^{-\pi r^2 n}</math> provides information about the connectivity of the RGG. For <math display="inline">\mu \longrightarrow 0</math>, the RGG is asymptotically almost surely connected. For <math>\mu \longrightarrow \infin</math>, the RGG is asymptotically almost surely disconnected. And for <math display="inline">\mu = \Theta(1)</math>, the RGG has a giant component that covers more than <math display="inline">\frac{n} {2}</math> vertices and <math>X</math> is Poisson distributed with parameter <math>\mu</math>. It follows that if <math display="inline">\mu = \Theta(1)</math>, the probability that the RGG is connected is <math display="inline">P[X=0] \sim e^{-\mu}</math> and the probability that the RGG is not connected is <math display="inline">P[X>0] \sim 1-e^{-\mu}</math>.

For any <math display="inline">l_p</math>-Norm ( <math display="inline">1 \leq p \leq \infin</math>) and for any number of dimensions <math>d>2</math>, a RGG possesses a sharp threshold of connectivity at <math display="inline">r \sim\left({\ln (n) \over \alpha_{p,d}n}\right)^{1 \over d}</math> with constant <math>\alpha_{p,d}</math>. In the special case of a two-dimensional space and the euclidean norm (<math>d=2</math> and <math>p=2</math>) this yields <math display="inline">r \sim \sqrt{{\ln (n) \over \pi n}}</math>.

=== Hamiltonicity ===
It has been shown, that in the two-dimensional case, the threshold <math display="inline">r \sim \sqrt{{\ln (n) \over \pi n}}</math> also provides information about the existence of a Hamiltonian cycle ([[Hamiltonian path|Hamiltonian Path]]).<ref>{{Cite arXiv|last1=Perez|first1=X.|last2=Mitsche|first2=D.|last3=Diaz|first3=J.|date=2006-07-07|title=Sharp threshold for hamiltonicity of random geometric graphs|eprint=cs/0607023}}</ref> For any <math>\epsilon>0</math>, if <math display="inline">r \sim \sqrt{{\ln (n) \over (\pi + \epsilon) n}}</math>, then the RGG has asymptotically almost surely no Hamiltonian cycle and if <math display="inline">r \sim \sqrt{{\ln (n) \over (\pi - \epsilon) n}}</math> for any <math display="inline">\epsilon>0</math>, then the RGG has asymptotically almost surely a Hamiltonian cycle.

=== Clustering coefficient ===
The [[clustering coefficient]] of RGGs only depends on the dimension {{var|d}} of the underlying space {{closed-open|0,1}}{{Math|<sup>d</sup>}}. The clustering coefficient is <ref>{{Cite journal|last1=Christensen|first1=Michael|last2=Dall|first2=Jesper|date=2002-03-01|title=Random Geometric Graphs|journal=Physical Review E|volume=66|issue=1 Pt 2|pages=016121|language=en|doi=10.1103/PhysRevE.66.016121|pmid=12241440|arxiv=cond-mat/0203026|bibcode=2002PhRvE..66a6121D|s2cid=15193516}}</ref>

<math display="inline">C_d = 1-H_d(1)</math> for even <math>d</math> and <math display="inline">C_d = {3 \over 2} -H_d({1 \over 2})</math> for odd <math>d</math> where<math display="block">H_d(x) = {1 \over \sqrt{\pi}} \sum_{i=x}^{d \over 2}
{\Gamma(i) \over \Gamma(i + {1 \over 2})} \left({3 \over 4}\right)^{i+{1 \over 2}}</math>For large <math>d</math>, this simplifies to <math>C_d \sim 3 \sqrt{2 \over \pi d} \left({3 \over 4}\right)^{d+1 \over 2}</math>.

== Generalized random geometric graphs ==
In 1988 Waxman<ref>{{cite journal|last1=Waxman|first1=B.M|date=1988|title=Routing of multipoint connections|journal=IEEE Journal on Selected Areas in Communications|volume=6|issue=9|pages=1617–1622|doi=10.1109/49.12889}}</ref> generalised the standard RGG by introducing a probabilistic connection function as opposed to the deterministic one suggested by Gilbert. The example introduced by Waxman was a stretched exponential where two nodes <math>i</math> and <math>j</math> connect with probability given by <math display="inline">H_{ij}=\beta e^{-{r_{ij} \over r_0}}</math> where <math>r_{ij}</math> is the euclidean separation and <math>\beta</math>, <math>r_0</math> are parameters determined by the system. This type of RGG with probabilistic connection function is often referred to a soft random geometric Graph, which now has two sources of randomness; the location of nodes (vertices) and the formation of links (edges). This connection function has been generalized further in the literature <math display="inline">H_{ij}=\beta e^{-\left({r_{ij} \over r_0}\right)^\eta}</math> which is often used to study wireless networks without interference. The parameter <math>\eta</math> represents how the signal decays with distance, when <math>\eta =2</math> is free space, <math>\eta >2</math> models a more cluttered environment like a town (= 6 models cities like New York) whilst <math>\eta <2</math> models highly reflective environments. We notice that for <math>\eta =1</math> is the Waxman model, whilst as <math>\eta \to \infin</math> and <math display="inline">\beta =1</math> we have the standard RGG. Intuitively these type of connection functions model how the probability of a link being made decays with distance.

===Overview of some results for Soft RGG===
In the high density limit for a network with exponential connection function the number of isolated nodes is Poisson distributed, and the resulting network contains a unique giant component and isolated nodes only.<ref name="Connectivity of large wireless netw">{{cite journal|last1=Mao|first1=G|last2=Anderson|first2=B.D|date=2013|title=Connectivity of large wireless networks under a general connection model|journal= IEEE Transactions on Information Theory|volume=59|issue=3|pages=1761–1772|doi=10.1109/tit.2012.2228894|s2cid=3027610}}</ref> Therefore by ensuring there are no isolated nodes, in the dense regime, the network is a.a.s fully connected; similar to the results shown in <ref>{{cite journal|last1=Penrose|first1=Mathew D|date=1997|title=The longest edge of the random minimal spanning tree|journal=The Annals of Applied Probability|pages=340361}}</ref> for the disk model. Often the properties of these networks such as betweenness centrality <ref>{{cite book |isbn=978-1-4673-6432-4 |arxiv=1410.8521|bibcode=2014arXiv1410.8521K|doi=10.1109/ICC.2015.7249352|chapter=Betweenness centrality in dense random geometric networks|title=2015 IEEE International Conference on Communications (ICC)|pages=6450–6455|year=2015|last1=Giles|first1=Alexander P.|last2=Georgiou|first2=Orestis|last3=Dettmann|first3=Carl P.|s2cid=928409}}</ref> and connectivity <ref name="Connectivity of large wireless netw"/> are studied in the limit as the density <math>\to \infin</math> which often means border effects become negligible. However, in real life where networks are finite, although can still be extremely dense, border effects will impact on full connectivity; in fact <ref>{{cite journal|last1=Coon|first1=J|last2=Dettmann|first2=C P|last3=Georgiou|first3=O|date=2012|title=Full connectivity: corners, edges and faces|journal=Journal of Statistical Physics|volume=147|issue=4|pages=758–778|arxiv=1201.3123|bibcode=2012JSP...147..758C|doi=10.1007/s10955-012-0493-y|s2cid=18794396}}</ref> showed that for full connectivity, with an exponential connection function, is greatly impacted by boundary effects as nodes near the corner/face of a domain are less likely to connect compared with those in the bulk. As a result full connectivity can be expressed as a sum of the contributions from the bulk and the geometries boundaries. A more general analysis of the connection functions in wireless networks has shown that the probability of full connectivity can be well approximated expressed by a few moments of the connection function and the regions geometry.<ref>{{cite journal|last1=Dettmann|first1=C.P|last2=Georgiou|first2=O|date=2016|title=Random geometric graphs with general connection functions|journal=Physical Review E|volume=93|issue=3|pages=032313|arxiv=1411.3617|bibcode=2016PhRvE..93c2313D|doi=10.1103/physreve.93.032313|pmid=27078372|s2cid=124506496 }}</ref>

==References==
<references /><br />

[[Category:Geometric graphs]]
[[Category:Random graphs]]