# Computing the Fiedler vector of a large, sparse graph

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$$?

• This is a problem that is frequently solved for many applications. What does a literature search turn up on how to compute these eigenvectors? Mar 20 at 23:35
• @WolfgangBangerth, cs.fsu.edu/~mascagni/papers/RICP2002_1.pdf
– Set
Mar 20 at 23:43
• There's also this paper, sciencedirect.com/science/article/pii/S0377042714001587
– Set
Mar 20 at 23:57
• Why not use one of these methods? Mar 21 at 2:06
• @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.
– Set
Mar 21 at 3:29