11
$\begingroup$

In spectral graph partition theory, the eigenvector $v_2$ (also called Fiedler vector) corresponding to the second smallest eigenvalue $\lambda_2$ (also known as Fiedler eigenvalue, which actually also defines the algebraic connectivity of a graph) of the Laplacian matrix $L$ of a graph $G$, in general, is used to partition the graph.

What is the underlying philosophy behind this? Any reference to any related proofs on this?

$\endgroup$
6
$\begingroup$

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".

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.