Algorithmic detectability threshold of the stochastic block model
arXiv:1710.08841 · doi:10.1103/PhysRevE.97.032301
Abstract
The assumption that the values of model parameters are known or correctly learned, i.e., the Nishimori condition, is one of the requirements for the detectability analysis of the stochastic block model in statistical inference. In practice, however, there is no example demonstrating that we can know the model parameters beforehand, and there is no guarantee that the model parameters can be learned accurately. In this study, we consider the expectation--maximization (EM) algorithm with belief propagation (BP) and derive its algorithmic detectability threshold. Our analysis is not restricted to the community structure, but includes general modular structures. Because the algorithm cannot always learn the planted model parameters correctly, the algorithmic detectability threshold is qualitatively different from the one with the Nishimori condition.
arXiv comment15 pages, 8 figures
References in corpus (36)
- Community detection in graphs
- Stochastic blockmodels and community structure in networks
- Community detection in networks: A user guide
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Spectral redemption: clustering sparse networks
- Spectral clustering and the high-dimensional stochastic blockmodel
- Statistical physics of inference: Thresholds and algorithms
- Phase transition in the detection of modules in sparse networks
- An efficient and principled method for detecting communities in networks
- Structure and inference in annotated networks
- Hierarchical Block Structures and High-resolution Model Selection in Large Networks
- Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
- Learning Latent Block Structure in Weighted Networks
- Uncovering latent structure in valued graphs: A variational approach
- Identification of core-periphery structure in networks
- Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
- Efficiently inferring community structure in bipartite networks
- Inferring the mesoscale structure of layered, edge-valued and time-varying networks
- Estimating the number of communities in a network
- The Nishimori line and Bayesian Statistics
- Detectability thresholds and optimal algorithms for community structure in dynamic networks
- Phase Transitions in Semidefinite Relaxations
- A network inference method for large-scale unsupervised identification of novel drug-drug interactions
- (Un)detectable cluster structure in sparse networks
- Phase transitions in semisupervised clustering of sparse networks
- Robust reconstruction on trees is determined by the second eigenvalue
- Eigenvalue Outliers of non-Hermitian Random Matrices with a Local Tree Structure
- Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
- Dynamics of the maximum marginal likelihood hyper-parameter estimation in image restoration : gradient descent vs. EM algorithm
- Predicting future conflict between team-members with parameter-free models of social networks
- The stability to instability transition in the structure of large scale networks
- Detectability of the spectral method for sparse graph partitioning
- Finite size analysis of the detectability limit of the stochastic block model
- Detectability thresholds of general modular graphs
- Community Detection and Stochastic Block Models
- Algorithmic infeasibility of community detection in higher-order networks
Cited by in corpus (11)
- Consistencies and inconsistencies between model selection and link prediction in networks
- Spectral Theory of Sparse Non-Hermitian Random Matrices
- Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
- Universality of the stochastic block model
- Linear stability analysis for large dynamical systems on directed random graphs
- Mean-field theory of graph neural networks in graph partitioning
- Localization and universality of eigenvectors in directed random graphs
- Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection
- Localization transition in non-Hermitian systems depending on reciprocity and hopping asymmetry
- Analyticity of the energy in an Ising spin glass with correlated disorder
- Democratic summary of public opinions in free-response surveys