import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
from scipy.linalg import eigh, sqrtm, inv
np.set_printoptions(formatter={'float': lambda x: "{0:0.3f}".format(x)})
Graph = nx.karate_club_graph()
L = nx.laplacian_matrix(Graph).toarray()
A = nx.adjacency_matrix(Graph).toarray()
D = L + A
L_norm = nx.normalized_laplacian_matrix(Graph).toarray()
val, vec = eigh(L_norm)
fiedler = np.matmul(inv(sqrtm(D)),vec[:,1])
P1 = np.where( fiedler < 0)
P2 = np.where( fiedler > 0)
sub_1 = nx.subgraph(Graph, P1[0])
W_1 = nx.adjacency_matrix(sub_1)
L_sub_1 = nx.laplacian_matrix(sub_1).toarray()
L_sub_1_norm = nx.normalized_laplacian_matrix(sub_1).toarray()
D_sub_1 = L_sub_1 + W_1
val_1, vec_1 = eigh(L_sub_1_norm)
fiedler_1 = np.matmul(inv(sqrtm(D_sub_1)),vec_1[:,1])
sub_2 = nx.subgraph(Graph, P2[0])
W_2 = nx.adjacency_matrix(sub_2)
L_sub_2 = nx.laplacian_matrix(sub_2).toarray()
L_sub_2_norm = nx.normalized_laplacian_matrix(sub_2).toarray()
D_sub_2 = L_sub_2 + W_2
val_2, vec_2 = eigh(L_sub_2_norm)
fiedler_2 = np.matmul(inv(sqrtm(D_sub_2)),vec_2[:,1])
Ind1_1 = np.where( fiedler_1 < 0)
Ind1_2 = np.where( fiedler_1 > 0)
P11 = []
for i in Ind1_1[0]:
P11.append(P1[0][i])
P12 = []
for i in Ind1_2[0]:
P12.append(P1[0][i])
Ind2_1 = np.where( fiedler_2 < 0)
Ind2_2 = np.where( fiedler_2 > 0)
P21 = []
for i in Ind2_1[0]:
P21.append(P2[0][i])
P22 = []
for i in Ind2_2[0]:
P22.append(P2[0][i])
color_map = np.empty(nx.number_of_nodes(Graph), dtype=object)
for node in P11:
color_map[node] = "white"
for node in P12:
color_map[node] = "orange"
for node in P21:
color_map[node] = "cyan"
for node in P22:
color_map[node] = "yellow"
options = {
"font_size": 15,
"node_size": 550, "node_color": color_map, "linewidths": 1,
"edgecolors": "black",
"width": 2,
"with_labels": True
}
pos = nx.spring_layout(Graph, seed=11)
plt.figure(figsize=(11,11))
nx.draw(Graph, pos, **options)