Testing thresholds for high-dimensional sparse random geometric graphs

The random geometric graph model GRG d ( n , p ) is a distribution over graphs in which the edges capture a latent geometry. To sample G ∼ GRG d ( n , p ), we identify each of our n vertices with an independently and uniformly sampled vector from the d -dimensional unit sphere S d −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.

Authors

• Siqi Liu 0005
• Sidhanth Mohanty
• Tselil Schramm
• Elizabeth Yang

Keywords

• optimal transport
• cavity method
• random graphs
• random geometric graphs
• belief propagation