mlsanityData to 7 Oct 2026

Achieving Optimal Misclassification Proportion in Stochastic Block Model

arXiv 1505.03772 ↗First posted 14 May 2015math.ST cs.SI stat.MEcited by 35

Not on the map. Why?

Abstract (arXiv)

Community detection is a fundamental statistical problem in network data analysis. Many algorithms have been proposed to tackle this problem. Most of these algorithms are not guaranteed to achieve the statistical optimality of the problem, while procedures that achieve information theoretic limits for general parameter spaces are not computationally tractable. In this paper, we present a computationally feasible two-stage method that achieves optimal statistical performance in misclassification proportion for stochastic block model under weak regularity conditions. Our two-stage procedure consists of a generic refinement step that can take a wide range of weakly consistent community detection procedures as initializer, to which the refinement stage applies and outputs a community assignment achieving optimal misclassification proportion with high probability. The practical effectiveness of the new algorithm is demonstrated by competitive numerical results.

Key facts. Cited by 35 papers in the map (data through 7 Oct 2026). First posted on arXiv 14 May 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 11; 2022: 10; 2023: 7; 2024: 2; 2025: 4; 2026: 1.

35 papers.

Sort:

  1. 2021One-Hot Graph Encoder Embeddingcited by 16
  2. 2022Differentially Private Community Detection for Stochastic Block Modelscited by 15
  3. 2021Exact Recovery in the General Hypergraph Stochastic Block Modelcited by 13
  4. 2021Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitionscited by 10
  5. 2021Community detection for weighted bipartite networkscited by 8
  6. 2021Localization in 1D non-parametric latent space models from pairwise affinitiescited by 7
  7. 2023Computational Lower Bounds for Graphon Estimation via Low-degree Polynomialscited by 6
  8. 2022Matrix Completion with Hierarchical Graph Side Informationcited by 5
  9. 2021Network Estimation by Mixing: Adaptivity and Morecited by 4
  10. 2022A Compressed Sensing Based Least Squares Approach to Semi-supervised Local Cluster Extractioncited by 4
  11. 2022The Multivariate Community Hawkes Model for Dependent Relational Events in Continuous-time Networkscited by 4
  12. 2022Sparse Subspace Clustering in Diverse Multiplex Network Modelcited by 4
23 more
  1. 2021Informative core identification in complex networkscited by 3
  2. 2021A useful criterion on studying consistent estimation in community detectioncited by 3
  3. 2021A Spectral Method for Joint Community Detection and Orthogonal Group Synchronizationcited by 3
  4. 2022Exact Community Recovery over Signed Graphscited by 3
  5. 2022Consensus Knowledge Graph Learning via Multi-view Sparse Low Rank Block Modelcited by 3
  6. 2021Mixed membership distribution-free modelcited by 2
  7. 2021Non-Convex Joint Community Detection and Group Synchronization via Generalized Power Methodcited by 2
  8. 2023Graphon Estimation in bipartite graphs with observable edge labels and unobservable node labelscited by 2
  9. 2023Consistency of Lloyd's Algorithm Under Perturbationscited by 2
  10. 2022Detection and Evaluation of Clusters within Sequential Datacited by 1
  11. 2023rMultiNet: An R Package For Multilayer Networks Analysiscited by 1
  12. 2023Information-Theoretic Limits and Strong Consistency on Binary Non-uniform Hypergraph Stochastic Block Modelscited by 1
  13. 2024Community Detection in the Multi-View Stochastic Block Modelcited by 1
  14. 2024Efficient Graph Encoder Embedding for Large Sparse Graphs in Pythoncited by 1
  15. 2025Near-Optimal Clustering in Mixture of Markov Chainscited by 1
  16. 2025Strongly Consistent Community Detection in Popularity Adjusted Block Modelscited by 1
  17. 2022On consistency of constrained spectral clustering under representation-aware stochastic block modelcited by 0
  18. 2022Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Thresholdcited by 0
  19. 2023Variational Inference: Posterior Threshold Improves Network Clustering Accuracy in Sparse Regimescited by 0
  20. 2023Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Modelcited by 0
  21. 2025Spectral clustering for dependent community Hawkes process models of temporal networkscited by 0
  22. 2025Model-free algorithms for fast node clustering in SBM type graphs and application to social role inference in animalscited by 0
  23. 2026Fundamental Limits of Community Detection in Contextual Multi-Layer Stochastic Block Modelscited by 0