Achieving optimal misclassification proportion in stochastic block models
From MaRDI portal
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.
Recommendations
- Community detection in degree-corrected block models
- Minimax rates of community detection in stochastic block models
- Bayesian degree-corrected stochastic blockmodels for community detection
- Optimal rates for community estimation in the weighted stochastic block model
- Community detection and stochastic block models: recent developments
Cited in
(84)- Rate-optimal graphon estimation
- Bayesian community detection
- Estimating a network from multiple noisy realizations
- Community detection in degree-corrected block models
- Fluctuations for block spin Ising models
- Fluctuation results for general block spin Ising models
- Clustering in block Markov chains
- Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
- Robust high-dimensional factor models with applications to statistical machine learning
- Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees
- Non-convex exact community recovery in stochastic block model
- Global and individualized community detection in inhomogeneous multilayer networks
- Iterative algorithm for discrete structure recovery
- Multi-group binary choice with social interaction and a random communication structure -- a random graph approach
- Optimal rates for community estimation in the weighted stochastic block model
- Rate optimal Chernoff bound and application to community detection in the stochastic block models
- Exact recovery in block spin Ising models at the critical line
- Entrywise eigenvector analysis of random matrices with low expected rank
- Theoretical and computational guarantees of mean field variational inference for community detection
- Network classification with applications to brain connectomics
- Exact recovery in the Ising blockmodel
- Dynamic network models and graphon estimation
- Partial recovery bounds for clustering with the relaxed K-means
- Numerical study of reciprocal recommendation with domain matching
- Convexified modularity maximization for degree-corrected stochastic block models
- Test on stochastic block model: local smoothing and extreme value theory
- Spectral norm bounds for block Markov chain random matrices
- Singular value distribution of dense random matrices with block Markovian dependence
- Minimax rates of community detection in stochastic block models
- scientific article; zbMATH DE number 4066166 (Why is no real title available?)
- Matched bipartite block model with covariates
- Analysis of spectral clustering algorithms for community detection: the general bipartite setting
- Universal latent space model fitting for large networks with edge covariates
- Optimal bipartite network clustering
- Change point estimation in a dynamic stochastic block model
- Community Detection in Sparse Networks Using the Symmetrized Laplacian Inverse Matrix (SLIM)
- Randomized Spectral Clustering in Large-Scale Stochastic Block Models
- On model selection for dense stochastic block models
- Hierarchical Community Detection by Recursive Partitioning
- Graph-Theoretic Concepts in Computer Science
- Using Maximum Entry-Wise Deviation to Test the Goodness of Fit for Stochastic Block Models
- Efficient Estimation for Random Dot Product Graphs via a One-Step Procedure
- Estimating Causal Peer Influence in Homophilous Social Networks by Inferring Latent Locations
- Fast Network Community Detection With Profile-Pseudo Likelihood Methods
- A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization
- Localization in 1D non-parametric latent space models from pairwise affinities
- Asymptotic uncertainty quantification for communities in sparse planted bi-section models
- Entrywise limit theorems for eigenvectors of signal-plus-noise matrix models with weak signals
- Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks
- Online estimation and community detection of network point processes for event streams
- Special invited paper: the SCORE normalization, especially for heterogeneous network and text data
- Profile-pseudo likelihood methods for community detection of multilayer stochastic block models
- Two-sample test of stochastic block models
- PCABM: Pairwise Covariates-Adjusted Block Model for Community Detection
- Network Estimation by Mixing: Adaptivity and More
- Hypothesis testing for equality of latent positions in random graphs
- Two-sample test of stochastic block models via the maximum sampling entry-wise deviation
- Pair-matching: link prediction with adaptive queries
- Computational and statistical thresholds in multi-layer stochastic block models
- Spectral clustering in the dynamic stochastic block model
- Optimal and exact recovery on the general nonuniform hypergraph stochastic block model
- Confidence sets in a sparse stochastic block model with two communities of unknown sizes
- Orthogonal symmetric non-negative matrix factorization under the stochastic block model
- Community extraction of network data under stochastic block models
- Variational inference for estimating dynamic stochastic block models through an evolutionary algorithm
- Higher-order entrywise eigenvectors analysis of low-rank random matrices: bias correction, Edgeworth expansion and bootstrap
- Subsampling based community detection for large networks
- Detection and evaluation of clusters within sequential data
- Semi-supervised clustering of sparse graphs: crossing the information-theoretic threshold
- Joint Network Reconstruction and Community Detection from Rich but Noisy Data
- Optimal Network Membership Estimation under Severe Degree Heterogeneity
- Spectral properties and weak detection in stochastic block models
- Testing for the network small-world property
- Network-adjusted covariates for community detection
- A Bootstrap-based Method for Testing Similarity of Matched Networks
- Consistency of Lloyd's algorithm under perturbations
- Spectral clustering with likelihood refinement for high-dimensional latent class recovery
- Robust estimation of a Markov chain transition matrix from multiple sample paths
- Deviation bounds for the norm of a random vector under exponential moment conditions with applications
- A goodness-of-fit test for sparse networks
- Community detection in sparse networks via Grothendieck's inequality
- A Unified Framework for Community Detection and Model Selection in Blockmodels
- Large-scale estimation of random graph models with local dependence
- Adjusted chi-square test for degree-corrected block models
This page was built for publication: Achieving optimal misclassification proportion in stochastic block models
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5361330)
