8 Spectra of Complex Networks

Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

Chapter 8
Spectra of Complex Networks

The eigenvalues and eigenvectors of a structure matrix of a complex network reveal information about its topology and its collective behavior. These structure matrices can be the adjacency matrix, weight matrix, Laplacian matrix, or random walk matrix of the graph representing a complex network. Studying the spectra, that is, the eigendecomposition of these matrices, leads to interesting results about the underlying network. For example, eigendecomposition of the Laplacian matrix helps in identifying communities (clusters) in a social network. Moreover, spectral densities of various complex network models follow specific patterns and, therefore, allow classification of networks. Furthermore, the eigenvalues of a structure matrix of a network provide frequency interpretation that is useful for analyzing data defined on the network. This chapter deals with the eigenvalues and eigenvectors of various matrices related to a graph, or indirectly to a complex network.

8.1 Introduction

The spectrum of a graph is the set of eigenvalues of a structure matrix representing the graph. These matrices include, but are not limited to, the adjacency matrix, Laplacian matrix, normalized Laplacian matrix, and random walk matrix. The spectrum of a graph is highly dependent on the form of the matrix and, therefore, depending on the structure matrix chosen, we can have different spectra for a graph. The graph spectrum has been widely used in graph theory to characterize the properties of a graph and extract structural information of the graph. An interesting property of the graph spectrum is that it is invariant to graph labeling; that is, no matter how vertices of the graph are indexed, the graph spectrum is unique. Therefore, the spectrum of the graph can be used as an alternative representation of a graph.

Most of the real-world networks are very large, containing thousands of nodes. For such a network, it is suitable to study their spectral density¹ instead of the list of eigenvalues. It is observed that spectral densities (adjacency matrix as well as Laplacian matrix) of complex networks follow specific patterns. For example, spectral density of an Erdös-Rényi (ER) random graph follows semicircle law [138], [139]. However, for scale-free networks, the spectral density has a shape of a triangle with a power-law tail [140], [141]. Moreover, for small-world networks, the distribution of spectra consists of several sharp peaks [140]. Studying the spectral distribution of various complex network models not only provides a means for network classification, but also reveals various topological features of networks. For example, by estimating moments of the spectral density, one can calculate the number of various subgraphs [142].

There are various ways to represent spectral distribution of a matrix. Among those, a simple way to show the distribution of eigenvalues is to use a histogram plot or relative frequency plot with desired number of bins between the interval of [λ_min, λ_max], where λ_min is the smallest magnitude eigenvalue of a structure matrix and λ_max is the eigenvalue with largest magnitude. The second method to represent the spectral distribution is to convolve the impulse train (Dirac delta sum) $\sum_{i = 0}^{N - 1} δ (λ - λ_{i})$ $\sum_{i = 0}^{N - 1} δ (λ - λ_{i})$ with a smooth kernel g(λ, λ_i) and plot the density function

(8.1.1) $ρ (λ) = g (λ, λ_{i})$ $ρ (λ) = g (λ, λ_{i})$

The smooth kernels can be Gaussian distribution or Cauchy-Lorentz distribution. When using a Gaussian kernel with a fixed variance σ², the spectral distribution is represented by

(8.1.2) $ρ (λ) = \frac{1}{\sqrt{2 π σ^{2}}} \sum_{i = 0}^{N - 1} e x p (- \frac{(λ - λ_{i})^{2}}{2 σ^{2}}) .$ $ρ (λ) = \frac{1}{\sqrt{2 π σ^{2}}} \sum_{i = 0}^{N - 1} e x p (- \frac{(λ - λ_{i})^{2}}{2 σ^{2}}) .$

Small values of the variance σ² emphasize the finer details, whereas large values bring out the global pattern more conspicuously.

In the chapter, we discuss spectra of adjacency and Laplacian matrices of different graphs. Various bounds on the eigenvalues of the adjacency and Laplacian matrices are also discussed. Spectra of complex network models including random, small-world, and scale-free networks are discussed. Moreover, the connection between discrete Fourier transform (DFT) and eigendecompositions of adjacency and Laplacian matrices of a ring graph is highlighted.

8.2 Spectrum of a Graph

An N-node graph $𝒢$ $?$ can be described using various structure matrices such as the adjacency matrix, Laplacian matrix, and random walk matrix. The set of (N number of) eigenvalues of a structure matrix of the graph is known as the graph spectrum. The spectrum of a graph does not depend on the labeling or indexing of vertices. Depending on the indexing of the vertices of a graph, the adjacency matrix may not be unique; however, the spectrum remains unaltered.

Example

Figure 8.1 shows different vertex indexings of a three-node path graph and their corresponding adjacency and Laplacian matrices. For all three cases, the adjacency matrix spectrum is ${- \sqrt{2}, 0, \sqrt{2}}$ ${- \sqrt{2}, 0, \sqrt{2}}$ and the Laplacian matrix spectrum is {0, 1, 3}.

Three different vertex indexings of a three-node path graph are shown with adjacency and Laplacian matrices for each.

The vertex indexings are listed on the left, followed by the adjacency and Laplacian matrices. All the matrices are 3 cross 3 matrices. The first graph has the nodes connected in the order 1, 2, and 3, in a horizontal series. Its adjacency matrix A reads the following row-wise: 0 1 0, 1 0 1, and 0 1 0. The Laplacian matrix L reads the following row-wise: 1 -1 0, -1 2 -1, and 0 -1 1. The second graph has the nodes connected in the order 1, 3, and 2, in a horizontal series. Its adjacency matrix A reads the following row-wise: 0 0 1, 0 0 1, and 1 1 0. The Laplacian matrix L reads the following row-wise: 1 0 -1, 0 1 -1, and -1 -1 2. The third graph has the nodes connected in the order 2, 1, and 3, in a horizontal series. Its adjacency matrix A reads the following row-wise: 0 1 1, 1 0 0, and 1 0 0. The Laplacian matrix L reads the following row-wise: 2 -1 -1, -1 1 0, and -1 0 1.

Figure 8.1. Different vertex indexings of a three-node path graph and corresponding adjacency and Laplacian matrices. For all the three cases, the graph spectrum (adjacency as well as Laplacian) remains unchanged.

Although the spectrum of a graph can reveal many characteristics of the graph, the structure of the graph cannot be uniquely determined from the graph spectrum. We may have two or more different graphs with the same spectra. The graphs having same spectra are called cospectral or isospectral graphs. For example, the graphs $𝒢_{1}$ $?_{1}$ and $𝒢_{2}$ $?_{2}$ shown in Figure 8.2 are cospectral graphs with respect to the adjacency matrix, since the eigenvalues of the adjacency matrices of both the graphs are {−2, 0, 0, 0, 2}. Note that, however, the eigenvectors of the adjacency matrices of the two graphs are different. For generating pairs of cospectral graphs, Seidel switching is a popular technique. Characterization by graph spectra is discussed in detail in [143], [144].

Two examples of cospectral graphs with respect to the adjacency matrix.

Figure 8.2. Cospectral graphs with respect to the adjacency matrix

Sometimes it is also beneficial to study the eigenvectors of a structure matrix of a graph. In Chapter 9, we will see that the eigenvectors of the Laplacian matrix of a graph act as graph harmonics that allow frequency analysis of signals defined on the graph. Moreover, eigenvectors of the graph Laplacian are also used in clustering of the graph (Section 8.5.5). For a three-node path graph, Figure 8.3 shows all the eigenvectors of the adjacency matrix and Figure 8.4 shows the eigenvectors of the Laplacian matrix. Note that all the eigenvectors have been normalized to have unit ℓ₂-norms.

Three figures showing the Eigenvectors of the adjacency matrix of a three-node path graph.

The figures are placed one beside the other and are labeled alphabetically. The nodes are connected in the order 1, 2, and 3, in a horizontal series in all three figures. Figure a, corresponds to lambda equals minus square root of 2. Short vertical lines are drawn upward from nodes 1 and 3 of equal magnitude and are marked 0.5; while a line of a slightly greater magnitude is drawn downward from the node 2 and is marked minus (1 over the square root of 2). Figure b corresponds to lambda equals 0. A short vertical line is drawn upward from node 1 and is marked 1 over the square root of 2, a line of the equal length is drawn downward from the node 3 and is marked minus (1 over the square root of 2), and the value 0 is marked over node 2. Figure c corresponds to lambda equals the square root of 2. Short vertical lines are drawn upward from node 1, 2, and 3 and are marked 0.5, 1 over the square root of 2, and 0.5, respectively. The lines from nodes 1 and 3 have the same magnitude, while that from node 2 is longer.

Figure 8.3. Eigenvectors of the adjacency matrix of a three-node path graph

Three figures showing the Eigenvectors of the Laplacian matrix of a three-node path graph.

The figures are placed one beside the other and are labeled alphabetically. The nodes are connected in the order 1, 2, and 3, in a horizontal series in all three figures. Figure a, corresponds to lambda equals 0. Short vertical lines of equal magnitude are drawn upward from the nodes and are marked 1 over the square root of 3. Figure b corresponds to lambda equals 1. A short vertical line is drawn upward from node 1 and is marked 1 over the square root of 2, a line of the equal length is drawn downward from the node 3 and is marked minus (1 over the square root of 2), and the value 0 is marked over node 2. Figure c corresponds to lambda equals 3. Short vertical lines are drawn upward from nodes 1 and 3 of equal magnitude and are marked 1 over the square root of 6; while a line of a slightly greater magnitude is drawn downward from the node 2 and is marked minus (2 over the square root of 6).

Figure 8.4. Eigenvectors of the Laplacian matrix of a three-node path graph

8.3 Adjacency Matrix Spectrum of a Graph

Adjacency matrix spectrum of a graph is the set of eigenvalues of the adjacency matrix of the graph. For an undirected graph, the adjacency matrix A is symmetric, and as a result, it constitutes N real eigenvalues. Let μ₀ ≤ μ₁ ≤ ... ≤ μ_N₋₁ be the eigenvalues of A. The sum of the absolute values of the eigenvalues of A is known as the graph energy. Some basic properties of the eigenvalues and eigenvectors of adjacency matrix for an undirected graph are as follows:

All the eigenvalues of the adjacency matrix are real.
The sum of the eigenvalues is zero, that is, $\sum_{i = 0}^{N - 1} μ_{i} = t r (𝐀) = 0$ $\sum_{i = 0}^{N - 1} μ_{i} = t r (?) = 0$ .
The sum of the square of the eigenvalue is equal to twice the number of edges present in the graph, that is, $\sum_{i = 0}^{N - 1} μ_{i}^{2} = 2 |ℰ|$ $\sum_{i = 0}^{N - 1} μ_{i}^{2} = 2 |ℰ|$ .
The geometric multiplicity and algebraic multiplicity are same for every eigenvalue.
As the adjacency matrix is nonnegative, it follows from Perron-Frobenius theorem that the eigenvalue with maximum absolute value (which is always positive) has a multiplicity of one, that is, it has a 1 × 1 size Jordan block. Moreover, the corresponding eigenvector will be non-negative. If the graph is connected, the largest eigenvalue has a multiplicity of one.
The eigenvectors form a complete set of orthogonal basis.

8.3.1 Bounds on the Eigenvalues

The largest eigenvalue μ_N₋₁ of the adjacency matrix A of a graph is bounded by

(8.3.1) $max [\bar{d}, \sqrt{d_{m a x}}] \leq μ_{N - 1} \leq d_{m a x},$ $max [\bar{d}, \sqrt{d_{m a x}}] \leq μ_{N - 1} \leq d_{m a x},$

where $\bar{d}$ $\bar{d}$ is the average degree, and d_max is the maximum degree of the graph.

Bounds Involving Chromatic Number

If $γ (𝒢)$ $γ (?)$ is the chromatic number of a graph $𝒢$ $?$ , then

(8.3.2) $γ (𝒢) \leq (1 + μ_{N - 1})$ $γ (?) \leq (1 + μ_{N - 1})$

and

(8.3.3) $γ (𝒢) \geq 1 - \frac{μ_{N - 1}}{μ_{0}},$ $γ (?) \geq 1 - \frac{μ_{N - 1}}{μ_{0}},$

where μ₀ and μ_N₋₁ are the smallest and the largest eigenvalues of the adjacency matrix A of the graph $𝒢$ $?$ , respectively.

8.3.2 Adjacency Matrix Spectra of Special Graphs

In this section, the adjacency matrix spectra of special graphs such as path graph, ring graph, star graph, complete graph, and bipartite graph are presented. Due to their special topological features, studying spectral properties of them can help one to identify and associate various spectal features and the associated topological characteristics. Definition of these graph types can be found in Chapter 2.

Path Graph

For a path graph with N vertices, the adjacency matrix has N distinct eigenvalues: $2 cos (\frac{π k}{N + 1})$ $2 cos (\frac{π k}{N + 1})$ , where k = 1, 2, . . . , N.

Cyclic (Ring) Graph

For a cyclic graph with N vertices, the adjacency matrix has N distinct eigenvalues: the complex n-th roots of unity, that is, $e^{\frac{2 π k j}{N}}$ $e^{\frac{2 π k j}{N}}$ , where k = 0, 1, . . . , N − 1.

Star Graph

For a star graph with N vertices, the adjacency matrix has three distinct eigenvalues: $- \sqrt{N - 1}$ $- \sqrt{N - 1}$ , 0 (with multiplicity N − 2), $\sqrt{N - 1}$ $\sqrt{N - 1}$ .

Complete Graph

For a complete graph with N nodes, the adjacency matrix has two distinct eigenvalues: −1 (with multiplicity N − 1) and N − 1.

Bipartite Graph

For a bipartite graph $𝒢$ $?$ , the spectrum of the adjacency matrix is symmetric about zero; that is, for each eigenvalue μ_i, the value −μ_i is also an eigenvalue of the graph $𝒢$ $?$ . An example bipartite graph is shown in Figure 8.5(a) and the corresponding adjacency matrix spectra is shown in Figure 8.5(b). Notice that the spectra is symmetric about zero eigenvalue.

Figure 8.5. A bipartite graph and its adjacency matrix spectra

Theorem 8.1. A graph $𝒢$ $?$ is bipartite if and only if its adjacency matrix spectrum is symmetric about 0.

Proof. If $𝒢$ $?$ is bipartite, then the adjacency matrix is of the form

$𝐀 = [\begin{matrix} 0 & 𝐁 \\ 𝐁^{T} & 0 \end{matrix}]$ $? = [\begin{matrix} 0 & ? \\ ?^{T} & 0 \end{matrix}]$

Now suppose that μ is an eigenvalue and $𝐯 = [\begin{matrix} 𝐚 \\ 𝐛 \end{matrix}]$ $? = [\begin{matrix} ? \\ ? \end{matrix}]$ is the corresponding eigenvector. Consequently, we have

$\begin{matrix} 𝐀 [\begin{matrix} 𝐚 \\ 𝐛 \end{matrix}] = μ [\begin{matrix} 𝐚 \\ 𝐛 \end{matrix}] & \Rightarrow [\begin{matrix} 0 & 𝐁 \\ 𝐁^{T} & 0 \end{matrix}] [\begin{matrix} 𝐚 \\ 𝐛 \end{matrix}] = μ [\begin{matrix} 𝐚 \\ 𝐛 \end{matrix}] \\ \Rightarrow 𝐁 𝐛 = μ 𝐚 a n d 𝐁^{T} 𝐚 = μ 𝐛 \end{matrix}$ $\begin{matrix} ? [\begin{matrix} ? \\ ? \end{matrix}] = μ [\begin{matrix} ? \\ ? \end{matrix}] & \Rightarrow [\begin{matrix} 0 & ? \\ ?^{T} & 0 \end{matrix}] [\begin{matrix} ? \\ ? \end{matrix}] = μ [\begin{matrix} ? \\ ? \end{matrix}] \\ \Rightarrow ? ? = μ ? a n d ?^{T} ? = μ ? \end{matrix}$

Now for a vector $𝐯' = [\begin{matrix} 𝐚 \\ - 𝐛 \end{matrix}]$ $?' = [\begin{matrix} ? \\ - ? \end{matrix}]$ , we have

$\begin{matrix} 𝐀 𝐯' = [\begin{matrix} 0 & 𝐁 \\ 𝐁^{T} & 0 \end{matrix}] [\begin{matrix} 𝐚 \\ - 𝐛 \end{matrix}] = [\begin{matrix} - 𝐁 𝐛 \\ 𝐁^{T} 𝐚 \end{matrix}] = [\begin{matrix} - μ 𝐚 \\ μ 𝐛 \end{matrix}] = - μ [\begin{matrix} 𝐚 \\ - 𝐛 \end{matrix}] = (- μ) 𝐯' . \end{matrix}$ $\begin{matrix} ? ?' = [\begin{matrix} 0 & ? \\ ?^{T} & 0 \end{matrix}] [\begin{matrix} ? \\ - ? \end{matrix}] = [\begin{matrix} - ? ? \\ ?^{T} ? \end{matrix}] = [\begin{matrix} - μ ? \\ μ ? \end{matrix}] = - μ [\begin{matrix} ? \\ - ? \end{matrix}] = (- μ) ?' . \end{matrix}$

Therefore, −μ is also an eigenvalue of A. To complete the proof, the converse also needs to be proved, which is left for the readers as an exercise.

Directed Ring Graph

For a directed cyclic graph with N vertices, the adjacency matrix has N distinct eigenvalues: $e^{\frac{- 2 π k j}{N}}$ $e^{\frac{- 2 π k j}{N}}$ , where k = 0, 1, . . . , N − 1.

A directed ring graph has special importance for us, because it is the graph corresponding to a discrete-time periodic signal. The eigendecomposition of the adjacency matrix of a directed ring graph provides the idea of graph Fourier transform (GFT), discussed in the next chapters. The eigenvectors of the adjacency matrix of a directed ring graph are same as the columns of the classical DFT matrix. The N × N DFT matrix is

(8.3.4) ${𝐃 𝐅 𝐓}_{N} = [\begin{matrix} 1 & 1 & 1 & 1 & \dots & 1 \\ 1 & e^{- \frac{2 π j}{N}} & e^{- \frac{2 π j}{N} 2} & e^{- \frac{2 π j}{N} 3} & \dots & e^{- \frac{2 π j}{N} (N - 1)} \\ 1 & e^{- \frac{2 π j}{N} 2} & e^{- \frac{2 π j}{N} 4} & e^{- \frac{2 π j}{N} 6} & e^{- \frac{2 π j}{N} 2 (N - 1)} \\ 1 & e^{- \frac{2 π j}{N} 3} & e^{- \frac{2 π j}{N} 6} & e^{- \frac{2 π j}{N} 9} & e^{- \frac{2 π j}{N} 3 (N - 1)} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 1 & e^{- \frac{2 π j}{N} (N - 1)} & e^{- \frac{2 π j}{N} 2 (N - 1)} & e^{- \frac{2 π j}{N} 3 (N - 1)} & \dots & e^{- \frac{2 π j}{N} (N - 1) (N - 1)} \end{matrix}] .$ ${? ? ?}_{N} = [\begin{matrix} 1 & 1 & 1 & 1 & \dots & 1 \\ 1 & e^{- \frac{2 π j}{N}} & e^{- \frac{2 π j}{N} 2} & e^{- \frac{2 π j}{N} 3} & \dots & e^{- \frac{2 π j}{N} (N - 1)} \\ 1 & e^{- \frac{2 π j}{N} 2} & e^{- \frac{2 π j}{N} 4} & e^{- \frac{2 π j}{N} 6} & e^{- \frac{2 π j}{N} 2 (N - 1)} \\ 1 & e^{- \frac{2 π j}{N} 3} & e^{- \frac{2 π j}{N} 6} & e^{- \frac{2 π j}{N} 9} & e^{- \frac{2 π j}{N} 3 (N - 1)} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 1 & e^{- \frac{2 π j}{N} (N - 1)} & e^{- \frac{2 π j}{N} 2 (N - 1)} & e^{- \frac{2 π j}{N} 3 (N - 1)} & \dots & e^{- \frac{2 π j}{N} (N - 1) (N - 1)} \end{matrix}] .$

The adjacency matrix of an N-node directed ring graph can be diagonalized as

(8.3.5) $𝐀 = {𝐃 𝐅 𝐓}_{N}^{- 1} [\begin{matrix} e^{- \frac{2 π .0}{N} j} \\ e^{- \frac{2 π .1}{N} j} \\ ⋱ \\ e^{- \frac{2 π . (N - 1)}{N} j} \end{matrix}] {𝐃 𝐅 𝐓}_{N} .$ $? = {? ? ?}_{N}^{- 1} [\begin{matrix} e^{- \frac{2 π .0}{N} j} \\ e^{- \frac{2 π .1}{N} j} \\ ⋱ \\ e^{- \frac{2 π . (N - 1)}{N} j} \end{matrix}] {? ? ?}_{N} .$

Figure 8.6 shows a directed ring graph and its adjacency matrix. The eigenvalues of the adjacency matrix are 1, 0.31 − 0.95j, −0.81 − 0.59j, −0.81 + 0.59j, and 0.31 − 0.95j. For the five-node directed ring graph, observe that

Two figures showing a directed graph and its corresponding adjacency matrix.

Figure 8.6. A directed ring graph and its adjacency matrix

(8.3.6) $\begin{matrix} 𝐀 & = [\begin{matrix} 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \end{matrix}] \\ = {𝐃 𝐅 𝐓}_{5}^{- 1} [\begin{matrix} 1 & 0 & 0 & 0 & 0 \\ 0.31 - 0.95 j & 0 & 0 & 0 \\ 0 & - 0.81 - 0.59 j & 0 \\ 0 & 0 & - 0.81 + 0.59 j & 0 \\ 0 & 0 & 0 & 0.31 + 0.95 j \end{matrix}] {𝐃 𝐅 𝐓}_{5}, \end{matrix}$ $\begin{matrix} ? & = [\begin{matrix} 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \end{matrix}] \\ = {? ? ?}_{5}^{- 1} [\begin{matrix} 1 & 0 & 0 & 0 & 0 \\ 0.31 - 0.95 j & 0 & 0 & 0 \\ 0 & - 0.81 - 0.59 j & 0 \\ 0 & 0 & - 0.81 + 0.59 j & 0 \\ 0 & 0 & 0 & 0.31 + 0.95 j \end{matrix}] {? ? ?}_{5}, \end{matrix}$

where

${𝐃 𝐅 𝐓}_{5} = [\begin{matrix} 1 & 1 & 1 & 1 & 1 \\ 1 & 0.31 - 0.95 j & - 0.81 - 0.59 j & - 0.81 + 0.58 j & 0.31 + 0.95 j \\ 1 & - 0.81 - 0.59 j & 0.31 + 0.95 j & 0.31 - 0.95 j & - 0.81 + 0.59 j \\ 1 & - 0.81 + 0.59 j & 0.31 - 0.95 j & 0.31 + 0.95 j & - 0.81 - 0.59 j \\ 1 & 0.31 + 0.95 j & - 0.81 + 0.59 j & - 0.81 - 0.59 j & 0.31 - 0.95 j \end{matrix}] .$ ${? ? ?}_{5} = [\begin{matrix} 1 & 1 & 1 & 1 & 1 \\ 1 & 0.31 - 0.95 j & - 0.81 - 0.59 j & - 0.81 + 0.58 j & 0.31 + 0.95 j \\ 1 & - 0.81 - 0.59 j & 0.31 + 0.95 j & 0.31 - 0.95 j & - 0.81 + 0.59 j \\ 1 & - 0.81 + 0.59 j & 0.31 - 0.95 j & 0.31 + 0.95 j & - 0.81 - 0.59 j \\ 1 & 0.31 + 0.95 j & - 0.81 + 0.59 j & - 0.81 - 0.59 j & 0.31 - 0.95 j \end{matrix}] .$

Note that the diagonal entries in the diagonal matrix in Equation (8.3.6) are nothing but the eigenvalues of the adjacency matrix of the five-node ring graph. The eigenvalues of the adjacency matrix of a directed ring graph are the discrete frequencies corresponding to the DFT. Moreover, we will see in Chapter 10 that the eigenvectors of the weight matrix (adjacency matrix for unweighted graph) can be used to define the GFT.

8.4 Adjacency Matrix Spectra of Complex Networks

As discussed in Section 8.1, for large networks having more than a few thousand nodes, the numerical calculation of the spectra (eigenvalues) consumes significant time and memory. For such networks, spectral characterization is made using spectral density (distribution) function. The most straightforward way to obtain this density is to compute all eigenvalues of the matrix; however, this approach is generally costly and wasteful for large networks. There exist alternative approaches [145] that allow us to estimate the spectral density function at much lower cost. Discussion of these methods is out of scope of this book.

The spectral density of adjacency matrix of a network reveals its topological features. The adjacency matrix for an undirected network is symmetric and, therefore, its all the eigenvalues are real. One can also view the spectral density as a probability density distribution that measures the likelihood of finding eigenvalues near some point on the real line.

The ER model of random networks generates an uncorrelated graph because the presence or absence of an edge between two vertices is independent of the presence or absence of any other edge, so that each edge may be considered to be present with independent probability. For such uncorrelated random networks, from Wigner’s law [146], [147], [148], the spectral density can be approximated by a semicircular function. However, most of the real-world networks are correlated and are modeled as small-world or scale-free networks (Chapters 4 and 5). Small-world networks have a complex spectral density consisting of several sharp peaks, and scale-free networks constitute a triangle-like spectral density with a power-law tail [140], [139], [141]. Therefore, considering the pattern of the spectral density function, one can classify a network. Moreover, various structural properties can also be extracted from the spectral density function of a network. Now, we will discuss spectral density of each network type in detail.

8.4.1 Random Networks

As discussed in Appendix A.7, for an N × N uncorrelated random symmetric matrix M with (i) mean of each entry (which is a random variable) is zero (E[m_ij] = 0), (ii) variance of the non-diagonal entries is σ² ( $E [m_{i j}^{2}] = σ^{2}$ $E [m_{i j}^{2}] = σ^{2}$ ) and has finite higher order moments, then if N → ∞, the spectral density of M follows a semicircular distribution given as

(8.4.1) $ρ (λ) = {\begin{matrix} \frac{\sqrt{4 N σ^{2} - λ^{2}}}{2 π N σ^{2}} & if |λ| < 2 \sqrt{N} σ \\ 0 & otherwise . \end{matrix}$ $ρ (λ) = {\begin{matrix} \frac{\sqrt{4 N σ^{2} - λ^{2}}}{2 π N σ^{2}} & if |λ| < 2 \sqrt{N} σ \\ 0 & otherwise . \end{matrix}$

The above result is known as Wigner’s law.

Wigner’s law is used to characterize the spectral density of ER random networks. For an ER random network with no self-loops, each non-diagonal entry of its adjacency matrix a_ij, for i ≠ j, is a bi-valued discrete random variable (0 with a probability (1 − p) and 1 with a probability p). Therefore, mean of the entry a_ij is given by

(8.4.2) $\begin{matrix} m & = E [a_{i j}] = 0 (probability that a_{i j} is zero) + 1 (probability that a_{i j} is 1) \\ = 0 (1 - p) + 1 (p) = p, \end{matrix}$ $\begin{matrix} m & = E [a_{i j}] = 0 (probability that a_{i j} is zero) + 1 (probability that a_{i j} is 1) \\ = 0 (1 - p) + 1 (p) = p, \end{matrix}$

and the variance is

(8.4.3) $σ^{2} = E [(a_{i j} - E [a_{i j}])^{2}] = (0 - p)^{2} (1 - p) + (1 - p)^{2} (p) = p (1 - p) .$ $σ^{2} = E [(a_{i j} - E [a_{i j}])^{2}] = (0 - p)^{2} (1 - p) + (1 - p)^{2} (p) = p (1 - p) .$

Observe that mean of an off-diagonal entry of the adjacency matrix is non-zero and, therefore, the condition of Wigner’s law is violated. However, for a positive mean, the spectral density follows semicircular distribution when properly rescaled [138], [140]. Only the largest eigenvalue μ_N−1 is isolated from the bulk of the eigenvalues and has a normal distribution with mean (N − 1)m + σ²/m = (N − 1)p + p (p − 1)/p = N_p and variance 2σ² = 2p(p − 1) [138].

Figure 8.7 shows the spectral density of a 1000-node random network generated using the ER model with edge probability of 0.1. The spectral distribution shown in the figure is averaged over 100 experiments. The plot is a histogram plot with 100 bins. In the plot, apart from the semicircular bulk, one can also observe a small peak which is separated from the bulk of eigenvalues.

A graph showing the spectral density of a 1000-node random network generated using the ER model.

Figure 8.7. Spectral distribution of a 1000-node ER network (p = 0.1) averaged over 100 experiments. The number of bins is 100.

8.4.2 Random Regular Networks

Here we discuss the distribution of eigenvalues of an N-node random d-regular graph, chosen uniformly at random from all d-regular graphs with N nodes. If d is fixed and N approaches infinity, then spectral density has a form

(8.4.4) $ρ (λ) = {\begin{matrix} \frac{d \sqrt{4 (d - 1) - λ^{2}}}{2 π (d^{2} - λ^{2})} & if λ < 2 \sqrt{d - 1} \\ 0 & otherwise . \end{matrix}$ $ρ (λ) = {\begin{matrix} \frac{d \sqrt{4 (d - 1) - λ^{2}}}{2 π (d^{2} - λ^{2})} & if λ < 2 \sqrt{d - 1} \\ 0 & otherwise . \end{matrix}$

The above distribution is known as McKay law [149]. Figure 8.8 shows empirical spectral distributions of random d-regular graphs for various values of d.

Four graphs showing the spectral distribution of d-regular networks when d equals 2, 3, 6, and 30.

The graphs are placed two in a row and are labeled alphabetically. All graphs are marked with lambda along the horizontal axis. Figure a shows the Spectral distribution when d equals 2. The horizontal axis ranges from -3 to 3 in increments of 1 and the vertical axis ranges from 0 to 0.05 in increments of 0.01. The graph here is a large U with an elongated base, passing through the following points: (-2, 0.045), (-2, 0.01), (-1.5, 0.06), (0, 0.005), (1.5, 0.06), (2, 0.01), and (2, 0.45). Figure b shows the Spectral distribution when d equals 3. The horizontal axis ranges from -3 to 3 in increments of 1 and the vertical axis ranges from 0 to 0.015 in increments of 0.005. The graph is plotted in the shape of the letter M, through the following points: (-3, 0.002), (-3.5, 0.015), (-2, 0.009), (-1, 0.005), (0, 0.01), (1, 0.005), (2, 0.009), (3.5, 0.015), and (3, 0.002). Figure c shows the Spectral distribution when d equals 6. The horizontal axis ranges from -6 to 8 in increments of 2 and the vertical axis ranges from 0 to 0.015 in increments of 0.005. The graph is plotted in the shape of an inverted U, with an elongated base across the following points: (-5.8, 0.002), (-4, 0.005), (-2, 0.75), (0, 0.75), (2, 0.75), (4, 0.75), (4.2, 0), (6, 0.02). Figure d shows the Spectral distribution when d equals 30. The horizontal axis ranges from -20 to 40 in increments of 10 and the vertical axis ranges from 0 to 0.005 in increments of 0.005. The graph is plotted in the shape of an inverted U across the following points: (-10, 0.002), (0, 0.025), and (-10, 0), followed by a straight line through (20, 0), and (30, 0). All graphs except the first run along the horizontal axis toward the end and have a small peak at the very end. All points are only approximate.

Figure 8.8. Spectral distribution of random d-regular networks with various values of d. Network size is 1000 nodes, and the distribution is averaged over 100 experiments. The number of bins is 100.

Further, it was proved that for d → ∞ and d ≤ N/2, the spectral distribution of a random d-regular graph follows semicircle law [150]. However, it is important to note that the semicircular distribution is achieved for even sufficiently large values of d. Figure 8.8(d) shows spectral distribution for d = 30. The semicircular spectral distribution is evident from the figure.

8.4.3 Small-World Networks

The adjacency matrix spectra of small-world networks contain multiple sharp peaks. In the Watts-Strogatz (WS) model or rewiring model of small-world networks, existing normal links (NLs) of a k-regular network are rewired to other nodes in the network based on a certain probability p_r, where 0 ≤ p_r ≤ 1 [6]. Details of the rewiring model can be found in Section 4.5.1. As the number of rewired links increases, small-worldness of the network also increases and the network tends to become random. With the increase in the rewiring probability, the sharp peaks in the spectral distribution become blurred and the spectral distribution tends to semicircular distribution.

For zero rewiring probability p_r = 0, the small-world graph is regular and also periodical as each vertex is connected to its k-nearest neighboring vertices. Because of this highly ordered structure the spectra contains numerous singularities. The spectral distribution of such a network is plotted in Figure 8.9(a). In the figure, the network considered is 20-regular and has a total of 1000 nodes. One can observe several sharp peaks in the spectral distribution for p_r = 0.

Eight graphs illustrating the spectral distribution of small-world networks with various rewiring probabilities.

The graphs are placed side-by-side, two in a row, and are labeled alphabetically. The horizontal axis is marked with lambda values in all graphs. Graph a pertains to rho subscript r equals 0. The horizontal axis ranges from -4 to 10 in increments of 2, and the vertical axis ranges from 0 to 0.07 in increments of 0.01. A pulse graph is generated through the following points: (-3, 0.035), (-2, 0.01), (-2, 0.069), (-1, 0.02), (0, 0.025), (0.2, 0.05), (0.4, 0.045), (0.06, 0.002), (2, 0.001), (4, 0.001), (5, 0.002), (6, 0.002), and (8, 0.01). Graph b pertains to when rho subscript r equals 0.01. The horizontal axis ranges from -4 to 10 in increments of 2, and the vertical axis ranges from 0 to 0.05 in increments of 0.01. A pulse graph is generated through the following points: (-3.8, 0), (-3, 0.025), (-2.8, 0.018), (-2, 0.049), (-1, 0.035), (0, 0.045), (0.2, 0.045), (0.04, 0.009), (2, 0.002), (4, 0.002), (6, 0.002), and (8, 0.01). Graph c pertains to when rho subscript r equals 0.04. The horizontal axis ranges from -5 to 10 in increments of 5, and the vertical axis ranges from 0 to 0.035 in increments of 0.005. A graph is generated through the following points: (-4, 0), (-3.5, 0.02), (-2, 0.03), (-1, 0.025), (0, 0.03), (2, 0.015), (3, 0.004), (5, 0.005), (7.5, 0.01), and (8, 0.002). In graph d that pertains to when rho subscript r equals 0.1. The horizontal axis ranges from -5 to 10 in increments of 5, and the vertical axis ranges from 0 to 0.03 in increments of 0.005. A graph is generated rises from (-4, 0) to (-2, 0.025), and has a small peak at (-1, 0.025). The curve the declines from (0, 0.024) up to (3.5, 0.005). It then goes through (5, 0.005), (7, 0.007), (7.5, 0), and (7.8, 0.002). Graph e pertains to when rho subscript r equals 0.2. The horizontal axis ranges from -5 to 10 in increments of 5, and the vertical axis ranges from 0 to 0.025 in increments of 0.005. A graph is generated through the following points: it begins at (-5, 0), raises to reach its maximum peak at (-2, 0.02), gradually falls to (3, 0.003), raises again to reach a peak at (6, 0.005), and finally falls to (-5, 0). Graph f pertains to when rho subscript r equals 0.5. The horizontal axis ranges from -6 to 10 in increments of 2, and the vertical axis ranges from 0 to 0.02 in increments of 0.005. A graph is generated through the following points: it begins at (-6, 0), raises to reach its maximum peak at (0, 0.017), gradually falls to (4, 0.007), proceeds through (6, 0.006), the falls to (6.2, 0), and runs along the horizontal axis until (8, 0) where it rises slightly. Graph g pertains to when rho subscript r equals 0.8. The horizontal axis ranges from -6 to 10 in increments of 2, and the vertical axis ranges from 0 to 0.02 in increments of 0.005. A graph is generated through the following points: it begins at (-6, 0), raises to reach its maximum peak at (0, 0.018), gradually falls to (4, 0), and runs along the horizontal axis until (8.5, 0) where it rises slightly. Graph h pertains to when rho subscript r equals 1. The horizontal axis ranges from -15 to 25 in increments of 5, and the vertical axis ranges from 0 to 0.025 in increments of 0.005. A graph is generated through the following points: it begins at (-10, 0), raises to reach its maximum peak at (0, 0.024), gradually falls to (10, 0), and runs along the horizontal axis until (20, 0) where it rises slightly. All points are only approximate.

Figure 8.9. Spectral distribution of small-world networks with various rewiring probabilities p_r. Small-world graph is generated using the Watts-Strogatz model starting with a 20-regular graph. Network size is 1000 nodes and the distribution is averaged over 100 experiments. The number of bins is 100.

When the rewiring probability is increased, the regularity of the network decreases and, therefore, the singularities are blurred and the spectal distribution tends to become smoother. The blurring of singularities with increase in rewiring probability can be observed from Figure 8.9(b–h). When the rewiring probability p_r = 1, the network follows semicircular distribution, as shown in Figure 8.9(h). This is because for p_r = 1, each link of the regular network is rewired and the network becomes completely random.

8.4.4 Scale-Free Networks

The adjacency matrix spectra of scale-free networks does not follow semicircle law. Consider the Barabási-Albert (BA) model of scale-free networks. According to the BA model of network generation, at time t = 0, there are m₀ nodes present in the network. At each time instant, t, a new node is introduced to the network and m links are then connected to the existing network. The details of the BA model can be found in Section 5.5. Spectral distributions for scale-free networks, generated using the BA model, is shown in Figure 8.10. For each case, the network size is 1000 and the distribution is averaged over 100 experiments. In general, bulk of the spectral distribution has triangular shape for each case. Moreover, it constitutes power-law tails. For small values of m₀, there is a sharp peak at zero eigenvalue. As the value of m₀ increases, the sharpness of the peak decreases. It is important to note that both sides of the spectrum show long tails due to the slow decay of power law.

Three graphs illustrating the spectral distribution of scale-free networks generated using the BA model.

The graphs are labeled alphabetically, with varying m subscript 0 values. The horizontal axis is marked with lambda values in all three graphs. Graph a pertains to when m subscript 0 equals 3 and m equals 5. The horizontal axis is plotted with values from -15 to 15 in increments of 5, while the vertical axis is plotted with values from 0 to 0.1 in increments of 0.02. The graph begins at (-13, 0), runs along the horizontal axis up to (-7, 0) where it begins curving up to reach (-2, 0.04). From here it reaches a peak at (0, 0.08) and again falls to (2, 0.04). From here it curves down to reach the point (7, 0) and runs along the horizontal axis up to (15, 0). Graph b corresponds to when m subscript 0 equals 4 and m equals 5. The horizontal axis is plotted with values from -15 to 20 in increments of 5, while the vertical axis is plotted with values from 0 to 0.07 in increments of 0.01. The graph begins at (-13, 0), runs along the horizontal axis up to (-7, 0) where it begins curving up to reach (-2, 0.04). From here it reaches a peak at (0, 0.06) and again falls to (2, 0.04). From here it curves down to reach the point (7, 0) and runs along the horizontal axis up to (18, 0). Graph c corresponds to when m subscript 0 equals 5 and m equals 5. The horizontal axis is plotted with values from -15 to 25 in increments of 5, while the vertical axis is plotted with values from 0 to 0.06 in increments of 0.01. The graph begins at (-13, 0), runs along the horizontal axis up to (-7, 0) where it begins curving up to reach (-2, 0.04). From here it reaches a peak at (0, 0.055) and again falls to (2, 0.04). From here it curves down to reach the point (7, 0) and runs along the horizontal axis up to (22, 0). The difference between the paths of the graphs is that the degree of curvature before tracing their respective peak points decreases through the graphs. All co-ordinate plots are only approximate.

Figure 8.10. Spectral distribution of scale-free networks generated using the BA model. Network size is 1000 nodes and the distribution is averaged over 100 experiments. The number of bins is 100.

8.5 Laplacian Spectrum of a Graph

Spectrum of the Laplacian matrix of a graph is used in several applications of complex network analysis. A large number of the topological properties of a graph can be inferred from the spectrum of its graph Laplacian. For example, the eigenvalues and eigenvectors of the graph Laplacian allow frequency analysis of complex network data (detailed discussion on this topic is provided in the subsequent chapters). The Laplacian spectrum has also been used for measuring difference (or similarity) between networks. Moreover, the spectrum of the Laplacian can be used to detect community structures in a complex network [48]. Therefore, it is valuable to study the properties of the eigenvalues and eigenvectors of the graph Laplacian. The eigenvalues of the Laplacian matrix L are represented as λ₀, λ₁,... , λ_N₋₁ and the correspnding eigenvectors as u₀, u₁,... , u_N₋₁, respectively. It is assumed that λ₀ ≤ λ₁ ≤ ... ≤ λ_N₋₁.

Some basic properties of the eigenvalues and eigenvectors of the adjacency matrix for an undirected graph are as follows.

All the eigenvalues of the Laplacian matrix are real and nonnegative.
It always has a zero eigenvalue.
If a graph is not connected, then the spectrum consists of the union of the eigenvalues of the connected components.

Proposition 8.1. For a connected graph, λ₀ = 0 and the corresponding eigenvector is constant over all the nodes of the graph.

Proof. From the definition of the Laplacian, the sum of each row is zero and, therefore,

L1 = 0 = 0(1),

where 1 is an N-dimensional vector, having all entries as unity and 0 is the zero vector. From the above argument, we can say that the eigenvector corresponding to zero eigenvalue is u₀ = 1.

Proposition 8.2. For a connected graph with N vertices, ∑_j u_i(j) = 0, for all i = 1, 2, . . . , N − 1, where u_i is the eigenvector corresponding to the eignevalue λ_i of the graph Laplacian L.

Proof. The Laplacian matrix of a graph is symmetric, and as a result, the eigenvectors are orthogonal. For an eigenvector u_i to be orthogonal to u₀ = 1, 〈u_i, u₀〉 = 0. For this to be true, it follows that ∑_j u_i(j) = 0, for all i = 1, 2, . . . , N − 1.

8.5.1 Bounds on the Eigenvalues of the Laplacian

We present a few important upper and lower bounds on the largest and smallest eigenvalues of the graph Laplacian. These bounds are very useful in characterizing the structure of a graph.

The second-smallest eigenvalue λ₁ of the graph Laplacian L is upper-bounded by

(8.5.1) $λ_{1} \leq N .$ $λ_{1} \leq N .$

In the above bound, the equality holds if the graph is complete. Moreover, from Gershgorin’s theorem (see Appendix A.8), the upper bound on the largest eigenvalue can be found to be

(8.5.2) $λ_{N - 1} \leq 2 d_{m a x},$ $λ_{N - 1} \leq 2 d_{m a x},$

where d_max is the maximum degree of the graph. The above upper bound on the largest eigenvalue was improved in [151] as

(8.5.3) $λ_{N - 1} \leq max {d_{i} + d_{j} (i, j) \in ℰ},$ $λ_{N - 1} \leq max {d_{i} + d_{j} (i, j) \in ℰ},$

where d_i represents degree of node i.

Bounds Involving Vertex and Edge Connectivity

For a non-complete N-node graph $𝒢$ $?$ , λ₁ is upper-bounded by

(8.5.4) $λ_{1} \leq v (𝒢) \leq e (𝒢),$ $λ_{1} \leq v (?) \leq e (?),$

where $v (𝒢)$ $v (?)$ and $e (𝒢)$ $e (?)$ are vertex and edge connectivities of the graph, respectively [152].

Moreover, λ₁ is lower-bounded by

(8.5.5) $λ_{1} \geq e (𝒢) 2 (1 - c o s (\frac{π}{N})) .$ $λ_{1} \geq e (?) 2 (1 - c o s (\frac{π}{N})) .$

Note that $λ_{1} = 2 (1 - c o s (\frac{π}{N}))$ $λ_{1} = 2 (1 - c o s (\frac{π}{N}))$ for an N-node path graph. Because $e (𝒢) \geq 1$ $e (?) \geq 1$ for a connected graph, we can interpret from the above inequality that among connected graphs, λ₁ is minimum for a path graph. As connectivity of a graph increases, λ₁ also increases. Therefore, λ₁ contains information regarding connectivity of a graph. More about this topic is discussed later in this chapter.

Bounds Involving Max-Cut Problem

For a graph $𝒢$ $?$ with N nodes, maximum cut of $𝒢$ $?$ , mc( $𝒢$ $?$ ), is bounded by

(8.5.6) $m c (𝒢) \leq \frac{1}{4} λ_{N - 1} N,$ $m c (?) \leq \frac{1}{4} λ_{N - 1} N,$

where λ_N₋₁ is the largest eigenvalue of the graph Laplacian [153]. Calculating max-cut of a graph is NP-hard and, therefore, the above bound is very helpful.

8.5.2 Bounds on the Eigenvalues of the Normalized Laplacian

The second smallest eigenvalue λ₁ and the largest eigenvalue λ_N₋₁ of the normalized Laplacian L^norm of a connected graph $𝒢$ $?$ with N vertices are bounded by the following inequalities:

(8.5.7) $λ_{1} \leq \frac{N}{N - 1}$ $λ_{1} \leq \frac{N}{N - 1}$

and

(8.5.8) $λ_{N - 1} \geq \frac{N}{N - 1} .$ $λ_{N - 1} \geq \frac{N}{N - 1} .$

If a graph is not complete, then λ₁ ≤ 1. Moreover, for every graph, λ_N₋₁ ≤ 2. For bipartite graphs, λ_N₋₁ = 2.

Bounds Involving Diameter

The diameter $D (𝒢)$ $D (?)$ of a graph $𝒢$ $?$ is upper-bounded by

(8.5.9) $D (𝒢) \leq ⌈ \frac{log (N - 1)}{log (\frac{λ_{N - 1} + λ_{1}}{λ_{N - 1} - λ_{1}})} ⌉,$ $D (?) \leq ⌈ \frac{log (N - 1)}{log (\frac{λ_{N - 1} + λ_{1}}{λ_{N - 1} - λ_{1}})} ⌉,$

where ⌈.⌉ represents the ceiling function. The diameter of a graph is an important structural parameter: for example, it is useful in estimation of maximum delay in a communication network. Knowing the Laplacian spectrum of the network, one can find out the upper bound on the graph diameter.

Bound Involving Cheeger Constant: Cheeger Inequality

For a connected graph $𝒢$ $?$ , the second smallest eigenvalue λ₁ of the normalized graph Laplacian is bounded by the following:

(8.5.10) $2 h_{𝒢} \geq λ_{1} > \frac{h_{𝒢}^{2}}{2},$ $2 h_{?} \geq λ_{1} > \frac{h_{?}^{2}}{2},$

where $h_{𝒢}$ $h_{?}$ is the Cheeger constant (refer to Section 2.7.1) of the graph. Moreover, an improved lower bound is given as $λ_{1} > 1 - \sqrt{1 - h_{𝒢}^{2}}$ $λ_{1} > 1 - \sqrt{1 - h_{?}^{2}}$ .

8.5.3 Matrix Tree Theorem

A spanning tree of a graph is a subgraph that is a tree consisting of all the vertices of the graph. Using the spectrum of the Laplacian of a connected graph, the number of spanning trees can be calculated. This is given by matrix-tree theorem, which is stated as follows.

Theorem 8.2. For a connected graph $𝒢$ $?$ with N nodes, the number of spanning trees is given by

$\frac{λ_{1} λ_{2} \dots λ_{N - 1}}{N},$ $\frac{λ_{1} λ_{2} \dots λ_{N - 1}}{N},$

where 0 = λ₀ ≤ λ₁ ≤ ... ≤ λ_N₋₁ are the eigenvalues of the Laplacian matrix L of the graph.

8.5.4 Laplacian Spectrum and Graph Connectivity

A graph is connected; that is, a path can always be found connecting one vertex to the other if and only if the smallest eigenvalue λ₀ = 0 has multiplicity one. Moreover, the second smallest Laplacian eigenvalue λ₁ of a graph is also important information contained in the spectrum of a graph. It is also known as spectral gap or algebraic connectivity [152] of the graph. The eigenvector corresponding to the algebraic connectivity is also known as the Fiedler vector. The value of λ₁ is related to the connectedness of a graph: large values of λ₁ are associated with graphs that are hard to disconnect. Moreover, the algebraic connectivity is non-decreasing; that is, adding more edges to the graph does not decrease the algebraic connectivity (see Exercise problem 4).

Community Detection Using Spectral Bisection

The eigenvalues and eigenvectors of the Laplacian can be used to detect communities in a network. The eigenvector corresponding to the second smallest eigenvalue, the Fiedler vector, bisects the graph into two communities based on the sign of the corresponding entry in the eigenvector. To divide a network into a large number of communities, one can use repeated bisection.

Consider a network that can be perfectly separated into k number of communities; that is, the edges exist only within communities and no edges exist between communities. For such networks, the Laplacian will be block-diagonal as follows:

(8.5.11) $𝐋 = [\begin{matrix} 𝐋_{1} \\ 𝐋_{2} \\ ⋱ \\ 𝐋_{k} \end{matrix}]$ $? = [\begin{matrix} ?_{1} \\ ?_{2} \\ ⋱ \\ ?_{k} \end{matrix}]$

Each diagonal block will form the Laplacian of its own component and, therefore, zero eigenvalue has a multiplicity of k. For example, consider a network shown in Figure 8.11. The network consists of two perfectly separating communities. The

A figure showing a network with two separate communities.

Figure 8.11. A network with two communities

Laplacian of the network has zero eigenvalue with a multiplicity of 2, and the corresponding degenerate eigenvectors are

(8.5.12) $𝐮_{0}^{(1)} = [\begin{matrix} 1 \\ 1 \\ 1 \\ 1 \\ 0 \\ 0 \\ 0 \end{matrix}], 𝐮_{0}^{(2)} = [\begin{matrix} 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 1 \end{matrix}] .$ $?_{0}^{(1)} = [\begin{matrix} 1 \\ 1 \\ 1 \\ 1 \\ 0 \\ 0 \\ 0 \end{matrix}], ?_{0}^{(2)} = [\begin{matrix} 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 1 \end{matrix}] .$

Observe the non-zero entries in the degenerate eigenvectors: the vertices corresponding to non-zero entries in each degenerate eigenvector form a community.

Now consider a case when the network does not separate perfectly into communities; that is, few edges exist between communities. In such networks, the Laplacian no longer remains block-diagonal and k − 1 eigenvalues are slightly greater than zero. Moreover, the second smallest eigenvalue λ₁ can be used to measure the goodness of the split: smaller values correspond to better splits.

Let us consider a simpler case of bisection: there are only two communities in the network, but they are not well separated. Figure 8.12 shows two such networks. The second network (Figure 8.12(b)) has more intra-community edges than the first network (Figure 8.12(a)). Therefore, λ₁ for the second network is more than that of the first network. The corresponding eigenvectors are

A figure showing a network with two separate communities and edges being added to connect them.

The figures are placed one beside the other and are labeled alphabetically. Both figures have the following network of communities. The first community is enclosed within a dashed circle and has four nodes, numbered from 1 to 4. The following bi-directional connections are made: 1 to 2, 3, and 4; and 2 to 3 and 4. The second community that is placed to the right of the first, is enclosed within another dashed circle and has three nodes, numbered from 5 to 7. The following bi-directional connections are made: 5 to 6 and 7. Figure a corresponds to when lambda 1 equals 0.3983 and lambda max equals 5.2618. Here the nodes 2 and 5 are connected by a bi-directional link. Figure b corresponds to when lambda 1 equals 1.1887 and lambda max equals 6.1518. Here the following nodes are connected bi-directionally: 2 and 5, 2 and 6, and 3 and 7.

Figure 8.12. Addition of edges between communities in a network

(8.5.13) $𝐮_{1} = [\begin{matrix} 0.3560 \\ 0.2142 \\ 0.3560 \\ 0.3560 \\ - 0.2966 \\ - 0.4929 \\ - 0.4929 \end{matrix}] and 𝐮_{1} = [\begin{matrix} 0.4112 \\ 0.0855 \\ 0.0472 \\ 0.6122 \\ - 0.3808 \\ - 0.3640 \\ - 0.4112 \end{matrix}],$ $?_{1} = [\begin{matrix} 0.3560 \\ 0.2142 \\ 0.3560 \\ 0.3560 \\ - 0.2966 \\ - 0.4929 \\ - 0.4929 \end{matrix}] and ?_{1} = [\begin{matrix} 0.4112 \\ 0.0855 \\ 0.0472 \\ 0.6122 \\ - 0.3808 \\ - 0.3640 \\ - 0.4112 \end{matrix}],$

respectively. Looking at the signs of the eigenvector entries for both of the networks, one can easily bisect the networks.

Although the spectral bisection method is fast, the main disadvantage is that it is limited to only bisection of a network. Division into a larger number of communities can be achieved by repeated bisection; however, this may not give satisfactory results. Moreover, in general, the number of communities is not known beforehand.

8.5.5 Spectral Graph Clustering

The eigenvectors of the graph Laplacian can also be utilized for clustering of graph nodes, and the method is polularly known as spectral graph clustering [154], [155]. Spectral clustering is one of the most popular modern clustering algorithms used by machine learning community. It has been extensively used for clustering of data points by creating a similarity graph from the data points and then utilizing the eigenvectors of the Laplacian matrix of the similarity graph. Spectral clustering outperforms traditional clustering algorithm such as k-means algorithm. In the field of complex networks, spectral graph clustering can be used for community detection.

Depending on which form of the graph Laplacian (unnormalized or normalized) is used, there exist multiple versions of the spectral clustering algorithms. Algorithm 8.1 describes spectral graph clustering that uses the unnormalized graph Laplacian L = D − W of a graph. Suppose we want to divide a graph into k number of clusters. For this purpose, first k eigenvectors of the graph Laplacian are computed to form the matrix U_k ∈ ℝ^N×k in which the eigenvectors are stacked as columns. Considering each row of U_k as a point in ℝ^k, these N points are divided into k number of clusters using k-means or any other clustering algorithm. Thus, the algorithm outputs k number of clusters.

Consider the graph shown shown in Figure 8.13 that has to be clustered into four clusters (the set of nodes inside a circle belongs to a cluster). The first four eigenvectors of the graph Laplacian are plotted in Figure 8.14. These eigenvectors can be stacked in a matrix U_k = [u₀, u₁, u₂, u₃] ∈ ℝ¹⁴×4. Each of the 14 rows in _k, z_i ∈ ℝ⁴, is treated as a point, and all 14 points are clustered into four clusters using k-means algorithm. The resulting clusters are the same as shown in Figure 8.13 using circles. A closer look at the plots of eigenvectors explains the working of the spectral graph clustering algorithm. Observe the signs (positive or negative) of the eigenvectors at each node. The signs of u₁ (see Figure 8.14(b)) clearly divide the graph into two parts: nodes 1 through 4 and the rest. Next, the eigenvector u₂, as shown in Figure 8.14(c), divides the rest of the nodes into two parts and identifies nodes 11 through 14 as one cluster based on their signs. Using u₁ and u₂, we could identify two clusters: nodes 1 through 4 and nodes 11 through 14. Finally, the signs of the eigenvector u₃, as shown in Figure 8.14(d), at the remaining nodes (5 through 10) result in two more clusters: nodes 5 through 7 and nodes 8 through 10.

An illustration of a network with four clusters.

Figure 8.13. An example graph with four clusters

Graphs of the first four Laplacian eigenvectors.

The graphs are labeled alphabetically and placed two in a row. The horizontal axis is labeled Node index n and is marked with values from 0 to 15 in increments of 5. The vertical axis is labeled with u(n) values from -0.4 to 0.6 in increments of 0.2. A line is drawn parallel to the horizontal axis from the point (0, 0). Vertical lines are drawn either above or below this line for every unit along the horizontal axis. The magnitude of the lines vary. Figure a pertains to u subscript 0. A vertical line, up to the 0.2 mark along the vertical axis is drawn from every point along the horizontal line. Figure b corresponds to u subscript 1. The first four lines are drawn vertically up, with the following magnitudes: 0.4, 0.4, 0.2, and 0.5. The next 10 lines are drawn vertically down and have the following magnitudes: -0.3, -0.4, -0.3, -0.2, 0, -0.1, -0.05, -0.2, -0.1, and -0.09. Figure c pertains to u subscript 2 and has vertical lines of the following magnitudes: 0.05, 0.05, 0, 0.05, 0.2, 0.1, 0, 0.38, 0.3, 0.4, -0.3, -0.2, -0.4, and -0.5. Figure d corresponds to u subscript 3 and its vertical lines have magnitudes as follows: 0.18, 0.18, -0.08, 0.2, 0.22, 0.5, 0.3, -0.3, -0.38, -0.5, -0.18, 0.02, -0.2, and -0.3. The lines with negative magnitudes are drawn perpendicularly down from the bottom of the horizontal line. All values are only approximate.

Figure 8.14. First four Laplacian eigenvectors of the graph shown in Figure 8.13

8.5.6 Laplacian Spectra of Special Graphs

The eigenvalues of a few special graphs such as path, ring, complete, and bipartite graphs are presented here.