Random geometric graph

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.

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.

the euclidean distance of x and y is defined as 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.[5] 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.

possible connections that are checked, the time complexity of the naive algorithm is

Practically, one can implement this using d random number generators on

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.

[6] It partitions the unit square into equal sized cells with side length of at least

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.

An upper bound for the communication cost of this algorithm is given by

is the time taken for a point-to-point communication for a message of length l bits.

Since this algorithm is not communication free, Funke et al. proposed[6] a scalable distributed RGG generator for higher dimensions, which works without any communication between the processing units.

The approach used in this algorithm[6] is similar to the approach in Holtgrewe: Partition the unit cube into equal sized chunks with side length of at least r. So in d = 2 this will be squares, in d = 3 this will be cubes.

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.

The probability that a single vertex is isolated in a RGG is

In the special case of a two-dimensional space and the euclidean norm (

In 1988 Waxman[10] generalised the standard RGG by introducing a probabilistic connection function as opposed to the deterministic one suggested by Gilbert.

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).

Intuitively these type of connection functions model how the probability of a link being made decays with distance.

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.

[11] 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 [12] for the disk model.

Often the properties of these networks such as betweenness centrality [13] and connectivity [11] are studied in the limit as the density

However, in real life where networks are finite, although can still be extremely dense, border effects will impact on full connectivity; in fact [14] 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.