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. 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. A real-world application of RGGs is the modeling of ad hoc networks. Furthermore they are used to perform benchmarks for (external) 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 formula_1 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 . 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 formula_3possible connections that are checked, the time  complexity of the naive algorithm is formula_4. The samples are generated by using a random number generator (RNG) on formula_5. Practically, one can implement this using d random number generators on formula_6, one RNG for every dimension. Pseudocode. "V" := generateSamples("n") "// Generates n samples in the unit cube." 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. 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 formula_7. For a given number formula_8of processors, each processor is assigned formula_9cells, where formula_10For simplicity, formula_11 is assumed to be a square number, but this can be generalized to any number of processors. Each processor then generates formula_12vertices, 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 formula_13. An upper bound for the communication cost of this algorithm is given by formula_14, where formula_15denotes the time for an all-to-all communication with messages of length bits to communication partners. formula_16is 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 formula_17 chunks per dimension, the number of chunks is capped at formula_18. As before, each processor is assigned formula_19chunks, 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 formula_20, 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 formula_21. Let formula_22 be the random variable counting how many vertices are isolated. Then the expected value of formula_22is formula_24. The term formula_25provides information about the connectivity of the RGG. For formula_26, the RGG is asymptotically almost surely connected. For formula_27, the RGG is asymptotically almost surely disconnected. And for  formula_28, the RGG has a giant component of that covers more than formula_29vertices and formula_30 is Poisson distributed with parameter formula_31. It follows that if formula_28, the probability that the RGG is connected is formula_33and the probability that the RGG is not connected is formula_34. For any formula_35-Norm ( formula_36) and for any number of dimensions formula_37, a RGG possesses a sharp threshold of connectivity at formula_38with constant formula_39. In the special case of a two-dimensional space and the euclidean norm (formula_40 and formula_41) this yields formula_42. Hamiltonicity. It has been shown, that in the two-dimensional case, the  threshold formula_42also provides information about the existence of a Hamiltonian cycle (Hamiltonian Path). For any formula_44, if formula_42, then the RGG has asymptotically almost surely no Hamiltonian cycle and if formula_42for any formula_47, 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 is formula_48for even formula_49 and formula_50for odd formula_49whereformula_52For large formula_49, this simplifies to formula_54. Generalized random geometric Graphs. In 1988 Waxman 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 formula_55 and formula_56 connect with probability given by formula_57where formula_58 is the euclidean separation and formula_59, formula_60are 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 formula_61which is often used to study wireless networks without interference. The parameter formula_62 represents how the signal decays with  distance, when formula_63 is free space, formula_64 models a more cluttered environment like a town (= 6 models cities like New York) whilst formula_65 models highly reflective environments. We notice that for formula_66 is the Waxman model, whilst as formula_67 and formula_68 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. 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 for the disk model. Often the properties of these networks such as betweenness centrality and connectivity are studied in the limit as the density formula_69 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 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.