Achieving Optimal Misclassification Proportion in Stochastic Block Model

Abstract

Community detection is a fundamental statistical problem in network data analysis. Many algorithms have been proposed to tackle this problem. Most of these algorithms are not guaranteed to achieve the statistical optimality of the problem, while procedures that achieve information theoretic limits for general parameter spaces are not computationally tractable. In this paper, we present a computationally feasible two-stage method that achieves optimal statistical performance in misclassification proportion for stochastic block model under weak regularity conditions. Our two-stage procedure consists of a generic refinement step that can take a wide range of weakly consistent community detection procedures as initializer, to which the refinement stage applies and outputs a community assignment achieving optimal misclassification proportion with high probability. The practical effectiveness of the new algorithm is demonstrated by competitive numerical results.

References in corpus (26)

• Community structure in social and biological networks
• Simultaneous analysis of Lasso and Dantzig selector
• Stochastic blockmodels and community structure in networks
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Mixture models and exploratory analysis in networks
• Consistency of spectral clustering
• Sparse principal component analysis and iterative thresholding
• Fast community detection by SCORE
• Sparse PCA: Optimal rates and adaptive estimation
• Stochastic blockmodels with growing number of classes
• Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Stochastic Block Models and Reconstruction
• Augmented sparse principal component analysis for high dimensional data
• Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms
• Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms
• Sparse CCA: Adaptive Estimation and Computational Barriers
• Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
• Nonconvex Statistical Optimization: Minimax-Optimal Sparse PCA in Polynomial Time
• High Dimensional Expectation-Maximization Algorithm: Statistical Optimization and Asymptotic Normality
• Community Detection via Random and Adaptive Sampling
• A Generic Sample Splitting Approach for Refined Community Recovery in Stochastic Block Models
• Impact of regularization on Spectral Clustering
• Network Cross-Validation for Determining the Number of Communities in Network Data
• How Many Communities Are There?

Cited by in corpus (29)

• Rate-optimal graphon estimation
• Consistency of Spectral Hypergraph Partitioning under Planted Partition Model
• Community detection in multi-relational data with restricted multi-layer stochastic blockmodel
• Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
• Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank
• A Survey on Theoretical Advances of Community Detection in Networks
• Testing Network Structure Using Relations Between Small Subgraph Probabilities
• Optimal hypothesis testing for stochastic block models with growing degrees
• Uniform Hypergraph Partitioning: Provable Tensor Methods and Sampling Techniques
• Information-theoretic bounds for exact recovery in weighted stochastic block models using the Renyi divergence
• Density Evolution in the Degree-correlated Stochastic Block Model
• Community Recovery in Graphs with Locality
• Inference via Message Passing on Partially Labeled Stochastic Block Models
• Recovering communities in the general stochastic block model without knowing the parameters
• Network cross-validation by edge sampling
• Community Detection in Degree-Corrected Block Models
• Community detection with nodal information
• Robust and efficient multi-way spectral clustering
• Exploration of Large Networks with Covariates via Fast and Universal Latent Space Model Fitting
• Robust high dimensional factor models with applications to statistical machine learning
• Higher-Order Spectral Clustering under Superimposed Stochastic Block Model
• Probabilistic community detection with unknown number of communities
• Spectral clustering in the dynamic stochastic block model
• Matched bipartite block model with covariates
• Relative Density and Exact Recovery in Heterogeneous Stochastic Block Models
• Local Algorithms for Block Models with Side Information
• Exponential error rates of SDP for block models: Beyond Grothendieck's inequality
• Edge sampling using network local information
• A Semidefinite Program for Structured Blockmodels