A useful criterion on studying consistent estimation in community detection

Abstract

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ös-Rényi 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.

References in corpus (37)

• The structure and function of complex networks
• Finding and evaluating community structure in networks
• Community detection in graphs
• Assortative mixing in networks
• Who is the best connected scientist? A study of scientific coauthorship networks
• Stochastic blockmodels and community structure in networks
• Community detection in networks: A user guide
• Mixed membership stochastic blockmodels
• User-friendly tail bounds for sums of random matrices
• Spectral clustering and the high-dimensional stochastic blockmodel
• An efficient and principled method for detecting communities in networks
• Consistency of spectral clustering in stochastic block models
• Fast community detection by SCORE
• Consistency of community detection in networks under degree-corrected stochastic block models
• Stochastic blockmodels with growing number of classes
• Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• 20 years of network community detection
• Coauthorship and Citation Networks for Statisticians
• A goodness-of-fit test for stochastic block models
• Spectral Methods for Data Science: A Statistical Perspective
• Multilayer stochastic block models reveal the multilayer structure of complex networks
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• A Tensor Approach to Learning Mixed Membership Community Models
• Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration
• Role of normalization in spectral clustering for stochastic blockmodels
• Semidefinite Programming Based Preconditioning for More Robust Near-Separable Nonnegative Matrix Factorization
• Mixed Membership Estimation for Social Networks
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
• Exact Recovery in the Hypergraph Stochastic Block Model: a Spectral Algorithm
• Overlapping Clustering Models, and One (class) SVM to Bind Them All
• Unified ${\ell }_{2\to \infty }$ Eigenspace Perturbation Theory for Symmetric Random Matrices
• Consistent Estimation of Mixed Memberships with Successive Projections
• Spectral Algorithms for Community Detection in Directed Networks
• Multi-way blockmodels for analyzing coordinated high-dimensional responses
• On Mixed Memberships and Symmetric Nonnegative Matrix Factorizations
• Directed degree corrected mixed membership model and estimating community memberships in directed networks

Cited by in corpus (2)

• Overlapping and nonoverlapping models
• Overlapping community detection in weighted networks