Random geometric graph
In graph theory, a random geometric graph is the mathematically simplest spatial network, namely an undirected graph constructed by randomly placing N nodes in some metric space 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 model do not create this type of structure. Additionally, random geometric graphs display degree assortativity according to their spatial dimension: "popular" nodes are particularly likely to be linked to other popular nodes.
Percolation theory on the random geometric graph 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 denote an undirected Graph with a set of vertices and a set of edges. The set sizes are denoted by and. Additionally, if not noted otherwise, the metric space with the euclidean distance is considered, i.e. for any points the euclidean distance of x and y is defined asA random geometric graph is an undirected geometric graph with nodes randomly sampled from the uniform distribution of the underlying space. Two vertices are connected if, and only if, their distance is less than a previously specified parameter, excluding any loops. Thus, the parameters and 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 possible connections that are checked, the time complexity of the naive algorithm is. The samples are generated by using a random number generator on. Practically, one can implement this using d random number generators on, one RNG for every dimension.Pseudocode
V := generateSamples // Generates n samples in the unit cube.for each p ∈ V do
for each q ∈ V\ do
if distance ≤ r then
addConnection // Add the edge to the edge data structure.
end if
end for
end for
As this algorithm is not scalable, 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. It partitions the unit square into equal sized cells with side length of at least. For a given number of processors, each processor is assigned cells, where For simplicity, is assumed to be a square number, but this can be generalized to any number of processors. Each processor then generates 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. An upper bound for the communication cost of this algorithm is given by, where denotes the time for an all-to-all communication with messages of length bits to communication partners. is the time taken for a point-to-point communication for a message of length bits.Since this algorithm is not communication free, Funke et al. proposed 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 is similar to the approach in Holtgrewe: Partition the unit cube into equal sized chunks with side length of at least. So in = 2 this will be squares, in = 3 this will be cubes. As there can only fit at most chunks per dimension, the number of chunks is capped at. As before, each processor is assigned 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 seeded hash functions. 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, without any cost for communication between processing units.
Properties
Isolated vertices and connectivity
In the special case that, the probability that a single vertex is isolated in a RGG is. Let be the random variable counting how many vertices are isolated. Then the expected value of is. The term provides information about the connectivity of the RGG. For, the RGG is asymptotically almost surely connected. For, the RGG is asymptotically almost surely disconnected. And for, the RGG has a giant component that covers more than vertices and is Poisson distributed with parameter. It follows that if, the probability that the RGG is connected is and the probability that the RGG is not connected is.For any -Norm and for any number of dimensions, a RGG possesses a sharp threshold of connectivity at with constant. In the special case of a two-dimensional space and the euclidean norm this yields.
Hamiltonicity
It has been shown, that in the two-dimensional case, the threshold also provides information about the existence of a Hamiltonian cycle. For any, if, then the RGG has asymptotically almost surely no Hamiltonian cycle and if for any, then the RGG has asymptotically almost surely a Hamiltonian cycle.Clustering coefficient
The clustering coefficient of RGGs only depends on the dimension of the underlying space. The clustering coefficient isfor even and for odd whereFor large, this simplifies to.