Computing the Fiedler Vector in Python

Question

How do I find the fielder vector of a Laplacian (L) in Python?

I can get the eigenvalues and eigenvectors using: eigenvalues, eigenvectors = linalg.eig(L)

I assume that python does not return the eigenvalues in an order.

Do I take the 2nd largest eigenvalue and then match it to the corresponding eigenvector (matching in index)?

When ordering the eigenvalues, how do I deal with negative values? Is the ordering by absolute magnitude?

Thanks for your help

Answer 1

Well, I don't know about the math involved, but I'll do my best.

If you check the documentation, linalg.eig does in fact return the eigenvectors in the same order as their corresponding eigenvalues.

I might do something like:

w, v = linalg.eig(L)
seen = {}
unique_eigenvalues = []
for (x, y) in zip(w, v):
    if x in seen:
        continue
    seen[x] = 1
    unique_eigenvalues.append((x, y))
fiedler = sorted(unique_eigenvalues)[1][1]

by default Python sorts tuples by the first element, then the second and so on, and numbers are ordered just the way you'd expect (-2 < -1 etc.). This assumes that your eigenvalues aren't complex of course.

Also, I've assumed that there might be duplicate eigenvalues and that the Fiedler vector is the eigenvector associated with the second smallest unique eigenvalue.

Answer 2

Just an additional solution:

import numpy as np
import scipy.linalg as la

eig_values, eig_vectors = la.eig(laplacian)
fiedler_pos = np.where(eigvalues.real == np.sort(eig_values.real)[1])[0][0]
fiedler_vector = np.transpose(eig_vectors)[fiedler_pos]

print("Fiedler vector: " + str(fieder_vector.real))

Explanation: Fiedler vector has the smallest non-zero eigenvalue. We therefore need to sort the eigenvalues, and take the second smallest one (it makes sense to verify that the zero element is there on the first place as well, by the way). This is done in np.sort(eigvalues.real)[1], as you can see the second element of the sorted (real) array is taken.

Now we just need to match the value in the original array and get its location. This is conveniently done with the np.where() command. The result is an array of all discovered instances defined in the parenthesis, from which we take the first one. The fiedler_pos variable now contains the fiedler vector position in eigenvectors.

In order to get the vector itself, one way is to use the transposed eigenvectors matrix at the relevant position.