Random Geometric Graphs
A. D. Barbour, Gesine Reinert · Networks · 2004
The random geometric graphs considered in this chapter are derived from a configuration of points that are independently placed in an underlying Euclidean space, according to some distribution. Each pair of points that are separated by a distance less than some given threshold is joined by an edge, and the graph then consists only of vertices, corresponding to the points, and of the edges between them, with the positional information discarded. In this model, the edges are no longer independent, and the neighbourhood structure is quite different from the tree-like neighbourhoods in Chapters 11–14; for instance, the average local clustering coefficient is not typically close to zero, even in sparse graphs. A giant component is shown to be unlikely to exist if the density of points is low enough, and to be almost certain to exist if the density of points is high enough, with the ratio of the critical densities fixed as the number of points grows. A subgraph threshold theorem is established, complemented by a number of distributional approximations to the counts of subgraphs; the independence of the positions of the underlying points simplifies this discussion. Under suitable asymptotics, typical shortest path lengths are shown to grow like a power of the number of points, rather than logarithmically, as was the case for the models in Chapters 11–14.