Community Recovery in Graphs with Locality
This addresses community detection in networks with locality constraints, such as social networks and computational biology, but is incremental as it adapts existing models to localized measurements.
The paper tackles the problem of community recovery in graphs where noisy measurements of node community membership are primarily from nearby nodes, rather than uniformly sampled across all pairs. It presents an algorithm that runs nearly linearly in the number of measurements and achieves the information-theoretic limit for exact recovery.
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.