Spectra of complex networks.
We propose a general approach to the description of spectra of complex networks. For the spectra of networks with uncorrelated vertices (and a local treelike structure), exact equations are derived. These equations are generalized to the case of networks with correlations between neighboring vertices. The tail of the density of eigenvalues rho(lambda) at large /lambda/ is related to the behavior of the vertex degree distribution P(k) at large k. In particular, as P(k) approximately k(-gamma), rho(lambda) approximately /lambda/(1-2 gamma). We propose a simple approximation, which enables us to calculate spectra of various graphs analytically. We analyze spectra of various complex networks and discuss the role of vertices of low degree. We show that spectra of locally treelike random graphs may serve as a starting point in the analysis of spectral properties of real-world networks, e.g., of the Internet.
Dorogovtsev
S N
SN
Departamento de Física and Centro de Física do Porto, Faculdade de Ciências, Universidade do Porto, Rua do Campo Alegre 687, 4169-007 Porto, Portugal. sdorogov@fc.up.pt
Goltsev
A V
AV
Mendes
J F F
JF
Samukhin
A N
AN