Random geometric graphs. (English) Zbl 1029.60007

Oxford Studies in Probability. 5. Oxford: Oxford University Press. xiii, 330 p. (2003).
A set of points scattered over a region generates a graph by connecting pairs of points separated by a distance less than a certain specified value. Properties of such graphs generated by a random set of points constitute a substantial part of the theory of geometric probability. This provides a remarkable source for various facts on random geometric graphs. The author unifies numerous facts previously scattered in journal papers and presents a number of new results. The concepts presented in the book have numerous applications in statistics (clustering and classification, scan statistics) and computer science (travelling salesman and other arrangement problems).
For a set \(\mathcal{X}_n\) of \(n\) random points denote by \(G(\mathcal{X}_n;r)\) the indirected graph with vertex set \(\mathcal{X}_n\) and with undirected edges connecting all \(r\)-close pairs of points. A number of numerical characteristics of graphs can be formulated in terms of the threshold distance being the smallest \(r\) such that the graph possesses the specified property. For example, the smallest \(r\) for which the graph has at least one edge equals the smallest inter-point distance in \(\mathcal{X}_n\). Although exact formulae for characteristics of \(G(\mathcal{X}_n;r)\) are usually not available, nice mathematical results can be obtained in the asymptotic framework when \(r=r_n\to 0\) and \(n\to\infty\).
In many cases the problem can be transformed into considering the random graph built on a finite Poisson process of growing total intensity. Other techniques include Stein-Chen method of Poisson approximation, the normal approximation, and martingales. In many cases the author presents the full spectrum of limit theorems: strong laws of large numbers, convergence in distribution and large deviation results.
Part I of the book concerns subgraphs and component counts, i.e. the numbers of copies of some arbitrary specified connected finite graph embedded in the graph \(G(\mathcal{X}_n;r)\). Then the author considers the empirical distribution of the vertex degrees, e.g. properties of the threshold value of \(r\) for which the graph has all vertices of degree at least \(k\). Part II deals with extremes of locally determined quantities, including the maximum degree, the minimum degree, the clique number and the chromatic number.
Part III concerns giant components and connectivity properties. If \(r_n\sim c n^{-1/d}\), then, with the constant \(c\) above a certain critical value, a positive fraction of the points likely constitutes a giant connected component of the graph \(G(\mathcal{X}_n;r_n)\). This phenomenon is known as percolation. In addition to laws of large numbers, central limit theorems and large deviations for the order of the largest component, this part contains a significant amount of material on continuum percolation. Applications include consistency results for testing unimodality in statistics and layout problems in computer science. A further important topic in Part III deals with the connectivity of random geometric graphs, and with the number of components, in particular when \(r_n\sim c((\log n)/n)^{-1/d}\). Results include limit laws for the threshold at which the graph becomes connected, and also on multiple connectivity.
The book is suitable to design a graduate course in random geometric graphs. Its scope stretches far beyond geometric probability and includes exciting material from Poisson approximation, percolation and statistical physics. This elegantly written monograph belongs to the collection of important books vital for every probabilist.


60D05 Geometric probability and stochastic geometry
05C80 Random graphs (graph-theoretic aspects)
60C05 Combinatorial probability
60K35 Interacting random processes; statistical mechanics type models; percolation theory
60-02 Research exposition (monographs, survey articles) pertaining to probability theory
Full Text: DOI Link