Finite size analysis of the detectability limit of the stochastic block model
arXiv:1701.00062 · doi:10.1103/PhysRevE.95.062304
Abstract
It has been shown in recent years that the stochastic block model (SBM) is sometimes undetectable in the sparse limit, i.e., that no algorithm can identify a partition correlated with the partition used to generate an instance, if the instance is sparse enough and infinitely large. In this contribution, we treat the finite case explicitly, using arguments drawn from information theory and statistics. We give a necessary condition for finite-size detectability in the general SBM. We then distinguish the concept of average detectability from the concept of instance-by-instance detectability and give explicit formulas for both definitions. Using these formulas, we prove that there exist large equivalence classes of parameters, where widely different network ensembles are equally detectable with respect to our definitions of detectability. In an extensive case study, we investigate the finite-size detectability of a simplified variant of the SBM, which encompasses a number of important models as special cases. These models include the symmetric SBM, the planted coloring model, and more exotic SBMs not previously studied. We conclude with three appendices, where we study the interplay of noise and detectability, establish a connection between our information-theoretic approach and random matrix theory, and provide proofs of some of the more technical results.
arXiv comment18 pages, 4 figures
References in corpus (31)
- Community detection in graphs
- Maps of random walks on complex networks reveal community structure
- Random graphs with arbitrary degree distributions and their applications
- Resolution limit in community detection
- Comparing community structure identification
- Hierarchical structure and the prediction of missing links in networks
- Stochastic blockmodels and community structure in networks
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Spectral redemption: clustering sparse networks
- Spectral methods for network community detection and graph partitioning
- Phase transition in the detection of modules in sparse networks
- Community detection in networks: Modularity optimization and maximum likelihood are equivalent
- Graph spectra and the detectability of community structure in networks
- Optimal network modularity for information diffusion
- Hierarchical Block Structures and High-resolution Model Selection in Large Networks
- Community structure and scale-free collections of Erdös-Rényi graphs
- Parsimonious module inference in large networks
- Estimating the number of communities in a network
- Entropy of stochastic blockmodel ensembles
- Model selection and hypothesis testing for large-scale network models with overlapping groups
- Evaluating accuracy of community detection using the relative normalized mutual information
- Eigenvalue Spectra of Modular Networks
- (Un)detectable cluster structure in sparse networks
- Spectra of random graphs with community structure and arbitrary degrees
- Community detection in networks with unequal groups
- Structural preferential attachment: Network organization beyond the link
- Phase Transitions in Community Detection: A Solvable Toy Model
- Growing networks of overlapping communities with internal structure
- Model-free consistency of graph partitioning
- Detectability thresholds of general modular graphs
- Community Detection and Stochastic Block Models
Cited by in corpus (7)
- Universality of the stochastic block model
- Threefold way to the dimension reduction of dynamics on networks: an application to synchronization
- Algorithmic detectability threshold of the stochastic block model
- Duality between predictability and reconstructability in complex systems
- Decoding communities in networks
- Sequential locality of graphs and its hypothesis testing
- Linking Through Time: Memory-Enhanced Community Discovery in Temporal Networks