from Part III - Network Models
Published online by Cambridge University Press: 11 June 2026
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.
To save this book to your Kindle, first ensure no-reply@cambridge.org is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.
Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.
Find out more about the Kindle Personal Document Service.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.