# Community Detection in Degree-Corrected Block Models

arXiv: https://arxiv.org/abs/1607.06993 · HTML: https://mlsanity.com/paper/1607.06993/

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jul 2016.

## Built on by (most cited first, 30 of 36)

- [An iterative clustering algorithm for the Contextual Stochastic Block Model with optimality guarantees](https://mlsanity.com/paper/2112.10467/) (2021)
- [Community detection for weighted bipartite networks](https://mlsanity.com/paper/2109.10319/) (2021)
- [Graph Encoder Ensemble for Simultaneous Vertex Embedding and Community Detection](https://mlsanity.com/paper/2301.11290/) (2023)
- [Spectral clustering under degree heterogeneity: a case for the random walk Laplacian](https://mlsanity.com/paper/2105.00987/) (2021)
- [The Multivariate Community Hawkes Model for Dependent Relational Events in Continuous-time Networks](https://mlsanity.com/paper/2205.00639/) (2022)
- [Optimal Clustering by Lloyd Algorithm for Low-Rank Mixture Model](https://mlsanity.com/paper/2207.04600/) (2022)
- [Efficiently matching random inhomogeneous graphs via degree profiles](https://mlsanity.com/paper/2310.10441/) (2023)
- [Nonparametric Modeling of Higher-Order Interactions via Hypergraphons](https://mlsanity.com/paper/2105.08678/) (2021)
- [Multiway Spherical Clustering via Degree-Corrected Tensor Block Models](https://mlsanity.com/paper/2201.07401/) (2022)
- [Adversarially robust clustering with optimality guarantees](https://mlsanity.com/paper/2306.09977/) (2023)
- [Universal Lower Bounds and Optimal Rates: Achieving Minimax Clustering Error in Sub-Exponential Mixture Models](https://mlsanity.com/paper/2402.15432/) (2024)
- [Exact Recovery of Community Structures Using DeepWalk and Node2vec](https://mlsanity.com/paper/2101.07354/) (2021)
- [Semi-supervised Community Detection via Structural Similarity Metrics](https://mlsanity.com/paper/2306.01089/) (2023)
- [Community detection in censored hypergraph](https://mlsanity.com/paper/2111.03179/) (2021)
- [Higher-order accurate two-sample network inference and network hashing](https://mlsanity.com/paper/2208.07573/) (2022)
- [rMultiNet: An R Package For Multilayer Networks Analysis](https://mlsanity.com/paper/2302.04437/) (2023)
- [Of Spiky SVDs and Music Recommendation](https://mlsanity.com/paper/2307.01212/) (2023)
- [Signed Diverse Multiplex Networks: Clustering and Inference](https://mlsanity.com/paper/2402.10242/) (2024)
- [Optimal community detection in dense bipartite graphs](https://mlsanity.com/paper/2505.18372/) (2025)
- [Strongly Consistent Community Detection in Popularity Adjusted Block Models](https://mlsanity.com/paper/2506.07224/) (2025)
- [Matrix Factorization Framework for Community Detection under the Degree-Corrected Block Model](https://mlsanity.com/paper/2601.06262/) (2026)
- [Block Dense Weighted Networks with Augmented Degree Correction](https://mlsanity.com/paper/2105.12290/) (2021)
- [Global Minima, Recoverability Thresholds, and Higher-Order Structure in GNNS](https://mlsanity.com/paper/2310.07667/) (2023)
- [Community Detection Guarantees Using Embeddings Learned by Node2Vec](https://mlsanity.com/paper/2310.17712/) (2023)
- [VEC-SBM: Optimal Community Detection with Vectorial Edges Covariates](https://mlsanity.com/paper/2402.18805/) (2024)
- [Selecting the Number of Communities for Weighted Degree-Corrected Stochastic Block Models](https://mlsanity.com/paper/2406.05340/) (2024)
- [Community Detection for Contextual-LSBM: Theoretical Limitations of Misclassification Rate and Efficient Algorithms](https://mlsanity.com/paper/2501.11139/) (2025)
- [Signal Recovery from Random Dot-Product Graphs Under Local Differential Privacy](https://mlsanity.com/paper/2504.17274/) (2025)
- [Biological Processing Units: Leveraging an Insect Connectome to Pioneer Biofidelic Neural Architectures](https://mlsanity.com/paper/2507.10951/) (2025)
- [Graph Neural Networks Powered by Encoder Embedding for Improved Node Learning](https://mlsanity.com/paper/2507.11732/) (2025)

## Abstract (arXiv)

Community detection is a central problem of network data analysis. Given a network, the goal of community detection is to partition the network nodes into a small number of clusters, which could often help reveal interesting structures. The present paper studies community detection in Degree-Corrected Block Models (DCBMs). We first derive asymptotic minimax risks of the problem for a misclassification proportion loss under appropriate conditions. The minimax risks are shown to depend on degree-correction parameters, community sizes, and average within and between community connectivities in an intuitive and interpretable way. In addition, we propose a polynomial time algorithm to adaptively perform consistent and even asymptotically optimal community detection in DCBMs.