# A useful criterion on studying consistent estimation in community detection

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 84 references that are in the map.
- First posted on arXiv 30 Sep 2021.

## Builds on (most cited first, 30 of 31)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Spectral Methods for Data Science: A Statistical Perspective](https://mlsanity.com/paper/2012.08496/) (2020)
- [Community detection in networks: A user guide](https://mlsanity.com/paper/1608.00163/) (2016)
- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel](https://mlsanity.com/paper/1309.4111/) (2013)
- [Achieving Optimal Misclassification Proportion in Stochastic Block Model](https://mlsanity.com/paper/1505.03772/) (2015)
- [Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration](https://mlsanity.com/paper/1909.06503/) (2019)
- [Impact of regularization on Spectral Clustering](https://mlsanity.com/paper/1312.1733/) (2013)
- [Community Detection and Classification in Hierarchical Stochastic Blockmodels](https://mlsanity.com/paper/1503.02115/) (2015)
- [Coauthorship and Citation Networks for Statisticians](https://mlsanity.com/paper/1410.2840/) (2014)
- [Detecting Overlapping Communities in Networks Using Spectral Methods](https://mlsanity.com/paper/1412.3432/) (2014)
- [Estimating Mixed Memberships with Sharp Eigenvector Deviations](https://mlsanity.com/paper/1709.00407/) (2017)
- [A goodness-of-fit test for stochastic block models](https://mlsanity.com/paper/1412.4857/) (2014)
- [Analysis of spectral clustering algorithms for community detection: the general bipartite setting](https://mlsanity.com/paper/1803.04547/) (2018)
- [Robust and computationally feasible community detection in the presence of arbitrary outlier nodes](https://mlsanity.com/paper/1404.6000/) (2014)
- [Spectral Algorithms for Community Detection in Directed Networks](https://mlsanity.com/paper/2008.03820/) (2020)
- [Random Laplacian matrices and convex relaxations](https://mlsanity.com/paper/1504.03987/) (2015)
- [On Mixed Memberships and Symmetric Nonnegative Matrix Factorizations](https://mlsanity.com/paper/1607.00084/) (2016)
- [Semidefinite Programming Based Preconditioning for More Robust Near-Separable Nonnegative Matrix Factorization](https://mlsanity.com/paper/1310.2273/) (2013)
- [Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions](https://mlsanity.com/paper/1502.07738/) (2015)
- [Overlapping Clustering Models, and One (class) SVM to Bind Them All](https://mlsanity.com/paper/1806.06945/) (2018)
- [A Tensor Approach to Learning Mixed Membership Community Models](https://mlsanity.com/paper/1302.2684/) (2013)
- [Exact Recovery in the Hypergraph Stochastic Block Model: a Spectral Algorithm](https://mlsanity.com/paper/1811.06931/) (2018)
- [Role of normalization in spectral clustering for stochastic blockmodels](https://mlsanity.com/paper/1310.1495/) (2013)
- [Multilayer stochastic block models reveal the multilayer structure of complex networks](https://mlsanity.com/paper/1411.1098/) (2014)
- [Variational Inference for Stochastic Block Models from Sampled Data](https://mlsanity.com/paper/1707.04141/) (2017)
- [Multisection in the Stochastic Block Model using Semidefinite Programming](https://mlsanity.com/paper/1507.02323/) (2015)
- [Model Selection in Overlapping Stochastic Block Models](https://mlsanity.com/paper/1405.2722/) (2014)
- [A Spectral Algorithm with Additive Clustering for the Recovery of Overlapping Communities in Networks](https://mlsanity.com/paper/1506.04158/) (2015)

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

- [Bipartite mixed membership distribution-free model. A novel model for community detection in overlapping bipartite weighted networks](https://mlsanity.com/paper/2211.00912/) (2022)
- [Mixed membership distribution-free model](https://mlsanity.com/paper/2112.04389/) (2021)
- [Overlapping and nonoverlapping models](https://mlsanity.com/paper/2111.01392/) (2021)

## Abstract (arXiv)

In network analysis, developing a unified theoretical framework that can compare methods under different models is an interesting problem. This paper proposes a partial solution to this problem. We summarize the idea of using separation condition for a standard network and sharp threshold of Erd"os-R'enyi random graph to study consistent estimation, compare theoretical error rates and requirements on network sparsity of spectral methods under models that can degenerate to stochastic block model as a four-step criterion SCSTC. Using SCSTC, we find some inconsistent phenomena on separation condition and sharp threshold in community detection. Especially, we find original theoretical results of the SPACL algorithm introduced to estimate network memberships under the mixed membership stochastic blockmodel were sub-optimal. To find the formation mechanism of inconsistencies, we re-establish theoretical convergence rates of this algorithm by applying recent techniques on row-wise eigenvector deviation. The results are further extended to the degree corrected mixed membership model. By comparison, our results enjoy smaller error rates, lesser dependence on the number of communities, weaker requirements on network sparsity, and so forth. Furthermore, separation condition and sharp threshold obtained from our theoretical results match classical results, which shows the usefulness of this criterion on studying consistent estimation.