Community detection on euclidean random graphs

Motivated by problems in Community Detection, we introduce a new class of sparse spatial random graphs. These graphs can be seen as `planted-partition' versions of the classical random connection graphs studied in Stochastic Geometry. Roughly speaking, we consider an infinite random graph with the vertex set identified by the natural numbers N. Each node has two labels, a R
^d
valued location label and a {-1, +1} valued community label. We model the location labels to form the support of a homogeneous Poisson Point Process (PPP) of intensity λ on R
^d
and the community labels are i.i.d. and uniformly distributed in {-1, +1}. Conditional on the node labels, edges are drawn independently at random so that on average, a node has more edges to other nodes of the same community than the opposite community. The central question on this model is that of community detection which asks how well can one partition the nodes into representative communities, given a single realization of the location labels and the edges drawn by assuming a partition. We establish a phase-transition for this problem in the sparse graph regime. We show that if the intensity λ is sufficiently small, then there exists no algorithm that beats a random guess for the partition. Conversely, we give an algorithm that efficiently performs community detection, when the intensity λ is sufficiently high. The key techniques employed in this paper are closely related to those used to study continuum percolation.