Why is second smallest eigenvalue and the corresponding eigenvector used to partition a graph?

Solution 1:

I found this exposition of the Smallest Eigenvalues of a Graph Laplacian by Shriphani Palakodety to be readable and informative.

The article begins with a discussion of eigenvectors for the smallest eigenvalue, which in the case of the graph Laplacian happens to be zero. The number of eigenvectors for this eigenvalue gives the connected components of the graph (and the nonzero entries of each eigenvector point to the nodes of each connected component).

Then the discussion turns to the second smallest eigenvalue and what it has to do with clustering of nodes and therefore partitioning of a graph. The corresponding bibliography reference is to a "landmark paper" by Miroslav Fiedler (1973) on Algebraic Connectivity of Graphs.

A deeper survey is in this 2007 paper by Nair Maria Maia de Abreu, "Old and new results on algebraic connectivity of graphs".

Solution 2:

The key ingredient of this result is Perron-Frobenius theorem.

Let $L=D-A$, where $D$ is the degree matrix and $A$ is the adjacency matrix (See this wiki page). Recall that $L$ is a singular positive semidefinite symmetric matrix.

Now, notice that if $D$ is singular then the graph is already disconnected and the nullity of $L$ is bigger or equal to 2. Let us assume that $D$ is invertible.

Let $L_{1}=Id-D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$, which is also positive semidefinite. Notice that the nullities of $L_{1}$ and $L$ are equal.

Now the nullity of $L_{1}=Id-D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$ is bigger or equal to 2 if and only if the biggest eigenvalue of $D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$, which is $1$ (why?), has multiplicity bigger or equal to $2$.

Since $D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$ is symmetric with positive entries and the multiplicity of the spectral radius (the biggest eigenvalue) is not 1 then $D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$ is not irreducible. Thus $A$ is also not irreducible (Check this wiki page).

Since $A$ is not irreducible, there is a permutation matrix $P$ (which represents a relabeling of the vertices of the graph) such that $PAP^{-1}=\begin{pmatrix} A_1 & B\\ 0 & A_2\end{pmatrix}$, where $A_1,A_2$ are square matrices.

Since $P$ is a permutation then $P^{-1}=P^t$. Hence $PAP^t$ is symmetric, since $A$ is symmetric. Thus, $B=0$. Notice that $A_1,A_2$ are adjacency matrices too. Thus, the graph is not connected.