Spectra of random networks with arbitrary degrees

Abstract

We derive a message passing method for computing the spectra of locally tree-like networks and an approximation to it that allows us to compute closed-form expressions or fast numerical approximates for the spectral density of random graphs with arbitrary node degrees -- the so-called configuration model. We find the latter approximation to work well for all but the sparsest of networks. We also derive bounds on the position of the band edges of the spectrum, which are important for identifying structural phase transitions in networks.

arXiv comment10 pages, 4 figures

References in corpus (24)

• Emergence of scaling in random networks
• Modularity and community structure in networks
• Epidemic spreading in scale-free networks
• Random graphs with arbitrary degree distributions and their applications
• Classes of behavior of small-world networks
• Epidemic dynamics and endemic states in complex networks
• Spectra of "Real-World" Graphs: Beyond the Semi-Circle Law
• Phase transition in the detection of modules in sparse networks
• A message passing approach for general epidemic models
• Graph spectra and the detectability of community structure in networks
• Localization and centrality in networks
• Percolation on sparse networks
• Spectra of complex networks
• Spectra and eigenvectors of scale-free networks
• Sparse random matrices: the eigenvalue spectrum revisited
• Cavity Approach to the Spectral Density of Sparse Symmetric Random Matrices
• Spectra of Sparse Random Matrices
• Dynamical Systems on Networks: A Tutorial
• Spectra of random graphs with arbitrary expected degrees
• A single defect approximation for localized states on random lattices
• Percolation on dense graph sequences
• Spectra of sparse regular graphs with loops
• Spectral density of random graphs with topological constraints
• Localization on low-order eigenvectors of data matrices

Cited by in corpus (9)

• Spectra of networks containing short loops
• Message passing methods on complex networks
• The spectral density of dense random networks and the breakdown of the Wigner semicircle law
• Multifractality and statistical localization in highly heterogeneous random networks
• Effects of clustering heterogeneity on the spectral density of sparse networks
• Belief propagation on networks with cliques and chordless cycles
• Spectral density of random graphs: convergence properties and application in model fitting
• On the accuracy of message-passing approaches to percolation in complex networks
• Statistical field theory of random graphs with prescribed degrees