In the spectral analysis of a graph with 1 connected component, the first non-trivial eigenvector (corresponding to the non-zero smallest eigenvalue) is also called the Fiedler vector. This vector is useful in graph partitioning because it minimizes the distance between the connected vertices in the original graph. In other ways, it can creates partitions in which nodes within the same partitions have minimal distance/high similarity and nodes between partitions have minimum edges connecting them. Now, my question is, as soon as we go to higher eigenvalues, what do eigenvectors mean? Do they represent other partitions of the same graph? Should they be taken into consideration?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Try to look up "nodal domains" in the context of graphs. The rough idea (but wrong in this exact form) is that the subgraph induced on the non-negative (or non-positive) entries of an eigenvector to the $k$-th largest eigenvalue has $k-1$ connected components. There exist some estimates on how wrong this number can be. $\endgroup$– M. WinterJun 23, 2020 at 14:43
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
Yes. See e.g. the paper Multi-way spectral partitioning and higher-order Cheeger inequalities by Lee, Oveis-Gharan and Trevisan. They show how the first $k$ eigenvectors can be used to find a useful $k$-way partitioning.
-
$\begingroup$ Thank you for your quick and helpful answer. Do you think 3rd,4th,5th... eigenvectors by themselves can be used or the k partitioning is supposed to happen in k-dimensions(so with eigenvectors up to k)? $\endgroup$ Jun 24, 2020 at 7:16
$\begingroup$
$\endgroup$
The Fiedler vector refers to the second smallest eigenvalue, here is a study of The third smallest eigenvalue of the Laplacian matrix (2001).
The relationship between the third smallest eigenvalue of the Laplacian matrix and the graph structure is explored. For a tree the complete description of the eigenvector corresponding to this eigenvalue is given and some results about the multiplicity of this eigenvalue are given.
answered Jun 23, 2020 at 14:24