# Convexified Modularity Maximization for Degree-corrected Stochastic Block Models

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Dec 2015.

## Built on by (most cited first, 16 of 16)

- [A Survey of Community Detection Approaches: From Statistical Modeling to Deep Learning](https://mlsanity.com/paper/2101.01669/) (2021)
- [Community detection for weighted bipartite networks](https://mlsanity.com/paper/2109.10319/) (2021)
- [Spectral clustering under degree heterogeneity: a case for the random walk Laplacian](https://mlsanity.com/paper/2105.00987/) (2021)
- [Efficiently matching random inhomogeneous graphs via degree profiles](https://mlsanity.com/paper/2310.10441/) (2023)
- [Bipartite mixed membership distribution-free model. A novel model for community detection in overlapping bipartite weighted networks](https://mlsanity.com/paper/2211.00912/) (2022)
- [SDP Achieves Exact Minimax Optimality in Phase Synchronization](https://mlsanity.com/paper/2101.02347/) (2021)
- [Community detection by spectral methods in multi-layer networks](https://mlsanity.com/paper/2403.12540/) (2024)
- [Directed mixed membership stochastic blockmodel](https://mlsanity.com/paper/2101.02307/) (2021)
- [Directed degree corrected mixed membership model and estimating community memberships in directed networks](https://mlsanity.com/paper/2109.07826/) (2021)
- [A Worker-Task Specialization Model for Crowdsourcing: Efficient Inference and Fundamental Limits](https://mlsanity.com/paper/2111.12550/) (2021)
- [Mixed membership distribution-free model](https://mlsanity.com/paper/2112.04389/) (2021)
- [Graphon Estimation in bipartite graphs with observable edge labels and unobservable node labels](https://mlsanity.com/paper/2304.03590/) (2023)
- [Matrix Factorization Framework for Community Detection under the Degree-Corrected Block Model](https://mlsanity.com/paper/2601.06262/) (2026)
- [NISQ-ready community detection based on separation-node identification](https://mlsanity.com/paper/2212.14717/) (2022)
- [Selecting the Number of Communities for Weighted Degree-Corrected Stochastic Block Models](https://mlsanity.com/paper/2406.05340/) (2024)
- [Fitting networks with a cancellation trick](https://mlsanity.com/paper/2502.16728/) (2025)

## Abstract (arXiv)

The stochastic block model (SBM) is a popular framework for studying community detection in networks. This model is limited by the assumption that all nodes in the same community are statistically equivalent and have equal expected degrees. The degree-corrected stochastic block model (DCSBM) is a natural extension of SBM that allows for degree heterogeneity within communities. This paper proposes a convexified modularity maximization approach for estimating the hidden communities under DCSBM. Our approach is based on a convex programming relaxation of the classical (generalized) modularity maximization formulation, followed by a novel doubly-weighted  ℓ1 -norm  k -median procedure. We establish non-asymptotic theoretical guarantees for both approximate clustering and perfect clustering. Our approximate clustering results are insensitive to the minimum degree, and hold even in sparse regime with bounded average degrees. In the special case of SBM, these theoretical results match the best-known performance guarantees of computationally feasible algorithms. Numerically, we provide an efficient implementation of our algorithm, which is applied to both synthetic and real-world networks. Experiment results show that our method enjoys competitive performance compared to the state of the art in the literature.