# Strongly Consistent Community Detection in Popularity Adjusted Block Models

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 49 references that are in the map.
- First posted on arXiv 8 Jun 2025.

## Builds on (most cited first, 21 of 21)

- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Community detection in networks: A user guide](https://mlsanity.com/paper/1608.00163/) (2016)
- [Community Detection in Degree-Corrected Block Models](https://mlsanity.com/paper/1607.06993/) (2016)
- [Achieving Optimal Misclassification Proportion in Stochastic Block Model](https://mlsanity.com/paper/1505.03772/) (2015)
- [Network cross-validation by edge sampling](https://mlsanity.com/paper/1612.04717/) (2016)
- [Minimax Rates of Community Detection in Stochastic Block Models](https://mlsanity.com/paper/1507.05313/) (2015)
- [Network Cross-Validation for Determining the Number of Communities in Network Data](https://mlsanity.com/paper/1411.1715/) (2014)
- [Mixed Membership Estimation for Social Networks](https://mlsanity.com/paper/1708.07852/) (2017)
- [Optimal Cluster Recovery in the Labeled Stochastic Block Model](https://mlsanity.com/paper/1510.05956/) (2015)
- [A Review of Dynamic Network Models with Latent Variables](https://mlsanity.com/paper/1711.10421/) (2017)
- [Network Enhancement: a general method to denoise weighted biological networks](https://mlsanity.com/paper/1805.03327/) (2018)
- [How Many Communities Are There?](https://mlsanity.com/paper/1412.1684/) (2014)
- [Using Maximum Entry-Wise Deviation to Test the Goodness-of-Fit for Stochastic Block Models](https://mlsanity.com/paper/1703.06558/) (2017)
- [Pairwise Covariates-adjusted Block Model for Community Detection](https://mlsanity.com/paper/1807.03469/) (2018)
- [Fast Network Community Detection with Profile-Pseudo Likelihood Methods](https://mlsanity.com/paper/2011.00647/) (2020)
- [Strong Consistency of Spectral Clustering for Stochastic Block Models](https://mlsanity.com/paper/1710.06191/) (2017)
- [Popularity Adjusted Block Models are Generalized Random Dot Product Graphs](https://mlsanity.com/paper/2109.04010/) (2021)
- [Sparse Popularity Adjusted Stochastic Block Model](https://mlsanity.com/paper/1910.01931/) (2019)
- [Projected Estimation for Large-dimensional Matrix Factor Models](https://mlsanity.com/paper/2003.10285/) (2020)
- [Variational Estimators of the Degree-corrected Latent Block Model for Bipartite Networks](https://mlsanity.com/paper/2206.08465/) (2022)
- [Model-Based Clustering of Nonparametric Weighted Networks with Application to Water Pollution Analysis](https://mlsanity.com/paper/1712.07800/) (2017)

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

- [Optimal Graph Clustering without Edge Density Signals](https://mlsanity.com/paper/2510.21669/) (2025)

## Abstract (arXiv)

The Popularity Adjusted Block Model (PABM) provides a flexible framework for community detection in network data by allowing heterogeneous node popularity across communities. However, this flexibility increases model complexity and raises key unresolved challenges, particularly in effectively adapting spectral clustering techniques and efficiently achieving strong consistency in label recovery. To address these challenges, we first propose the Thresholded Cosine Spectral Clustering (TCSC) algorithm and establish its weak consistency under the PABM. We then introduce the one-step Refined TCSC algorithm and prove that it achieves strong consistency under the PABM, correctly recovering all community labels with high probability. We further show that the two-step Refined TCSC accelerates clustering error convergence, especially with small sample sizes. Additionally, we propose a data-driven approach for selecting the number of communities, which outperforms existing methods under the PABM. The effectiveness and robustness of our methods are validated through extensive simulations and real-world applications.