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: "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 after the work of Edgar Gilbert, who introduced these graphs and percolation in them in a 1961 paper. A real-world application of RGGs is the modeling of ad hoc networks. Furthermore, they are used to perform benchmarks for graph algorithms.
Definition
In the following, let G = (V, E) denote an undirected Graph with a set of vertices V and a set of edges E ⊆ V × V. The set sizes are denoted by |V| = n and |E| = m. Additionally, if not noted otherwise, the metric space [0,1)d with the euclidean distance is considered, i.e. for any points x , y ∈ [ 0 , 1 ) d {\displaystyle x,y\in [0,1)^{d}} the euclidean distance of x and y is defined as
d ( x , y ) = | | x − y | | 2 = ∑ i = 1 d ( x i − y i ) 2 {\displaystyle d(x,y)=||x-y||_{2}={\sqrt {\sum _{i=1}^{d}(x_{i}-y_{i})^{2}}}} . A random geometric graph (RGG) is an undirected geometric graph with nodes randomly sampled from the uniform distribution of the underlying space [0,1)d. Two vertices p, q ∈ V are connected if, and only if, their distance is less than a previously specified parameter r ∈ (0,1), excluding any loops. Thus, the parameters r and 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 n ( n − 1 ) 2 {\textstyle {\frac {n(n-1)}{2}}} possible connections that are checked, the time complexity of the naive algorithm is Θ ( n 2 ) {\textstyle \Theta (n^{2})} . The samples are generated by using a random number generator (RNG) on [ 0 , 1 ) d {\displaystyle [0,1)^{d}} . Practically, one can implement this using d random number generators on [ 0 , 1 ) {\displaystyle [0,1)} , 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 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
… excerpt ends here. Continue reading the full article.
