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(28,4,0.1)
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))
def mapping(partition_1, partition_2):
for i in partition_1:
for j in partition_2:
if nx.shortest_path_length(Graph, source=i, target=j) == 1 :
Graph[i][j]['color'] = "silver"
Graph[i][j]['style'] = "dotted"
def standard_map_init():
for e in Graph.edges():
Graph[e[0]][e[1]]['color'] = "black"
Graph[e[0]][e[1]]['style'] = "solid"
standard_map_init()
for i in [P11, P12, P21, P22]:
for j in [P11, P12, P21, P22]:
if i != j :
mapping(i, j)
edge_color_map_sp = [ Graph[e[0]][e[1]]['color'] for e in Graph.edges() ]
edge_style_map_sp = [ Graph[e[0]][e[1]]['style'] for e in Graph.edges() ]
standard_map_init()
for i in [Partition_4_communities[0], Partition_4_communities[1], Partition_4_communities[2], Partition_4_communities[3]]:
for j in [Partition_4_communities[0], Partition_4_communities[1], Partition_4_communities[2], Partition_4_communities[3]]:
if i != j :
mapping(i, j)
edge_color_map_gn = [ Graph[e[0]][e[1]]['color'] for e in Graph.edges() ]
edge_style_map_gn = [ Graph[e[0]][e[1]]['style'] for e in Graph.edges() ]
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_sp = {
"font_size": 15,
"node_size": 550, "node_color": color_map_sp, "linewidths": 1,
"edgecolors": "black", "edge_color": edge_color_map_sp, "style": edge_style_map_sp,
"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", "edge_color": edge_color_map_gn, "style": edge_style_map_gn,
"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_sp)
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]))