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

• Community structure in social and biological networks
• Modularity and community structure in networks
• Community detection in graphs
• Benchmark graphs for testing community detection algorithms
• Stochastic blockmodels and community structure in networks
• Phase transition in the detection of modules in sparse networks
• The largest eigenvalues of finite rank deformation of large Wigner matrices: convergence and nonuniversality of the fluctuations
• (Un)detectable cluster structure in sparse networks

Cited by in corpus (108)

• Community detection in networks: A user guide
• Spectral redemption: clustering sparse networks
• Spectral methods for network community detection and graph partitioning
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Parsimonious module inference in large networks
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• OptShrink: An algorithm for improved low-rank signal matrix denoising by optimal, data-driven singular value shrinkage
• Community detection and graph partitioning
• Social significance of community structure: Statistical view
• Detecting communities using asymptotical Surprise
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• Spectra of random graphs with arbitrary expected degrees
• MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel
• Multistart Methods for Quantum Approximate Optimization
• Multiway spectral community detection in networks
• Enhanced detectability of community structure in multilayer networks through layer aggregation
• On the spectrum of the normalized Laplacian of iterated triangulations of graphs
• Eigenvalue Spectra of Modular Networks
• Universal Matrix Completion
• Detectability of communities in heterogeneous networks
• Eigenvalue tunnelling and decay of quenched random networks
• Spectra of networks containing short loops
• Deep Community Detection
• A Spectral Framework for Anomalous Subgraph Detection
• Spectra of random networks with arbitrary degrees
• Graph Clustering with Graph Neural Networks
• Improved Graph Clustering
• Spectra of random graphs with community structure and arbitrary degrees
• Unfolding the multiscale structure of networks with dynamical Ollivier-Ricci curvature
• Phase Transitions in Spectral Community Detection
• Community Detection in Quantum Complex Networks
• Spectral Detection on Sparse Hypergraphs
• A paradox in community detection
• Super-resolution community detection for layer-aggregated multilayer networks
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• Consistency Thresholds for the Planted Bisection Model
• Community extraction in multilayer networks with heterogeneous community structure
• Universal Phase Transition in Community Detectability under a Stochastic Block Model
• Centrality metrics and localization in core-periphery networks
• Improving the performance of algorithms to find communities in networks
• Comparative Study for Inference of Hidden Classes in Stochastic Block Models
• Effect on normalized graph Laplacian spectrum by motif attachment and duplication
• Origin and implications of zero degeneracy in networks spectra
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• Walk modularity and community structure in networks
• Modularity and the spread of perturbations in complex dynamical systems
• A Map Equation with Metadata: Varying the Role of Attributes in Community Detection
• Identifying multi-scale communities in networks by asymptotic surprise
• Network Detection Theory and Performance
• Bayesian Discovery of Threat Networks
• Analytic solution of the resolvent equations for heterogeneous random graphs: spectral and localization properties
• Modularity and Projection of Bipartite Networks
• Phase Transitions in Community Detection: A Solvable Toy Model
• Revisiting the Bethe-Hessian: Improved Community Detection in Sparse Heterogeneous Graphs
• Finding the Resistance Distance and Eigenvector Centrality from the Network's Eigenvalues
• Comparative analysis on the selection of number of clusters in community detection
• Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs
• Community detection based on significance optimization in complex networks
• Graph Product Multilayer Networks: Spectral Properties and Applications
• Clustering and Community Detection with Imbalanced Clusters
• Global disorder transition in the community structure of large-q Potts systems
• Phase Transitions and a Model Order Selection Criterion for Spectral Graph Clustering
• Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection
• Thermodynamics of network model fitting with spectral entropies
• Detectability of the spectral method for sparse graph partitioning
• Signal processing on graphs: Transforms and tomograms
• Finite size analysis of the detectability limit of the stochastic block model
• Community detectability and structural balance dynamics in signed networks
• Multi-scale Laplacian community detection in heterogeneous networks
• Hierarchical Message-Passing Graph Neural Networks
• Decoding communities in networks
• Compressive spectral embedding: sidestepping the SVD
• Spectral partitioning in equitable graphs
• Structured networks and coarse-grained descriptions: a dynamical perspective
• Eigenvector dynamics under perturbation of modular 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
• Detectability of Macroscopic Structures in Directed Asymmetric Stochastic Block Model
• Inference of hidden structures in complex physical systems by multi-scale clustering
• Local multiresolution order in community detection
• Statistical Mechanics of Dynamical System Identification
• Uncovering Complex Overlapping Pattern of Communities in Large-scale Social Networks
• Soft happy colourings and community structure of networks
• Comprehensive spectral approach for community structure analysis on complex networks
• NISQ-ready community detection based on separation-node identification
• A Random Matrix Perspective on Random Tensors
• Maximum Likelihood Latent Space Embedding of Logistic Random Dot Product Graphs
• Multilayer Modularity Belief Propagation To Assess Detectability Of Community Structure
• Stochastic fluctuations and the detectability limit of network communities
• Consistency between ordering and clustering methods for graphs
• Large deviations of connected components in the stochastic block model
• Revisiting Spectral Graph Clustering with Generative Community Models
• Router-level community structure of the Internet Autonomous Systems
• Linking Through Time: Memory-Enhanced Community Discovery in Temporal Networks
• Locally Boosted Graph Aggregation for Community Detection
• Potential energy of complex networks: a novel perspective
• Uniqueness of communities in regular stochastic block models
• Phase Transitions in Spectral Community Detection of Large Noisy Networks
• Contribution of directedness in graph spectra
• Network induced large correlation matrix estimation
• Spectral clustering of annotated graphs using a factor graph representation
• Error-Correcting Decoders for Communities in Networks
• Distributed Community Detection with the WCC Metric
• Fragility of spectral clustering for networks with an overlapping structure
• Emergence of a spectral gap in a class of random matrices associated with split graphs
• Reinventing the Triangles: Rule of Thumb for Assessing Detectability
• Detectability threshold in weighted modular networks