Publication :
Finite-size analysis of the detectability limit of the stochastic block model

En cours de chargement...
Vignette d'image
Direction de publication
Direction de recherche
Titre de la revue
ISSN de la revue
Titre du volume
American Physical Society
Projets de recherche
Structures organisationnelles
Numéro de revue

It has been shown in recent years that the stochastic block model 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.

Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics, Vol. 95 (6), 62304-1 - 62304-16 (2017)
URL vers la version publiée
Community structure , Continuous phase transition , Erdos-Renyi graph , Stochastic networks , Uncorrelated network , Block models , Metropolis algorithm
Type de document
article de recherche