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