Random Geometric Graphs

Abstract

This book sets out a body of rigorous mathematical theory for finite graphs with nodes placed randomly in Euclidean d-space according to a common probability density, and edges added to connect points that are close to each other. As an alternative to classical random graph models, these geometric graphs are relevant to the modelling of real networks having spatial content, arising for example in wireless communications, parallel processing, classification, epidemiology, astronomy, and the internet. Their study illustrates numerous techniques of modern stochastic geometry, including Stein's method, martingale methods, and continuum percolation. Typical results in the book concern properties of a graph G on n random points with edges included for interpoint distances up to r, with the parameter r dependent on n and typically small for large n. Asymptotic distributional properties are derived for numerous graph quantities. These include the number of copies of a given finite graph embedded in G, the number of isolated components isomorphic to a given graph, the empirical distributions of vertex degrees, the clique number, the chromatic number, the maximum and minimum degree, the size of the largest component, the total number of components, and the connectivity of the graph.