Community Recovery in Graphs with Locality
  Motivated by applications in domains such as social networks and
computational biology, we study the problem of community recovery in graphs
with locality. In this problem, pairwise noisy measurements of whether two
nodes are in the same community or different communities come mainly or
exclusively from nearby nodes rather than uniformly sampled between all nodes
pairs, as in most existing models. We present an algorithm that runs nearly
linearly in the number of measurements and which achieves the information
theoretic limit for exact recovery.
