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.

10 pages, 4 figures

References in corpus (9)

• Modularity and community structure in networks
• 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
• Percolation on sparse networks
• 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

Cited by in corpus (3)

• Multifractality and statistical localization in highly heterogeneous random networks
• Belief propagation on networks with cliques and chordless cycles
• On the accuracy of message-passing approaches to percolation in complex networks