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 (9)

• Stochastic blockmodels and community structure in networks
• Community detection in networks: A user guide
• 20 years of network community detection
• Spectral Methods for Data Science: A Statistical Perspective
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration
• Unified ${\ell }_{2\to \infty }$ Eigenspace Perturbation Theory for Symmetric Random Matrices
• Spectral Algorithms for Community Detection in Directed Networks
• 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