import networkx as nx
from networkx.algorithms import community
import numpy as np
import matplotlib.pyplot as plt
from scipy.linalg import eigh
np.set_printoptions(formatter={'float': lambda x: "{0:0.3f}".format(x)})
Graph = nx.connected_watts_strogatz_graph(124,8,0.05)
L = nx.laplacian_matrix(Graph).toarray()
A = nx.adjacency_matrix(Graph).toarray()
D = L + A
val, vec = eigh(L)
fiedler = 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()
D_sub_1 = L_sub_1 + W_1
val_1, vec_1 = eigh(L_sub_1)
fiedler_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()
D_sub_2 = L_sub_2 + W_2
val_2, vec_2 = eigh(L_sub_2)
fiedler_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])
girvan_newman_generator = community.girvan_newman(Graph)
generator_2_communities = next(girvan_newman_generator)
generator_3_communities = next(girvan_newman_generator)
generator_4_communities = next(girvan_newman_generator)
Partition_2_communities = list(map(list, generator_2_communities))
Partition_3_communities = list(map(list, generator_3_communities))
Partition_4_communities = list(map(list, generator_4_communities))
color_map_sp = np.empty(nx.number_of_nodes(Graph), dtype=object)
for node in P11:
color_map_sp[node] = "white"
for node in P12:
color_map_sp[node] = "orange"
for node in P21:
color_map_sp[node] = "cyan"
for node in P22:
color_map_sp[node] = "yellow"
options = {
"font_size": 15,
"node_size": 550, "node_color": color_map_sp, "linewidths": 1,
"edgecolors": "black",
"width": 2,
"with_labels": True
}
color_map_gn = np.empty(nx.number_of_nodes(Graph), dtype=object)
for node in Partition_4_communities[0]:
color_map_gn[node] = 'red'
for node in Partition_4_communities[1]:
color_map_gn[node] = 'dodgerblue'
for node in Partition_4_communities[2]:
color_map_gn[node] = 'silver'
for node in Partition_4_communities[3]:
color_map_gn[node] = 'lime'
options_gn = {
"font_size": 15,
"node_size": 550, "node_color": color_map_gn, "linewidths": 1,
"edgecolors": "black",
"width": 2,
"with_labels": True
}
position = nx.spring_layout(Graph)
plt.figure(figsize=(28,15))
plt.subplots_adjust( wspace=0.0, hspace=0.0)
plt.subplot(1,2,1)
nx.draw(Graph, position, **options)
plt.subplot(1,2,2)
nx.draw(Graph, position, **options_gn)
PG11 = Partition_4_communities[0]
PG12 = Partition_4_communities[1]
PG21 = Partition_4_communities[2]
PG22 = Partition_4_communities[3]
print(community.partition_quality(Graph, [P11,P12,P21,P22]))
print(community.partition_quality(Graph, [PG11,PG12,PG21,PG22]))
print(community.modularity(Graph, [P11,P12,P21,P22]))
print(community.modularity(Graph, [PG11,PG12,PG21,PG22]))