4
$\begingroup$

For a given N-vertex similarity graph $ G=(V,A) $ the eigenvalues of the unrenormalized (graph) Laplacian may be denoted as

$$ 0= \mu_0 \leq \mu_1 \leq ... \leq \mu_N $$ where the corresponding eigenvectors may be written as

$$ v_0 , v_1 , ... ,v_N $$ In the case where $ 0= \mu_0 = \mu_1 < \mu_2 $ I find conflicting definitions for the Fiedler vector in the literature , namely $ v_1 $(eigenvector corresponding to the second lowest eigenvalue?) or $ v_2 $ (eigenvector corresponding to the lowest non-zero eigenvalue). Which one should one choose as Fiedler vector?

In addition things get ambiguous when the lowest non-zero eigenvalue is degenerated as well. For example assume $ N = 5 $ and $ A_{ij} = 1$ if $i \neq j $ and $0$ else. The eigenvalues of the Laplacian are (0,5,5,5,5) in this case. Which eigenvector corresponds to the Fiedler vector in this case?

A good reference would be appreciated !

$\endgroup$

1 Answer 1

7
$\begingroup$

The concept of a Fiedler vector is defined for graphs that consist of one single connected component. Since the number of zero eigenvalues counts the number of connected components, the second largest eigenvalue $\nu_1$ is then always nonzero. The multiplicity $m_1$ of the second largest eigenvalue may be greater than one, in which case there is more than a single Fiedler vector.

One might ask why not extend the definition of the Fiedler vector to graphs with more than a single connected component. This is not particularly useful, as explained in this MO posting.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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