Analysis of Complex Networks

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 ϕ₁,ϕ₂,...,ϕ_n with eigenvalues λ₁ ≥ λ₂ ≥ 0 ... ≥ λ_n [11]. The largest eigenvalue of graph λ₁ is known as the principal eigenvalue, the spectral radius, or the Perron–Frobenius eigenvalue [11]. The eigenvector associated with this eigenvalue is also ...