In [1]:
%matplotlib inline

import matplotlib.pyplot as plt
import networkx as nx
import numpy as np
In [5]:
g = nx.karate_club_graph()
print("Node Degree")

pos = nx.fruchterman_reingold_layout(g)
    
nx.draw(g, pos=pos, with_labels=True)
plt.show()
Node Degree

Partitioning

Spectral Partitioning

In [6]:
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()
Algebraic Connectivity: 0.4685252267013922

Kernighan-Lin Paritioning

In [7]:
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()

Community Detection

Girvan-Newman Centrality Method

In [8]:
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")
Out[8]:
<matplotlib.text.Text at 0x1081e35c0>
In [ ]:
 
In [9]:
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: 0.35996055226824225
Communities: 2
In [ ]:
 
In [10]:
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()
Max Q: 0.40129848783694877
Communities: 5
In [11]:
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()
Communities: 2
Q: 0.35996055226824225
In [ ]:
 

Label Propagation-Based Communities

In [12]:
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()
Communities: 3
Q: 0.3251150558842867
In [ ]:
 
In [ ]: