Random geometric graph

A random geometric graph is an undirected geometric graph with nodes evenly distributed on the underlying space . Two nodes are connected if and only if their distance is less than a previously specified parameter . ${\displaystyle [0,1)^{d}}$ ${\displaystyle r\in (0,1)}$

Random geometric graphs are similar to human social networks in many ways. They often show community structures; H. densely linked groups of nodes are formed. Other generators for random graphs, such as the Erdős – Rényi model or Barabási – Albert (BA) model , do not generate such structures. In addition, nodes with a high node degree are particularly likely to be connected to other nodes with a high node degree.

One application of the random geometric graphs is the modeling of ad hoc networks . They can also be used to benchmark (external) graph algorithms.

definition

Generation of a random geometric graph with n = 500 nodes for different parameters r.

In the following denotes an undirected graph with a set of nodes and a set of edges . Let the number of nodes be the number of edges . In addition, all mathematical considerations are in metric space , unless otherwise specified. The associated metric is the Euclidean distance , so for any node the Euclidean distance is defined as . ${\displaystyle G=(V,E)}$ ${\displaystyle V}$ ${\displaystyle E\subseteq V\times V}$ ${\displaystyle |V|=n}$ ${\displaystyle |E|=m}$ ${\displaystyle [0,1)^{d}}$ ${\displaystyle x,y\in [0,1)^{d}}$ ${\textstyle d(x,y)=\|x-y\|_{2}={\sqrt {\sum _{i=1}^{d}(x_{i}-y_{i})^{2}}}}$

For and a random geometric graph is generated by nodes equally distributed to be drawn. All nodes whose Euclidean distance is less than are connected by an edge. No loops are considered here, as otherwise every node would have a loop. This characterizes the parameters and a random geometric graph. ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle r\in (0,1)}$ ${\displaystyle {\mathcal {G}}(n,r)}$ ${\displaystyle n}$ ${\displaystyle [0,1)^{d}}$ ${\displaystyle r\in (0,1)}$ ${\displaystyle n}$ ${\displaystyle r}$

Algorithms

Naive algorithm

The naive approach is to calculate the distance to every other node for each node. Since there are possible connections, the time complexity is . The nodes are using a random number generator to generate. In practice, this can be done with random number generators , one for each dimension. ${\displaystyle {\frac {n(n-1)}{2}}}$ ${\displaystyle \Theta (n^{2})}$ ${\displaystyle [0,1)^{d}}$ ${\displaystyle d}$ ${\displaystyle [0,1)}$

An algorithm in pseudo-code for this is:

V = generiereKnoten(n) // Generiere n Knoten im Einheitswürfel.
besuchteKnoten = {}
for each p ∈ V
    besuchteKnoten.add(p)
	for each q ∈ V\besuchteKnoten   // Da es ein ungerichteter Graph ist, müssen
	                                // bereits besuchte Knoten nicht betrachtet werden.
		if distanz(p, q) <= r
			ergänzeKante(p, q) // Füge die Kante (p, q) zur Kantendatenstruktur hinzu.
		end
	end
end

Since this algorithm is not scalable (every node needs the position of every other node), Holtgrewe et al. and Funke et al. proposed new algorithms for this problem.

Distributed algorithms

Holtgrewe et al.

This algorithm, which was developed by Holtgrewe et al. was proposed, was the first distributed generator for random geometric graphs for dimension 2. The unit square is partitioned into squares of equal size (cells) with a side length of at least . For a given number of processors, cells are allocated to each processor . Here is the number of cells of the size in a dimension. For the sake of simplicity, a square number is assumed, but the algorithm can be adapted for any number of processors. Each processor generates nodes in the unit square, so overall the required nodes are generated. If nodes are generated that belong in a cell of another processor, these are then distributed to the correct processors. After this step, the nodes are sorted according to the cell number in which they fall, for example with Quicksort . Then each processor sends each neighboring processor the position of the nodes in the edge cells, with which all edges can then be generated. The processors no longer need information to generate the edges, since the cells are at least as long as the side . ${\displaystyle r}$ ${\displaystyle P=p^{2}}$ ${\textstyle {k \over p}\times {k \over p}}$ ${\displaystyle k=\left\lfloor {1/r}\right\rfloor }$ ${\displaystyle r}$ ${\displaystyle P}$ ${\textstyle {\frac {n}{P}}}$ ${\displaystyle n}$ ${\displaystyle r}$

The expected run time is . An upper limit to the communication costs is given by . This is the time required for all-to-all communication with messages of length 1 bit to communication partners. is the time for a point-to-point communication for a message of length 1 bit. ${\textstyle O({\frac {n}{P}}\log {\frac {n}{P}})}$ ${\displaystyle T_{all-to-all}(n/P,P)+T_{all-to-all}(1,P)+T_{point-to-point}(n/(k\cdot {P})+2)}$ ${\displaystyle T_{all-to-all}(l,c)}$ ${\displaystyle c}$ ${\displaystyle T_{point-to-point}(l)}$

Since this algorithm is not communication-free, Funke et al. proposed a scalable, distributed generator that also works in higher dimensions without communication between the processors.

Funke et al.

The procedure in this algorithm is similar to that of Holtgrewe: The unit cube is divided into chunks of equal size, the length of the side or larger. In dimension 2 there are squares, in dimension 3 cubes. Since a maximum of chunks fit into each dimension, the number of chunks is limited by . Each of the processors are assigned chunks for which it generates points. For a communication-free process, each processor also generates the same nodes in the neighboring chunks. This is made possible by hash functions with special seeds . In this way, each processor calculates the same nodes and there is no need to communicate node positions. ${\displaystyle r}$ ${\displaystyle {\left\lfloor {1/r}\right\rfloor }}$ ${\textstyle {\left\lfloor {1/r}\right\rfloor }^{d}}$ ${\displaystyle P}$ ${\textstyle {\left\lfloor {1/r}\right\rfloor }^{d} \over P}$

For dimension 3, Funke et al. proved that the expected run time is without additional communication costs. ${\textstyle O({\frac {m+n}{P}}+\log {P})}$

properties

Isolated nodes and connectivity

The probability that a single node is isolated in a random geometric graph is . Let be the random variable that counts how many nodes are isolated, then is the expectation . The term contains information about the connectivity of the random geometric graph. For the graph is almost certainly connected asymptotically . For the graph is almost certainly not connected asymptotically. And for the graph has a huge component with more than nodes and is Poisson distributed with parameters . It follows that if is the probability that the graph is connected and the probability that it is not connected is . For every - norm ( ) and for every number of dimensions the graph has a sharp limit for the connectivity with a constant . In the special case of two-dimensional space and the Euclidean norm ( and ) is . ${\textstyle (1-\pi r^{2})^{n-1}}$ ${\textstyle X}$ ${\textstyle E(X)=n(1-\pi r^{2})^{n-1}=ne^{-\pi r^{2}n}-O(r^{4}n)}$ ${\textstyle \mu =ne^{-\pi r^{2}n}}$ ${\textstyle \mu \longrightarrow 0}$ ${\displaystyle \mu \longrightarrow \infty }$ ${\textstyle \mu =\Theta (1)}$ ${\textstyle n \over 2}$ ${\displaystyle X}$ ${\displaystyle \mu }$ ${\textstyle \mu =\Theta (1)}$ ${\textstyle P[X=0]\sim e^{-\mu }}$ ${\textstyle P[X>0]\sim 1-e^{-\mu }}$ ${\textstyle l_{p}}$ ${\textstyle 1\leq p\leq \infty }$ ${\displaystyle d>2}$ ${\textstyle r\sim ({\ln(n) \over \alpha _{p,d}n})^{1 \over d}}$ ${\displaystyle \alpha _{p,d}}$ ${\displaystyle d=2}$ ${\displaystyle p=2}$ ${\textstyle r\sim {\sqrt {\ln(n) \over \pi n}}}$

Hamiltonicity

It was shown that in the two-dimensional case the threshold value also provides information about the existence of a Hamiltonian circle . For each , the graph asymptotically almost certainly has a Hamiltonian cycle if and the graph asymptotically almost certainly has no Hamiltonian cycle if . ${\textstyle r\sim {\sqrt {\ln(n) \over \pi n}}}$ ${\displaystyle \epsilon >0}$ ${\textstyle r\sim {\sqrt {\ln(n) \over (\pi +\epsilon )n}}}$ ${\textstyle r\sim {\sqrt {\ln(n) \over (\pi -\epsilon )n}}}$

Cluster coefficient

The cluster coefficient of the random geometric graph depends exclusively on the dimension of the underlying space . The cluster coefficient is for even and for odd . Here is . ${\displaystyle d}$ ${\textstyle [0,1)^{d}}$ ${\textstyle C_{d}=1-H_{d}(1)}$ ${\displaystyle d}$ ${\textstyle C_{d}={3 \over 2}-H_{d}({1 \over 2})}$ ${\displaystyle d}$ ${\displaystyle H_{d}(x)={1 \over {\sqrt {\pi }}}\sum _{i=x}^{d \over 2}{\Gamma (i) \over \Gamma (i+{1 \over 2})}({3 \over 4})^{i+{1 \over 2}}}$

For large ones, the cluster coefficient simplifies to . ${\displaystyle d}$ ${\displaystyle C_{d}\sim 3{\sqrt {2 \over \pi d}}({3 \over 4})^{d+1 \over 2}}$

Generalized random geometric graphs

In 1988 Waxman generalized the random geometric graph by replacing the deterministic connection function given by a probabilistic connection function. The variant presented by Waxman was a stretched exponential function , in which two nodes and are connected with probability , where the Euclidean separation is and as well as parameters given by the system. Such a random geometric graph is also called a "soft" random geometric graph, which has two sources of chance: the location of the nodes and the formation of the edges. The connectivity function has been further generalized by , which is often used to examine wireless networks without interference. The parameter indicates how the signal drops over the distance. It corresponds to a free space and corresponds to more filled surroundings like a city ( is used as a modeling for New York). In turn, corresponds to highly reflective environments. For exactly the model of Waxman results and for and the original model of the random geometric graph results. The extended connection functions thus model how the probability of a connection between two nodes decreases with their distance. ${\displaystyle r}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle H_{ij}=\beta e^{-{r_{ij} \over r_{0}}}}$ ${\displaystyle _{ij}}$ ${\displaystyle \beta }$ ${\displaystyle r_{0}}$ ${\textstyle H_{ij}=\beta e^{-({r_{ij} \over r_{0}})^{\eta }}}$ ${\displaystyle \eta }$ ${\displaystyle \eta =2}$ ${\displaystyle \eta >2}$ ${\displaystyle \eta =6}$ ${\displaystyle \eta <2}$ ${\displaystyle \eta =1}$ ${\displaystyle \eta \to \infty }$ ${\textstyle \beta =1}$

Soft random geometric graphs

When using the exponential function presented as a connection function in a high-density network, the number of isolated nodes is Poisson distributed and the resulting network contains a single huge component and otherwise only isolated nodes. Ensuring that no node is isolated, the graph is asymptotically almost surely connected, similar to that shown in FIG. Properties such as centrality and connectivity are mostly examined for the case that the density converges asymptotically to infinity. As a result, marginal cases are often negligible. In the real world, however, the networks are finite, even if they can become very dense and marginal cases have an impact on connectivity. Indeed, it has been shown that connectivity, with an exponential connection function, is strongly influenced by edge effects, since nodes near the boundary of the domain are less likely to be connected to nodes in the ground. Hence, full connectivity can be expressed by a sum of contributions from the mass and from the geometric boundaries. A more general analysis of the connection functions in wireless networks has shown that the likelihood of full connectivity can be approximated by the moments of the connection function and the geometry of the domain.

Individual evidence

1. ^ Mathew Penrose: Random geometric graphs . Oxford University Press, Oxford 2003, ISBN 0-19-850626-0 .
2. ↑ Maziar Nekovee: Worm Epidemics in Wireless Ad Hoc Networks . July 16, 2007, doi : 10.1088 / 1367-2630 / 9/6/189 , arxiv : 0707.2293v1 .
3. ↑ ^{a b c} Moritz von Looz, Darren Strash, Christian Schulz, Manuel Penschuck, Peter Sanders, Ulrich Meyer, Sebastian Lamm, Daniel Funke: Communication-free Massively Distributed Graph Generation . In: arXiv . 20th October 2017.
4. ^ Xavier Perez, Dieter Mitsche, Josep Diaz: Dynamic Random Geometric Graphs . In: Dynamic Random Geometric Graphs . February 13, 2007.
5. ^ X. Perez, D. Mitsche, J. Diaz: Sharp threshold for hamiltonicity of random geometric graphs . In: Sharp threshold for hamiltonicity of random geometric graphs . July 7, 2006.
6. ↑ Michael Christensen, Jesper Dall: Random Geometric Graphs . In: Random Geometric Graphs . March 1, 2002. doi : 10.1103 / PhysRevE.66.016121 .
7. ^ BM Waxman: Routing of multipoint connections . In: IEEE Journal on Selected Areas in Communications . 6, No. 9, 1988, pp. 1617-1622. doi : 10.1109 / 49.12889 .
8. ^ G Mao, BD Anderson: Connectivity of large wireless networks under a general connection model . In: IEEE Transactions on Information . 59, No. 3, 2013, pp. 1761–1772. doi : 10.1109 / tit.2012.2228894 .
9. ^ Mathew D Penrose: The longest edge of the random minimal spanning tree . In: The Annals of Applied Probability . 1997, p. 340361.
10. ^ AP Giles, O Georgiou, CP Dettmann: Betweenness centrality in dense random geometric networks . In: IEEE International Conference on Communications . 2015, pp. 6450-6455. arxiv : 1410.8521 . bibcode : 2014arXiv1410.8521K . doi : 10.1109 / ICC.2015.7249352 .
11. ^ G Mao, BD Anderson: Connectivity of large wireless networks under a general connection model . In: IEEE Transactions on Information . 59, No. 3, 2013, pp. 1761–1772. doi : 10.1109 / tit.2012.2228894 .
12. ^ J Coon, CP Dettmann, O Georgiou: Full connectivity: corners, edges and faces . In: Journal of Statistical Physics . 147, No. 4, 2012, pp. 758-778. arxiv : 1201.3123 . bibcode : 2012JSP ... 147..758C . doi : 10.1007 / s10955-012-0493-y .
13. ↑ CP Dettmann, O Georgiou: Random geometric graphs with general connection functions . In: Physical Review E . 93, No. 3, 2016, p. 032313. arxiv : 1411.3617 . bibcode : 2016PhRvE..93c2313D . doi : 10.1103 / physreve.93.032313 . PMID 27078372 .