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

• Stochastic blockmodels and community structure in networks
• Mixture models and exploratory analysis in networks
• Consistency of spectral clustering
• 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
• 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
• High Dimensional Expectation-Maximization Algorithm: Statistical Optimization and Asymptotic Normality
• Nonconvex Statistical Optimization: Minimax-Optimal Sparse PCA in Polynomial Time
• Network Cross-Validation for Determining the Number of Communities in Network Data

Cited by in corpus (28)

• 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
• Inference via Message Passing on Partially Labeled Stochastic Block Models
• Community Recovery in Graphs with Locality
• 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
• Spectral clustering in the dynamic stochastic block model
• Probabilistic community detection with unknown number of communities
• Relative Density and Exact Recovery in Heterogeneous Stochastic Block Models
• Matched bipartite block model with covariates
• 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