2
$\begingroup$

I have a sparse, undirected and unweighted graph $G$ of size $n$, with $n$ on the order of say several million. I would like to compute the Fiedler vector $f$ of $G$, which is the eigenvector associated to the smallest nonzero eigenvalue of the associated Laplacian matrix $W$.

My current method is to compute the largest eigenvalue $\lambda_1$ of $W$, using power iteration, and then form the matrix,

$$B=\lambda_1I - W$$

The matrix $B$ still has largest eigenvalue equal to $\lambda_1$, but now with associated eigenvector $\frac{1}{\sqrt{n}}{\bf 1}$, and $f$ is now associated to its second largest eigenvalue.

Therefore, if I subtract off $\frac{\lambda_1}{n}{\bf 1}^{}{\bf 1}^t$ from $B$, then the eigenvector associated to the largest eigenvalue of this matrix will be $f$, and I can again use power iteration to compute it.

Note, however, that due to the size of $G$, I can neither explicitly form $\frac{\lambda_1}{n}{\bf 1}^{}{\bf 1}^t$, nor can I explicitly subtract it off from $B$.

Instead, I use the following modified power iteration algorithm to compute $f$,

\begin{align} &x=x_0\\ &\text{for i in 1:N}\\ &\hspace{8mm}x=Bx - \frac{\lambda_1}{n}({\bf 1}^tx){\bf 1}\\ &\hspace{8mm}x = x\; /\; \|x\|_2\\ &\text{done}\\ &\text{return}\;x \end{align}

Unfortunately, convergence is exceedingly slow, likely due to a very small spectral gap.

Is there a better/faster way to compute the Fiedler vector $f$ of $G$?

$\endgroup$
5
  • $\begingroup$ This is a problem that is frequently solved for many applications. What does a literature search turn up on how to compute these eigenvectors? $\endgroup$ Mar 20 at 23:35
  • $\begingroup$ @WolfgangBangerth, cs.fsu.edu/~mascagni/papers/RICP2002_1.pdf $\endgroup$
    – Set
    Mar 20 at 23:43
  • $\begingroup$ There's also this paper, sciencedirect.com/science/article/pii/S0377042714001587 $\endgroup$
    – Set
    Mar 20 at 23:57
  • $\begingroup$ Why not use one of these methods? $\endgroup$ Mar 21 at 2:06
  • $\begingroup$ @WolfgangBangerth, well, just because someone publishes a paper doesn't mean the method is any good, so I thought I would run the problem by the community first before I spend a bunch of time implementing one of these methods. $\endgroup$
    – Set
    Mar 21 at 3:29

1 Answer 1

5
$\begingroup$

Disclosure: This is my master's supervisor's work, he and his co-authors are pretty well-known in the field.

TRACEMIN-Fiedler is a parallel algorithm to compute the Fiedler vector of large graphs based on the Trace Minimization algorithm. The algorithm is efficient and quite scalable. It performs better than the better known ("gold" standard) MC73 FIEDLER of the Harwell Subroutine Library.

If you are in a position where an academic license is enough, or if you can pay for the commercial licence, MC73 is pretty good ( https://www.hsl.rl.ac.uk/catalogue/hsl_mc73.html ). That is probably why it is better known.

TRACEMIN-Fiedler: A Parallel Algorithm for Computing the Fiedler Vector Murat Manguoglu and Eric Cox and Faisal Saied and Ahmed Sameh https://user.ceng.metu.edu.tr/~manguoglu/PDFs/vecpar10.pdf

(An earlier preprint version is also available at https://arxiv.org/pdf/1003.3689v1.pdf , some details are explained here but not in the published paper)

$\endgroup$
0

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.