import numpy as np
import matplotlib.pyplot as plt
import networkx as nx
A = np.array([
[0,1,1,0,0,0],
[1,0,1,0,0,0],
[1,1,0,1,0,0],
[0,0,1,0,1,1],
[0,0,0,1,0,1],
[0,0,0,1,1,0]], dtype=float)
g = nx.from_numpy_matrix(A)
layout = nx.spring_layout(g, pos=nx.circular_layout(g))
nx.draw(g, pos=layout, with_labels=True, node_color='white')
plt.show()
# compute the degree matrix, by summing rows (or columns, since it's symmetric)
d = np.sum(A, axis=0)
print(d)
# put them on the diagonal
D = np.diag(d)
print(D)
# compute the Laplacian
L = D - A
print(L)
# compute eigenvectors and eigenvalues of the Laplacian
val, Vec = np.linalg.eigh(L)
print(val)
print(Vec)
# verify that they satisfy definition of eigenvalues/vectors
# is there one close to 3?
np.any(np.isclose(val, 3))
# check that multiplication by 3 and multiplication by eigenvector give same answer
idx_lambda3 = np.argmin(np.abs(val - 3))
v3 = Vec[:, idx_lambda3]
print(v3)
print(L @ v3)
# graph them so that we can see the eigenvalue corresponding to the fiedler vector
plt.plot(np.sort(val), linestyle='-', marker='o')
plt.show()
# get the fiedler vector, look out for the sign change
f = Vec[:, np.argsort(val)[1]]
plt.plot(f, linestyle='-', marker='o'); plt.show();
# color by fiedler vector sign change
color = ['orange' if eigv > 0 else 'gray' for eigv in f]
nx.draw(g, pos=layout, with_labels=True, node_color=color); plt.show();