Spectra of random graphs with arbitrary expected degrees

Abstract

We study random graphs with arbitrary distributions of expected degree and derive expressions for the spectra of their adjacency and modularity matrices. We give a complete prescription for calculating the spectra that is exact in the limit of large network size and large vertex degrees. We also study the effect on the spectra of hubs in the network, vertices of unusually high degree, and show that these produce isolated eigenvalues outside the main spectral band, akin to impurity states in condensed matter systems, with accompanying eigenvectors that are strongly localized around the hubs. We also give numerical results that confirm our analytic expressions.

14 pages, 5 figures

References in corpus (16)

• The structure and function of complex networks
• Modularity and community structure in networks
• Community detection in graphs
• Random graphs with arbitrary degree distributions and their applications
• Synchronization in complex networks
• Network robustness and fragility: Percolation on random graphs
• Resilience of the Internet to random breakdowns
• Spectra of "Real-World" Graphs: Beyond the Semi-Circle Law
• Graph spectra and the detectability of community structure in networks
• Spectra of complex networks
• Spectra and eigenvectors of scale-free networks
• The largest eigenvalues of finite rank deformation of large Wigner matrices: convergence and nonuniversality of the fluctuations
• Spectra of Sparse Random Matrices
• Percolation on dense graph sequences
• Spectral properties of the Google matrix of the World Wide Web and other directed networks
• Spectral Properties of Directed Random Networks with Modular Structure

Cited by in corpus (37)

• Spectral methods for network community detection and graph partitioning
• Localization and centrality in networks
• OptShrink: An algorithm for improved low-rank signal matrix denoising by optimal, data-driven singular value shrinkage
• Distinct types of eigenvector localization in networks
• Message passing on networks with loops
• Enhanced detectability of community structure in multilayer networks through layer aggregation
• Epidemic Threshold of Susceptible-Infected-Susceptible Model on Complex Networks
• Eigenvalue Spectra of Modular Networks
• Relating Topological Determinants of Complex Networks to Their Spectral Properties: Structural and Dynamical Effects
• Emergence of slow-switching assemblies in structured neuronal networks
• Eigenvalue tunnelling and decay of quenched random networks
• Looplessness in networks is linked to trophic coherence
• Spectra of random networks with arbitrary degrees
• A Spectral Framework for Anomalous Subgraph Detection
• A Survey on Theoretical Advances of Community Detection in Networks
• Spectra of random graphs with community structure and arbitrary degrees
• Localization and universality of eigenvectors in directed random graphs
• Finding communities in sparse networks
• Principal eigenvector localization and centrality in networks: revisited
• Autopoietic influence hierarchies in pancreatic $\beta$-cells
• Spectral community detection in sparse networks
• Comparative analysis on the selection of number of clusters in community detection
• Anatomy of the fragmented Hilbert space: eigenvalue tunneling, quantum scars and localization in the perturbed random regular graph
• Quenched mean-field theory for the majority-vote model on complex networks
• Spectra of random networks in the weak clustering regime
• Thermodynamics of network model fitting with spectral entropies
• Effects of clustering heterogeneity on the spectral density of sparse networks
• Susceptible-infected-susceptible model on networks with eigenvector localization
• Finite size effects. The averaged eigenvalue density of Wigner random sign real symmetric matrices
• Stochastic fluctuations and the detectability limit of network communities
• Superelliptical laws for complex networks
• Spectral similarity for Barabási-Albert and Chung-Lu models
• Testing goodness-of-fit of random graph models
• Impact of Community Structure on Consensus Machine Learning
• Non-backtracking walks reveal compartments in sparse chromatin interaction networks
• Reinventing the Triangles: Rule of Thumb for Assessing Detectability
• Spectral analysis for gene communities in cancer cells