Connectivity of soft random geometric graphs

Mathew D. Penrose

Published 2013-11-15, updated 2015-03-23Version 2

Consider a graph on $n$ uniform random points in the unit square, each pair being connected by an edge with probability $p$ if the inter-point distance is at most $r$. We show that as $n \to \infty$ the probability of full connectivity is governed by that of having no isolated vertices, itself governed by a Poisson approximation for the number of isolated vertices, uniformly over all choices of $p,r$. We determine the asymptotic probability of connectivity for all $(p_n,r_n)$ subject to $r_n = O(n^{-\epsilon}),$ some $\epsilon >0$. We generalize the first result to higher dimensions, and to a larger class of connection probability functions in $d=2$.