  We consider the community recovery problem on a one-dimensional random
geometric graph where every node has two independent labels: an observed
location label and a hidden community label. A geometric kernel maps the
locations of pairs of nodes to probabilities. Edges are drawn between pairs of
nodes based on their communities and the value of the kernel corresponding to
the respective node locations. Given the graph so generated along with the
location labels, the latent communities of the nodes are to be inferred. In
this work, we will look into the fundamental statistical limits for recovering
the communities in such models. Additionally, we propose a linear-time
algorithm (in the number of edges) and show that it recovers the communities of
nodes exactly up to the information theoretic threshold.
