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 (21)

• Community structure in social and biological networks
• Community detection in graphs
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Spectral redemption: clustering sparse networks
• Spectral clustering and the high-dimensional stochastic blockmodel
• Phase transition in the detection of modules in sparse networks
• Graph spectra and the detectability of community structure in networks
• Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
• Identification of core-periphery structure in networks
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Detectability thresholds and optimal algorithms for community structure in dynamic networks
• (Un)detectable cluster structure in sparse networks
• Detectability of communities in heterogeneous networks
• Phase transitions in semisupervised clustering of sparse networks
• Phase transitions in random Potts systems and the community detection problem: spin-glass type and dynamic perspectives
• A paradox in community detection
• Unifying two Graph Decompositions with Modular Decomposition
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• Phase Transitions in Community Detection: A Solvable Toy Model
• Global disorder transition in the community structure of large-q Potts systems
• Detectability of the spectral method for sparse graph partitioning

Cited by in corpus (5)

• Community Detection in Bipartite Networks with Stochastic Blockmodels
• Universality of the stochastic block model
• Community Detection and Improved Detectability in Multiplex Networks
• Algorithmic detectability threshold of the stochastic block model
• Finite size analysis of the detectability limit of the stochastic block model