## 4.2 Background on Graph Spectra

A graph *G* = (*V*, *E*) is a set of nodes *V* connected by means of the elements of the set of links *E*. Here we are dealing only with simple graphs [6], that is, an undirected graph without multiple links or self-loops. Thus, by graph we mean a simple graph. A node *v* ∈ *V* is a terminal point of a link and represents an abstraction of an entity in a complex network such as a person, a city, a protein, an atom, etc. The links represent the relations between these entities.

A graph *G* = (*V*, *E*) can be represented by different kinds of matrices [6]. The (ordinary) spectrum of a graph always refers to the spectrum of the adjacency matrix of the graph [9]. Thus, we will be concerned here only with this matrix. Excellent reviews about the Laplacian spectrum of graphs can be found in the literature [10]. The adjacency matrix **A** = **A**(*G*) of a graph *G* = (*V*, *E*) is a symmetric matrix of order *n* = |*V*|, where |···| means the cardinality of the set and where **A**_{ij} = 1 if there is a link between nodes *i* and *j*, and **A**_{ij} = 0 otherwise.

The “spectrum” of a network is a listing of the *eigenvalues* of the adjacency matrix of such a network. It is well known that every *n* × *n* real symmetric matrix **A** has a spectrum of *n* orthonormal eigenvectors ϕ_{1},ϕ_{2},...,ϕ_{n} with eigenvalues λ_{1} ≥ λ_{2} ≥ 0 ... ≥ λ_{n} [11]. The largest eigenvalue of graph λ_{1} is known as the principal eigenvalue, the spectral radius, or the Perron–Frobenius eigenvalue [11]. The eigenvector associated with this eigenvalue is also ...