O'Reilly logo

Analysis of Complex Networks by Frank Emmert-Streib, Matthias Dehmer

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 vV 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 Aij = 1 if there is a link between nodes i and j, and Aij = 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 ϕ12,...,ϕ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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required