A useful criterion on studying consistent estimation in community detection
Not on the map. Why?
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.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 31 of its 84 references that are in the map. First posted on arXiv 30 Sep 2021.
Builds on
31 of 84 references.
References · 31
- 2017Community Detection and Stochastic Block Modelscited by 317
- 2013Consistency of spectral clustering in stochastic block modelscited by 128
- 2020Spectral Methods for Data Science: A Statistical Perspectivecited by 111
- 2016Community detection in networks: A user guidecited by 105
- 2014Exact Recovery in the Stochastic Block Modelcited by 77
- 2013Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodelcited by 45
- 2015Achieving Optimal Misclassification Proportion in Stochastic Block Modelcited by 35
- 2019Community Detection for Hypergraph Networks via Regularized Tensor Power Iterationcited by 26
- 2013Impact of regularization on Spectral Clusteringcited by 25
- 2015Community Detection and Classification in Hierarchical Stochastic Blockmodelscited by 23
- 2014Coauthorship and Citation Networks for Statisticianscited by 22
- 2014Detecting Overlapping Communities in Networks Using Spectral Methodscited by 22
19 more
- 2017Estimating Mixed Memberships with Sharp Eigenvector Deviationscited by 22
- 2014A goodness-of-fit test for stochastic block modelscited by 20
- 2018Analysis of spectral clustering algorithms for community detection: the general bipartite settingcited by 20
- 2014Robust and computationally feasible community detection in the presence of arbitrary outlier nodescited by 17
- 2020Spectral Algorithms for Community Detection in Directed Networkscited by 17
- 2016On Mixed Memberships and Symmetric Nonnegative Matrix Factorizationscited by 14
- 2013Semidefinite Programming Based Preconditioning for More Robust Near-Separable Nonnegative Matrix Factorizationcited by 13
- 2015Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensionscited by 13
- 2015Random Laplacian matrices and convex relaxationscited by 13
- 2018Overlapping Clustering Models, and One (class) SVM to Bind Them Allcited by 10
- 2013A Tensor Approach to Learning Mixed Membership Community Modelscited by 9
- 2018Exact Recovery in the Hypergraph Stochastic Block Model: a Spectral Algorithmcited by 9
- 2013Role of normalization in spectral clustering for stochastic blockmodelscited by 7
- 2014Multilayer stochastic block models reveal the multilayer structure of complex networkscited by 7
- 2017Variational Inference for Stochastic Block Models from Sampled Datacited by 7
- 2015Multisection in the Stochastic Block Model using Semidefinite Programmingcited by 4
- 2014Model Selection in Overlapping Stochastic Block Modelscited by 3
- 2015A Spectral Algorithm with Additive Clustering for the Recovery of Overlapping Communities in Networkscited by 3
- 2021Directed degree corrected mixed membership model and estimating community memberships in directed networkscited by 2
Built on by
Citing papers per year: 2021: 2; 2022: 1.
3 papers.