17 - Spectral properties, transport, diffusion and dynamics

Summary

In this chapter we discuss the spectral properties of networks, and their relation to dynamical properties such as diffusion. There are two main characteristic matrices for a graph, the adjacency matrix and the Laplacian. We discuss both of them and explain the relation to the dynamical properties. A good summary of results on the spectrum of networks can be found in [Chu97]. For a nice survey of random walks on graphs see [Lov96].

The spectrum of the adjacency matrix

As described in Chapter 1, the adjacency matrix, A, is an N × N matrix (where N is the number of nodes) whose entries are A_{i, j} = 1 if there is an edge between nodes i and j, and A_{i, j} = 0 otherwise. If the graph is not directed then the adjacency matrix is symmetric. In a directed graph it is not necessarily so.

The spectrum of this matrix is the collection of eigenvalues of the matrix. Since we refer to an ensemble of graphs rather than a single graph, we are interested in the distribution of eigenvalues when the entire ensemble is considered.

The study of the spectrum of random graphs is strongly related to the study of the spectrum of random matrices in general. The study of random matrix theory was initiated by Wigner [Wig55] in the 1950s. His main goal was to understand the energy levels of the nucleus. These levels are the eigenvalues of the Hamiltonian (energy) matrix.