Almost optimal sparsification of random geometric graphs
Nicolas Broutin, Luc Devroye, Gábor Lugosi · The Annals of Applied Probability · 2016
A random geometric irrigation graph $\Gamma_{n}(r_{n},\xi)$ has $n$ vertices identified by $n$ independent uniformly distributed points $X_{1},\ldots,X_{n}$ in the unit square $[0,1]^{2}$. Each point $X_{i}$ selects $\xi_{i}$ neighbors at random, without replacement, among those points $X_{j}$ ($j eq i$) for which $\Vert X_{i}-X_{j}\Vert 1$, then the number of vertices of the largest connected component is, with high probability, $n-o(n)$. This offers a natural noncentralized sparsification of a random geometric graph that is mostly connected.