Graph Laplacian and its Eigenvalues
Contents
Graph Laplacian and its Eigenvalues¶
Laplacian Matrix¶
Given a graph \( G = (V,E) \) where \( V = \{ v_1, v_2, ..., v_n \} \) is the set of nodes and \( E = \{ e_1, e_2, ..., e_n \} \) is the set of edges then Laplacian Matrix is defined as
where \( A \) is an adjacency matrix
and \( D \) is a diagonal matrix
\(\rightarrow \text{If edges of graph are weighted then } degree(v_i) = \sum_j A_{ij}\\\)
Consider the following example

Fig. 26 Node with weighted edges¶
As we can see from the above figure, the edges of the node are weighted. So the degree of the node will be 3+2+1.5=6.5 rather than 3.
For irregular graphs we typically normalize \( L \) as
where \( D^{-1/2} \equiv \) diagonal matrix with \( i^{th} \) entry \( = \frac{1}{\sqrt{d_i}} \)
Diagonal entries, \( L_{ii} = d_i \)
Offdiagonal entries, $\( L_{ij} = \begin{cases} 0, \text{ if there is no edge between } i \text{ and } j\\ -1, \text{otherwise} \end{cases} \)$
\( \rightarrow \) Sum of each row of \( L \) is 0 as \( D_{ii} = \sum_{j=1}^{n}A_{ij} \) and \( L = D - A \)
Eigenvector/Eigenvalues of Laplacian Matrix¶
\( \forall \) \( \lambda_i (\frac{1}{d} L) \in [0, 2] \)
\( \lambda_i \in [0, 2d]\)
\( \lambda_i (\frac{1}{d} L) \in [0, d] \)Normalized Laplacian = \( D^{-1/2}LD^{-1/2} \)
For regular graphs (d)
\[\begin{split} D^{-1/2} = \begin{bmatrix} \frac{1}{\sqrt{d}} & & \\ & \ddots & \\ & & \frac{1}{\sqrt{d}} \end{bmatrix} = \frac{1}{\sqrt{d}} I \end{split}\]Normalized Laplacian = \( (\frac{1}{\sqrt{d}} I) L (\frac{1}{\sqrt{d}} I) = \frac{1}{d}L \)
\( \lambda_1(L) = 0 \\ \) \( \lambda_k(L) = 0 \) iff k disconnected components are present in graph
For example, consider the following graph
Fig. 27 A disconnected graph¶
\(\hspace{7mm} \lambda_1(L) = 0 \) using all ones eigen vector \( \\ \hspace{7mm} \lambda_2(L) = 0 \\ \)
\( \rightarrow v_1 \) and \( v_2 \) are orthogonal to each other.
\( \rightarrow \) Looking at the values of \( v_2(L), ...., v_k(L) \) tells us what the components are.
What if the graph is disconnected?¶
\( \hspace{7mm} \lambda_2(L) \) will still give a “measure of how much, \( G \) resembles a 2 disconnected components, i.e., sparsest cut”.