The spectral density of dense random networks and the breakdown of the Wigner semicircle law

Abstract

Although the spectra of random networks have been studied for a long time, the influence of network topology on the dense limit of network spectra remains poorly understood. By considering the configuration model of networks with four distinct degree distributions, we show that the spectral density of the adjacency matrices of dense random networks is determined by the strength of the degree fluctuations. In particular, the eigenvalue distribution of dense networks with an exponential degree distribution is governed by a simple equation, from which we uncover a logarithmic singularity in the spectral density. We also derive a relation between the fourth moment of the eigenvalue distribution and the variance of the degree distribution, which leads to a sufficient condition for the breakdown of the Wigner semicircle law for dense random networks. Based on the same relation, we propose a classification scheme of the distinct universal behaviours of the spectral density in the dense limit. Our theoretical findings should lead to important insights on the mean-field behaviour of models defined on graphs.

arXiv comment12 pages and 4 figures

References in corpus (36)

• Statistical mechanics of complex networks
• Power-law distributions in empirical data
• Statistical physics of social dynamics
• Epidemic processes in complex networks
• Random graphs with arbitrary degree distributions and their applications
• Synchronization in complex networks
• Classes of behavior of small-world networks
• Structural Vulnerability of the North American Power Grid
• Spectra of "Real-World" Graphs: Beyond the Semi-Circle Law
• The onset of synchronization in large networks of coupled oscillators
• Spectra of complex networks
• Ferromagnetic ordering in graphs with arbitrary degree distribution
• Spectra and eigenvectors of scale-free networks
• Introduction to Random Matrices - Theory and Practice
• Sparse random matrices: the eigenvalue spectrum revisited
• Cavity Approach to the Spectral Density of Sparse Symmetric Random Matrices
• Spectra of Sparse Random Matrices
• Random incidence matrices: moments of the spectral density
• Dynamics of random recurrent networks with correlated low-rank structure
• Cavity approach to the spectral density of non-Hermitian sparse matrices
• On the localization transition in symmetric random matrices
• Spectral Theory of Sparse Non-Hermitian Random Matrices
• Spectra of networks containing short loops
• Spectra of random networks with arbitrary degrees
• Spectra of sparse non-Hermitian random matrices: an analytical solution
• Large deviation function for the number of eigenvalues of sparse random graphs inside an interval
• Spectra of sparse regular graphs with loops
• Multiplication law and S transform for non-hermitian random matrices
• Spectra of Modular and Small-World Matrices
• Edge rigidity and universality of random regular graphs of intermediate degree
• Spectral Analysis of Protein-Protein Interactions in Drosophila melanogaster
• Spectral density of random graphs with topological constraints
• Linear stability analysis for large dynamical systems on directed random graphs
• Universal transient behavior in large dynamical systems on networks
• Spectral density of generalized Wishart matrices and free multiplicative convolution
• On some compound distributions with Borel summands

Cited by in corpus (16)

• Cavity and replica methods for the spectral density of sparse symmetric random matrices
• Localization and universality of eigenvectors in directed random graphs
• Eigenvalue spectra and stability of directed complex networks
• Fully localized and partially delocalized states in the tails of Erdös-Rényi graphs in the critical regime
• Analytic solution of the resolvent equations for heterogeneous random graphs: spectral and localization properties
• Dynamical Mean-Field Theory of Complex Systems on Sparse Directed Networks
• Antagonistic interactions can stabilise fixed points in heterogeneous linear dynamical systems
• Spectral properties, localization transition and multifractal eigenvectors of the Laplacian on heterogeneous networks
• Effects of clustering heterogeneity on the spectral density of sparse networks
• Nonequilibrium dynamics of the Ising model on heterogeneous networks with an arbitrary distribution of threshold noise
• Global eigenvalue fluctuations of random biregular bipartite graphs
• Sparse Random Block Matrices
• A path integral approach to sparse non-Hermitian random matrices
• Condensation of vanishing photon emission rates in random atomic clouds
• Phase-space networks and connectivity of the kagome antiferromagnet
• Mean-field theory of vector spin models on networks with arbitrary degree distributions