Spectra of random graphs with community structure and arbitrary degrees

Abstract

Using methods from random matrix theory researchers have recently calculated the full spectra of random networks with arbitrary degrees and with community structure. Both reveal interesting spectral features, including deviations from the Wigner semicircle distribution and phase transitions in the spectra of community structured networks. In this paper we generalize both calculations, giving a prescription for calculating the spectrum of a network with both community structure and an arbitrary degree distribution. In general the spectrum has two parts, a continuous spectral band, which can depart strongly from the classic semicircle form, and a set of outlying eigenvalues that indicate the presence of communities.

9 pages, 3 figures

References in corpus (6)

• Finding community structure in networks using the eigenvectors of matrices
• Phase transition in the detection of modules in sparse networks
• Graph spectra and the detectability of community structure in networks
• Spectra of Sparse Random Matrices
• Spectra of random graphs with arbitrary expected degrees
• (Un)detectable cluster structure in sparse networks

Cited by in corpus (19)

• Metrics for Graph Comparison: A Practitioner's Guide
• Emergence of slow-switching assemblies in structured neuronal networks
• Eigenvalue tunnelling and decay of quenched random networks
• A Survey on Theoretical Advances of Community Detection in Networks
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• A unifying model for random matrix theory in arbitrary space dimensions
• A generative model for protein contact networks
• Comparative analysis on the selection of number of clusters in community detection
• Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection
• Finite size analysis of the detectability limit of the stochastic block model
• Community detectability and structural balance dynamics in signed networks
• Structured networks and coarse-grained descriptions: a dynamical perspective
• The Kato--Temple inequality and eigenvalue concentration with applications to graph inference
• Inference of hidden structures in complex physical systems by multi-scale clustering
• Proof of a conjecture on the infinite dimension limit of a unifying model for random matrix theory
• Spectral Anomaly Detection in Very Large Graphs: Models, Noise, and Computational Complexity
• Asymptotics of the spectral radius for directed Chung-Lu random graphs with community structure
• Spectral signatures of structural change in financial networks
• Reinventing the Triangles: Rule of Thumb for Assessing Detectability