Graph spectra and the detectability of community structure in networks

Abstract

We study networks that display community structure -- groups of nodes within which connections are unusually dense. Using methods from random matrix theory, we calculate the spectra of such networks in the limit of large size, and hence demonstrate the presence of a phase transition in matrix methods for community detection, such as the popular modularity maximization method. The transition separates a regime in which such methods successfully detect the community structure from one in which the structure is present but is not detected. By comparing these results with recent analyses of maximum-likelihood methods we are able to show that spectral modularity maximization is an optimal detection method in the sense that no other method will succeed in the regime where the modularity method fails.

5 pages, 2 figures

References in corpus (5)

• Modularity and community structure in networks
• Benchmark graphs for testing community detection algorithms
• Stochastic blockmodels and community structure in networks
• Phase transition in the detection of modules in sparse networks
• (Un)detectable cluster structure in sparse networks

Cited by in corpus (37)

• Community detection in networks: A user guide
• Parsimonious module inference in large networks
• Social significance of community structure: Statistical view
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• Spectra of random graphs with arbitrary expected degrees
• Eigenvalue tunnelling and decay of quenched random networks
• Spectra of random networks with arbitrary degrees
• Unfolding the multiscale structure of networks with dynamical Ollivier-Ricci curvature
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• Universal Phase Transition in Community Detectability under a Stochastic Block Model
• Comparative Study for Inference of Hidden Classes in Stochastic Block Models
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• Analytic solution of the resolvent equations for heterogeneous random graphs: spectral and localization properties
• Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs
• Global disorder transition in the community structure of large-q Potts systems
• Clustering and Community Detection with Imbalanced Clusters
• Multi-scale Laplacian community detection in heterogeneous networks
• Hierarchical Message-Passing Graph Neural Networks
• Communities in C.elegans connectome through the prism of non-backtracking walks
• Effects of clustering heterogeneity on the spectral density of sparse networks
• Detectability thresholds of general modular graphs
• Statistical Mechanics of Dynamical System Identification
• A Random Matrix Perspective on Random Tensors
• Soft happy colourings and community structure of networks
• Consistency between ordering and clustering methods for graphs
• NISQ-ready community detection based on separation-node identification
• Linking Through Time: Memory-Enhanced Community Discovery in Temporal Networks
• Revisiting Spectral Graph Clustering with Generative Community Models
• Locally Boosted Graph Aggregation for Community Detection
• Potential energy of complex networks: a novel perspective
• Phase Transitions in Spectral Community Detection of Large Noisy Networks
• Contribution of directedness in graph spectra
• Distributed Community Detection with the WCC Metric
• Spectral clustering of annotated graphs using a factor graph representation
• Emergence of a spectral gap in a class of random matrices associated with split graphs
• Detectability threshold in weighted modular networks
• Error-Correcting Decoders for Communities in Networks