Detectability thresholds of general modular graphs

Abstract

We investigate the detectability thresholds of various modular structures in the stochastic block model. Our analysis reveals how the detectability threshold is related to the details of the modular pattern, including the hierarchy of the clusters. We show that certain planted structures are impossible to infer regardless of their fuzziness.

5 pages, 3 figures

References in corpus (9)

• Phase transition in the detection of modules in sparse networks
• Graph spectra and the detectability of community structure in networks
• Identification of core-periphery structure in networks
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• (Un)detectable cluster structure in sparse networks
• Phase transitions in semisupervised clustering of sparse networks
• Unifying two Graph Decompositions with Modular Decomposition
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• Global disorder transition in the community structure of large-q Potts systems