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?
Best Answer
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".