Testing thresholds for high-dimensional sparse random geometric graphs

Abstract

The random geometric graph model GRGd(n,p) is a distribution over graphs in which the edges capture a latent geometry. To sample G ∼ GRGd(n,p), we identify each of our n vertices with an independently and uniformly sampled vector from the d-dimensional unit sphere Sd−1, and we connect pairs of vertices whose vectors are “sufficiently close,” such that the marginal probability of an edge is p. Because of the underlying geometry, this model is natural for applications in data science and beyond.