On the spectra of large sparse graphs with cycles

We derive exact equations that determine the spectra of undirected and directed sparsely connected regular graphs containing loops of arbitrary length. The implications of our results to the structural and dynamical properties of networks are discussed by showing how loops influence the size of the spectral gap and the propensity for synchronization. Analytical formulas for the spectrum are obtained for specific length of the loops.

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 imp...

We propose a general approach to the description of spectra of complex networks. For the spectra of networks with uncorrelated vertices (and a local tree-like 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 ...

We develop a thorough analytical study of the $O(1/N)$ correction to the spectrum of regular random graphs with $N \rightarrow \infty$ nodes. The finite size fluctuations of the resolvent are given in terms of a weighted series over the contributions coming from loops of all possible lengths, from which we obtain the isolated eigenvalue as well as an analytical expression for the $O(1/N)$ correction to the continuous part of the spectrum. The comparison between this analytica...

Many natural and social systems develop complex networks, that are usually modelled as random graphs. The eigenvalue spectrum of these graphs provides information about their structural properties. While the semi-circle law is known to describe the spectral density of uncorrelated random graphs, much less is known about the eigenvalues of real-world graphs, describing such complex systems as the Internet, metabolic pathways, networks of power stations, scientific collaboratio...

Networks are often studied using the eigenvalues of their adjacency matrix, a powerful mathematical tool with a wide range of applications. Since in real systems the exact graph structure is not known, researchers resort to random graphs to obtain eigenvalue properties from known structural features. However, this theory is far from intuitive and often requires training of free probability, cavity methods or a strong familiarity with probability theory. In this note we offer ...

The Laplacian matrix of a simple graph is the difference of the diagonal matrix of vertex degree and the (0,1) adjacency matrix. In the past decades, the Laplacian spectrum has received much more and more attention, since it has been applied to several fields, such as randomized algorithms, combinatorial optimization problems and machine learning. This paper is primarily a survey of various aspects of the eigenvalues of the Laplacian matrix of a graph for the past teens. In a...

We establish new bounds on the minimum number of distinct eigenvalues among real symmetric matrices with nonzero off-diagonal pattern described by the edges of a graph and apply these to determine the minimum number of distinct eigenvalues of several families of graphs and small graphs.

Using methods from random matrix theory researchers have recently calculated the full spectra of random networks with arbitrary degrees and with community structure. Both reveal interesting spectral features, including deviations from the Wigner semicircle distribution and phase transitions in the spectra of community structured networks. In this paper we generalize both calculations, giving a prescription for calculating the spectrum of a network with both community structur...

We describe a method for disentangling giant component and finite cluster contributions to sparse random matrix spectra, using sparse symmetric random matrices defined on Erdos-Renyi graphs as an example and test-bed.