Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery

Abstract

In this paper, we present and analyze a simple and robust spectral algorithm for the stochastic block model with $k$ blocks, for any $k$ fixed. Our algorithm works with graphs having constant edge density, under an optimal condition on the gap between the density inside a block and the density between the blocks. As a co-product, we settle an open question posed by Abbe et. al. concerning censor block models.

References in corpus (1)

• Community detection thresholds and the weak Ramanujan property

Cited by in corpus (15)

• Rate-optimal graphon estimation
• Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms
• Achieving Optimal Misclassification Proportion in Stochastic Block Model
• Clustering with Noisy Queries
• Asymptotic Mutual Information for the Two-Groups Stochastic Block Model
• Spectral Thresholds in the Bipartite Stochastic Block Model
• Clustering Via Crowdsourcing
• The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences
• Community Recovery in Graphs with Locality
• Network cross-validation by edge sampling
• Reducing Crowdsourcing to Graphon Estimation, Statistically
• An Information-Percolation Bound for Spin Synchronization on General Graphs
• Recovering Structured Probability Matrices
• Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer Prediction
• Edge sampling using network local information