Finite size analysis of the detectability limit of the stochastic block model

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.

18 pages, 4 figures

References in corpus (13)

• Maps of random walks on complex networks reveal community structure
• 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
• Phase transition in the detection of modules in sparse networks
• Graph spectra and the detectability of community structure in networks
• Parsimonious module inference in large networks
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• (Un)detectable cluster structure in sparse networks
• 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