Community Recovery in Graphs with Locality

Abstract

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.

accepted in part to International Conference on Machine Learning (ICML), 2016

References in corpus (8)

• Robust PCA via Outlier Pursuit
• Phase Transitions in Semidefinite Relaxations
• Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms
• Achieving Optimal Misclassification Proportion in Stochastic Block Model
• Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
• Information-theoretic bounds for exact recovery in weighted stochastic block models using the Renyi divergence
• Density Evolution in the Degree-correlated Stochastic Block Model

Cited by in corpus (6)

• Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
• Clustering with Noisy Queries
• MC2G: An Efficient Algorithm for Matrix Completion with Social and Item Similarity Graphs
• Matrix Completion with Hierarchical Graph Side Information
• Subspace Estimation from Unbalanced and Incomplete Data Matrices: ${\ell }_{2,\infty }$ Statistical Guarantees
• Detecting communities is hard, and counting them is even harder