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)

[2. 2. 3. 3. 2. 2.]

# put them on the diagonal
D = np.diag(d)
print(D)

[[2. 0. 0. 0. 0. 0.]
 [0. 2. 0. 0. 0. 0.]
 [0. 0. 3. 0. 0. 0.]
 [0. 0. 0. 3. 0. 0.]
 [0. 0. 0. 0. 2. 0.]
 [0. 0. 0. 0. 0. 2.]]

# compute the Laplacian
L = D - A
print(L)

[[ 2. -1. -1.  0.  0.  0.]
 [-1.  2. -1.  0.  0.  0.]
 [-1. -1.  3. -1.  0.  0.]
 [ 0.  0. -1.  3. -1. -1.]
 [ 0.  0.  0. -1.  2. -1.]
 [ 0.  0.  0. -1. -1.  2.]]

# compute eigenvectors and eigenvalues of the Laplacian
val, Vec = np.linalg.eigh(L)
print(val)
print(Vec)

[6.24500451e-17 4.38447187e-01 3.00000000e+00 3.00000000e+00
 3.00000000e+00 4.56155281e+00]
[[ 0.40824829 -0.46470513 -0.01070412  0.76360255  0.0113975  -0.18452409]
 [ 0.40824829 -0.46470513 -0.5097485  -0.55068122 -0.14226733 -0.18452409]
 [ 0.40824829 -0.26095647  0.52045262 -0.21292133  0.13086983  0.6571923 ]
 [ 0.40824829  0.26095647  0.52045262 -0.21292133  0.13086983 -0.6571923 ]
 [ 0.40824829  0.46470513 -0.43751783  0.09376005  0.61896731  0.18452409]
 [ 0.40824829  0.46470513 -0.08293479  0.11916128 -0.74983715  0.18452409]]

# verify that they satisfy definition of eigenvalues/vectors
# is there one close to 3?
np.any(np.isclose(val, 3))

True

# 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)

[ 0.76360255 -0.55068122 -0.21292133 -0.21292133  0.09376005  0.11916128]
[ 2.29080765 -1.65204367 -0.63876398 -0.63876398  0.28128015  0.35748383]

# 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();