%matplotlib inline
import matplotlib.pyplot as plt
import networkx as nx
import numpy as np
g = nx.karate_club_graph()
print("Node Degree")
pos = nx.fruchterman_reingold_layout(g)
nx.draw(g, pos=pos, with_labels=True)
plt.show()
A = nx.adj_matrix(g)
n = len(g.nodes)
D = np.zeros((n,n))
for i, node in enumerate(g.nodes):
D[i,i] = g.degree(node)
L = D - A
lams, xs = np.linalg.eig(L)
sorted_lams = sorted(enumerate(lams), key=lambda x: x[1])
alg_connectivity = sorted_lams[1]
print("Algebraic Connectivity:", alg_connectivity[1])
second_lambda = xs[:,alg_connectivity[0]].tolist()
split_val = np.median(second_lambda)
node_colors = []
for i in range(n):
if ( second_lambda[i][0] < split_val ):
node_colors.append(0)
else:
node_colors.append(1)
nx.draw(g, pos=pos, with_labels=True, node_color=node_colors)
plt.show()
parts = nx.community.kernighan_lin_bisection(g)
node_colors_map = {}
for i, lg in enumerate(parts):
for node in lg:
node_colors_map[node] = i
node_colors = [node_colors_map[n] for n in g.nodes]
nx.draw(g, pos=pos, with_labels=True, node_color=node_colors)
plt.show()
tmp_g = nx.Graph(g)
mod_scores = []
ccs = [tmp_g.subgraph(c) for c in nx.connected_components(tmp_g)]
mod = nx.community.quality.modularity(tmp_g, ccs)
mod_scores.append(mod)
max_q_g = []
for x in range(len(g.edges)-1):
edge_scores = nx.betweenness.edge_betweenness_centrality(tmp_g)
ranked = sorted(edge_scores, key=edge_scores.get, reverse=True)
top_edge = ranked[0]
tmp_g.remove_edge(top_edge[0], top_edge[1])
ccs = [tmp_g.subgraph(c) for c in nx.connected_components(tmp_g)]
mod = nx.community.quality.modularity(g, ccs)
mod_scores.append(mod)
max_q_g.append((mod, nx.Graph(tmp_g)))
plt.plot(mod_scores)
plt.grid()
plt.xlabel("# of Edges Removed")
plt.ylabel("Modularity")
max_q = [q for q, tmp_g in max_q_g if q >= 0.3][0]
print("Max Q:", max_q)
target_g = [tmp_g for q, tmp_g in max_q_g if q >= max_q][0]
ccs = [g.subgraph(c) for c in nx.connected_components(target_g)]
comms = len(ccs)
print("Communities:", comms)
node_colors_map = {}
for i, lg in enumerate(ccs):
for node in lg.nodes:
node_colors_map[node] = i/comms
node_colors = [node_colors_map[n] for n in g.nodes]
nx.draw(g, pos=pos, with_labels=True, node_color=node_colors)
plt.show()
max_q = max([q for q, _ in max_q_g])
print("Max Q:", max_q)
target_g = [tmp_g for q, tmp_g in max_q_g if q >= max_q][0]
ccs = [g.subgraph(c) for c in nx.connected_components(target_g)]
comms = len(ccs)
print("Communities:", comms)
node_colors_map = {}
for i, lg in enumerate(ccs):
for node in lg.nodes:
node_colors_map[node] = i/comms
node_colors = [node_colors_map[n] for n in g.nodes]
nx.draw(g, pos=pos, with_labels=True, node_color=node_colors)
plt.show()
ccs = next(nx.community.girvan_newman(g))
comms = len(ccs)
print("Communities:", comms)
print("Q:", nx.community.quality.modularity(g, ccs))
node_colors_map = {}
for i, lg in enumerate(ccs):
for node in lg:
node_colors_map[node] = i/comms
node_colors = [node_colors_map[n] for n in g.nodes]
nx.draw(g, pos=pos, with_labels=True, node_color=node_colors)
plt.show()
ccs = [c for c in nx.community.label_propagation_communities(g)]
comms = len(ccs)
print("Communities:", comms)
print("Q:", nx.community.quality.modularity(g, ccs))
node_colors_map = {}
for i, lg in enumerate(ccs):
for node in lg:
node_colors_map[node] = i/comms
node_colors = [node_colors_map[n] for n in g.nodes]
nx.draw(g, pos=pos, with_labels=True, node_color=node_colors)
plt.show()