Algorithmic detectability threshold of the stochastic block model

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.

15 pages, 8 figures

References in corpus (17)

• Stochastic blockmodels and community structure in networks
• Community detection in networks: A user guide
• Phase transition in the detection of modules in sparse networks
• 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
• 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
• 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
• Predicting future conflict between team-members with parameter-free models of social networks
• Finite size analysis of the detectability limit of the stochastic block model
• Community Detection and Stochastic Block Models
• Detectability thresholds of general modular graphs
• 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