I have a graph with multiple connected components, and its adjacency matrix. I form the Laplacian matrix (wiki Laplacian matrix), and from the 1K nodes there around 100 eigenvalues of value zero. (I use eig in matlab and the first 5 have negative values which I assume is a problem with the accuracy of matlab).
I take that there are 100 connected components in the graph.
If only the first eigenvalue was 0, I would take the eigenvector corresponding to the second smallest eigenvalue (Fiedler vector) to sort the adjacency matrix into a band matrix. This is done by finding the indexes to sort the Fiedler vector and use that to sort the adjacency matrix. Can this be done accordingly using the first non-zero eigenvalue's vector?
Can I perform clustering with these eigenvectors in the same way as I would with PCA (principal component analysis).
Best Answer
In fact, the multiplicity of the eigenvalue 0 matches the number of connected components in the graph. However, I doubt that in the case of multiple components the eigenvector corresponding to the first non-zero eigenvalue has a similar clear meaning as the Fiedler vector for a single connected component. My doubts arise from the fact, that the ordering given by the Fiedler vector is strongly related to the 'best' cut of the nodes, which appears strange across multiple components, and might not really consider the inter-component-connections as intended.
The following approach will surely better fit your purpose: In a first step, identify all the connected components (e.g. by a simple breadth-first-search). Then, handle each connected component individually, since now the Laplacian of each single component has indeed a meaningful and well-understood Fiedler vector. Further, the numerical stability might be better, since the eigenvalues are computed only on much smaller submatrices.
Then, finally, sort the adjacency matrix by at first the components in arbitrary order, and within each component according to the order given by the inner-component's Fiedler vector's entries. This will lead to a block matrix (one block for each component), with an individual meaningful ordering inside each block.
Further, you might also consider to use the normalized Laplacian instead of the Laplacian, i.e., instead of $L = D - W$ you could just use $\hat L = D^{-1/2} L D^{-1/2} = I - D^{-1/2} W D^{-1/2}$, since its Fiedler vector approximates the so-called 'normalized cut', which often gives 'better' (implicitly size-balanced) results in clustering than the simple 'mincut' that is approximated by the unnormalized Laplacian.
Edit, answering the comment:
I just played around with the eigenvectors of a graph that consists of $C > 1$ components and found the results quite interesting:
As expected, the eigenvectors $v_0, ..., v_{C-1}$ are constant within each component, while favoring different components, together building the nullspace.
The first eigenvector corresponding to a positive eigenvalue, $v_C$, as well as all other eigenvectors $v_{C+1}, \ldots$ (1000 in my tests), behave in the same way: They 'select' a single component and provide some cluster information for it (i.e., setting positive and negative values correlating to some cluster structure), while assigning value 0 to all other components (!). Thus, there is no 'cutting across multiple components'.
The order in which the components are selected is surely driven by the cut's strength (as given by the eigenvalue). Thus, especially for unbalanced component sizes, the order appears somewhat arbitrary, and a large component might for example be selected very often before another component is selected for the first time.
Conjecture 1: In the experiments, there is no 'cutting accross multiple components'. Perhaps one can even prove this, i.e., for all eigenvectors $v_C, v_{C+1}, \ldots$ it holds that all their non-zero entries belong to the same component.
Conjecture 2: For each component $c = 1, \ldots, C$ let $v_{i_c}$ with $i_c \geq C$ denote the 'first' (lowest index) 'non-trivial' (positive eigenvalue) eigenvector, which has non-zero entries within component $c$. Then, $v_{i_c}$ represents the strongest cut within component $c$, thus, it takes the same role as $f_c$ the Fiedler vector of $G_{|c}$, i.e., of $G$ restricted to component $c$. I suppose that $v_{i_c}$ equals $f_c$ on the nodes in $c$, and that the eigenvalue $\lambda_{i_c}$ equals the eigenvalue of $f_c$.
These (experimental) insights show that the Fiedler vector of $G$ alone is no good choice to order all nodes of the graph, since it only clusters the nodes of a single component, but it assigns 0 to all other nodes.
Since each non-trivial eigenvector of $G$ concentrates on just a single component, it is a better choice (for the purpose of providing a global ordering) to use the Fiedler vector $f_c$ of each component $c$ individually, which might match $v_{i_c}$, and to bring the components in any order (for example in the order as they are selected by the $v_{C+*}$'s .
Edit, proving the conjectures:
The first conjecture must be slightly weakened, otherwise it does not hold.
Conjecture 1b: one can find a full set of eigenvectors $v_1, \ldots, v_n$ such that for each $v_i$ all its non-zero entries belong to the same component.
The key insight is the following:
Each of $G$'s eigenvectors gives also an eigenvector for each component $c$ by restricting its coordinates to just the nodes in $c$.
Proof of Conjecture 1b: Assume that all non-trivial eigenvalues of all subgraphs $G_{|c}$ are all distinct. Then, no eigenvector of $G$ can cross multiple components, since for each component it must correspond to different eigenvalues. Now assume that (for example in a very symmetric graph) multiple components do have exactly the same non-trivial eigenvalue. Then, in fact, there do exist eigenvectors that are non-zero across these multiple components (somehow in contradiction to the above), but, one can restrict any of these to just each component alone and still gets an eigenvector. Thus (similar as for the 1-vector for the trivial eigenvalue), the multiplicity is exactly the number of components that share this eigenvalue. Thus, the corresponding eigenspace can also be spanned by choosing eigenvectors that do not cross multiple components.
So, depending on how you compute the eigenvectors, there can appear eigenvectors that cross multiple components, iff these components share the same inner-component eigenvalue. However, one can still choose another basis for this eigenspace that consists of eigenvectors that do not cross multiple components.
Proof of Conjecture 2: This follows directly from the key insight.