# IMPORT
import random
import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
# LOAD & DRAW
G=nx.read_adjlist('network.txt')
nx.draw(G, with_labels=True, font_color="white")
# CONVERT STRING LABELS TO INTS
# print(G.nodes)
G=nx.convert_node_labels_to_integers(G, first_label=0); #print(G.nodes)ANLY-645: Week-06
Chapter-6: Communities
Slide download
Click here to download the relevant notebook(s) for these slides
–>
Break
Lets take a 10 minute break before moving onto the lab.

Lab presentation
Student lab presentation

Lab Demonstration
Partitions, Modularity, Zachary’s Karate Club, Girvan-Newman clustering algorithm 
Partitions
Recall: A partition of a graph is a separation of its nodes into disjoint groups.- There are two trivial partitions:
- The partition with one set containing every node;
- The partition with N sets, each containing a single node.
- A valid partition thus contains between 1 and N sets.
Import & load network
- We will use a simple toy graph, with two fully connected communities, each with four nodes, connected by a single link
Example: Partition
- Formally, a partition is a list of sets such that every node is in exactly one set, which is the case here.
- The following is an example of a partition of the nodes in our network
- Notice how the partitions are stored as a list of dictionaries containing node-IDs for the three partitions
partition = [
{1, 2, 3},
{5, 6, 7},
{0, 4},
]NetworkX can verify that our partition is valid:
print(partition)
print("\n",nx.community.is_partition(G, partition))[{1, 2, 3}, {5, 6, 7}, {0, 4}]
True
Aside: Python enumerate
- In Python, a for loop is usually written as a loop over an iterable object. This means you don’t need a counting variable to access items in the iterable.
- Sometimes, though, you do want to have a variable that changes on each loop iteration.
- Rather than creating and incrementing a variable yourself, you can use Python’s enumerate() to get a counter and the value from the iterable at the same time!
# WITHOUT ENUMERATE
idx=0;
for i in [0,10,20,30]:
idx+=1
print(idx,i)1 0
2 10
3 20
4 30
# WITH ENUMERATE
for idx,item in enumerate([0,10,20,30]):
print(idx,item)0 0
1 10
2 20
3 30
Partition maps
- When developing community detection algorithms, we often use a partition map
- i.e a dictionary mapping node names to a partition index.
- This is useful for quickly comparing if two nodes are in the same cluster in the partition:
partition_map = {}
for idx, cluster_nodes in enumerate(partition):
print(idx,cluster_nodes)
for node in cluster_nodes:
partition_map[node] = idx
partition_map0 {1, 2, 3}
1 {5, 6, 7}
2 {0, 4}
{1: 0, 2: 0, 3: 0, 5: 1, 6: 1, 7: 1, 0: 2, 4: 2}
In this dictionary, the keys are the node names and two nodes will have the same value if they are in the same partition:
print(partition_map[1] == partition_map[2])
print(partition_map[0] == partition_map[7])True
False
Aside: list comprehension
- List comprehension provides a more concise syntax when creating a new list based on the values of an existing list,
# WITH LIST COMPREHENSION
list1=[0,1,2,3,4,5]
list2=[]
for i in range(0,len(list1)):
list2.append(2*list1[i])
print(list2)[0, 2, 4, 6, 8, 10]
# WITH LIST COMPREHENSION-1
list3=[2*list1[i] for i in range(0,len(list1))]
print(list3)[0, 2, 4, 6, 8, 10]
# WITH LIST COMPREHENSION-2
list4=[2*value for value in list1]
print(list4)[0, 2, 4, 6, 8, 10]
Visualizing partitions
We can visualize partitions by coloring nodes with their partition membership:
node_colors = [partition_map[n] for n in G.nodes]
print(node_colors)
nx.draw(G, node_color=node_colors, with_labels=True, font_color="white")[2, 0, 0, 0, 2, 1, 1, 1]
Utility function
- We can make a function that takes a graph, and a given partition, and generates a color coded plot
def plot_partition(G,partition):
#BUILD PARTITION-MAP
partition_map = {}
for idx, cluster_nodes in enumerate(partition):
for node in cluster_nodes:
partition_map[node] = idx
#PLOT
node_colors = [partition_map[n] for n in G.nodes]
nx.draw(G, node_color=node_colors, with_labels=True, font_color="white")
plt.show()Explore partitions
Run the following code to test your plotting function
#PARTITION-1: (singletons)
partition = [{0},{1},{2},{3},{4},{5},{6},{7}]
plot_partition(G,partition)
#PARTITION-2: (full network)
partition = [{0,1,2,3,4,5,6,7}]
plot_partition(G,partition)
#PARTITION-3:
partition = [{1, 2, 3},{5, 6, 7},{0, 4}]
plot_partition(G,partition)Modularity: Overview
- At a high level, network community detection consists of finding a partition that achieves good separation between the groups of nodes.
- Before we get into how to find good partitions of a graph, we need an objective – a way to measure how good the partition is.
- Modularity is one such objective function.
- The modularity of a graph partition compares the number of intra-group edges with a random baseline.
- Higher modularity scores correspond to a higher proportion of intra-group edges
Higher modularity = better separation of groupsA random partition will have a modularity around zero
- For weighted undirected networks, as described in the text, we have
\[ Q_w=\frac{1}{W}\sum_C \left(W_C-\frac{s_C^2}{4W}\right) \]
where
- \(W\) is the total weight of the links of the network,
- \(W_C\) the total weight of the internal links of cluster \(C\), and
- \(s_C\) the total strength of the nodes of \(C\).
Explore modularity
- NetworkX provides a modularity function, let’s compare several partitions
#PARTITION-1: (singletons)
str1=""
partition = [{0},{1},{2},{3},{4},{5},{6},{7}]
plot_partition(G,partition)
str1+=str(np.round(nx.community.quality.modularity(G, partition),3))+" "
#PARTITION-2: (full network)
partition = [{0,1,2,3,4,5,6,7}]
plot_partition(G,partition)
str1+=str(np.round(nx.community.quality.modularity(G, partition),3))+" "
#PARTITION-3:
partition = [{1, 2, 3},{5, 6, 7},{0, 4}]
plot_partition(G,partition)
str1+=str(np.round(nx.community.quality.modularity(G, partition),3))+" "
# PARTITION-4
partition = [{0, 1, 2, 3},{4, 5, 6, 7}]
plot_partition(G,partition)
str1+=str(np.round(nx.community.quality.modularity(G, partition),3))+" "
print("modularity values: \n", str1)modularity values:
-0.127 0.0 0.204 0.423
Zachary’s Karate Club
Overview
- When writing and testing community-detection algorithms, it helps to make use of benchmark networks: graphs with a known, “natural” community structure.
- Perhaps the most famous benchmark graph is Zachary’s Karate Club.
- It contains 34 nodes, representing members of a karate club whose interactions were monitored over a period of three years by researchers.
- Links in this graph connect individuals interacting outside club activities, a proxy for social ties.
- During the course of the study, a conflict between the instructor Mr. Hi (node 0) and the president, or Officer (node 33) led to a split of the club into separate groups led by Mr. Hi and Officer.
- In this case we know whom each member of the group followed after the split, providing empirical community labels: those members who followed Mr. Hi are said to be one community and those following the Officer make up the other.
- For this graph, we assume that the post-split group composition was largely driven by the social ties: members of the same friend groups would want to be part of the same club after the split.
- We thus expect a good community-detection algorithm to predict the post-split group composition with high accuracy.
- Zachary’s karate club is such a popular benchmark graph that it has its own function in NetworkX:
Load and draw network: Random
K = nx.karate_club_graph()
# RANDOM
nx.draw(K, pos=nx.random_layout(K), with_labels=True)
plt.show()Load and draw network: Force directed
Recall:Instructor Mr. Hi is node-0 and the president, or Officer is node-33.
# FORCE DIRECTED (Fruchterman-Reingold force-directed algorithm.)
nx.draw(K, pos=nx.spring_layout(K, iterations=250, threshold=0.00001), with_labels=True)
plt.show()Aside: Assigning node attributes
- Each node in a NetworkX graph has a dictionary of attributes associated with it. (empty by default)
- This dictionary can hold arbitrary data about a node.
- We can get the attributes for a single node by giving the node name to the
nodesobject.
# CREATE GRAPH WITH ATTRIBUTES
G1=nx.Graph()
G1.add_node(0, D=-1)
G1.add_node(1, D=-2)
print(G1)
# ACCESS ATTRIBUTES
print(G1.nodes[0]["D"])
print(G1.nodes[1]["D"])
# OVERWRITE ATTRIBUTE
G1.nodes[0]["D"]=100
print(nx.get_node_attributes(G1, 'D'))Graph with 2 nodes and 0 edges
-1
-2
{0: 100, 1: -2}
Explore node attributes
- Each node in this graph has a
'club'attribute, indicating whether the member followed the instructor or the president after the split:
print(K.nodes)
for i in range(0,len(K.nodes)):
print(K.nodes[i])[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33]
{'club': 'Mr. Hi'}
{'club': 'Mr. Hi'}
{'club': 'Mr. Hi'}
{'club': 'Mr. Hi'}
{'club': 'Mr. Hi'}
{'club': 'Mr. Hi'}
{'club': 'Mr. Hi'}
{'club': 'Mr. Hi'}
{'club': 'Mr. Hi'}
{'club': 'Officer'}
{'club': 'Mr. Hi'}
{'club': 'Mr. Hi'}
{'club': 'Mr. Hi'}
{'club': 'Mr. Hi'}
{'club': 'Officer'}
{'club': 'Officer'}
{'club': 'Mr. Hi'}
{'club': 'Mr. Hi'}
{'club': 'Officer'}
{'club': 'Mr. Hi'}
{'club': 'Officer'}
{'club': 'Mr. Hi'}
{'club': 'Officer'}
{'club': 'Officer'}
{'club': 'Officer'}
{'club': 'Officer'}
{'club': 'Officer'}
{'club': 'Officer'}
{'club': 'Officer'}
{'club': 'Officer'}
{'club': 'Officer'}
{'club': 'Officer'}
{'club': 'Officer'}
{'club': 'Officer'}
Visualize “ground truth” partition
- We can visualize these labels by coloring each node according to its
'club'attribute:
K = nx.karate_club_graph()
club_color = {
'Mr. Hi': 'orange',
'Officer': 'lightblue',
}
node_colors = [club_color[K.nodes[n]['club']] for n in K.nodes]
nx.draw(K, pos=nx.spring_layout(K),node_color=node_colors, with_labels=True)- The separation looks good (few inter-community links vs intra-community links)
Convert to a partition data-structure
- Let’s create a graph partition based on these labels and measure its modularity.
- We can do this by creating a dictionary of two sets, one for each value of the nodes’
'club'attribute, then assigning the nodes to the corresponding set.
groups = {
'Mr. Hi': set(),
'Officer': set(),
}
for n in K.nodes:
club = K.nodes[n]['club']
groups[club].add(n)
print(groups){'Mr. Hi': {0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 16, 17, 19, 21}, 'Officer': {32, 33, 9, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31}}
Using the dictionary’s .values() method, we get the list that defines our partition:
empirical_partition = list(groups.values())
print(empirical_partition)[{0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 16, 17, 19, 21}, {32, 33, 9, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31}]
Explore “ground truth” partition modularity
plot_partition(K,empirical_partition)
nx.community.is_partition(K, empirical_partition)True
Since our partition is indeed a valid partition, we can get the modularity of this partition:
print(nx.community.quality.modularity(K, empirical_partition))0.39143756676224206
This is a relatively high modularity, which is what we expect.
Random partition: Create list
- For comparison, let’s generate a random partition of this network and check its modularity.
- We would expect a modularity close to zero in this case.
- First we generate a sample of 17 nodes, half the total number of nodes, and assign them to one community.
- Our second community then includes the nodes in the graph not in the first community.
- We can use some set arithmetic to do this concisely:
random_nodes = random.choices(list(K.nodes), k=17)
random_partition = [set(random_nodes),
set(K.nodes) - set(random_nodes)]
print(random_partition)[{5, 6, 7, 8, 9, 10, 11, 12, 14, 17, 21, 23, 28, 29, 30}, {0, 1, 2, 3, 4, 13, 15, 16, 18, 19, 20, 22, 24, 25, 26, 27, 31, 32, 33}]
Random partition: Visualize and compute modularity
We can visualize this partition and observe that the communities are much less natural-looking, as we would expect from a random assignment.
random_node_colors = ['orange' if n in random_nodes else 'lightblue' for n in K.nodes]
nx.draw(K, pos=nx.spring_layout(K), node_color=random_node_colors)And finally we can test the modularity of this partition:
print(nx.community.quality.modularity(K, random_partition))-0.057232810479563676
- Since this is a random process the modularity should be close to zero, as expected
Girvan-Newman clustering
Using NetworkX
Overview
- The Girvan–Newman algorithm detects communities by progressively removing edges from the original graph.
- The algorithm removes the “most valuable” edge, traditionally the edge with the highest betweenness centrality, at each step.
- As the graph breaks down into pieces, the tightly knit community structure is exposed
The result can be depicted as a dendrogram.- Finds communities in a graph using the Girvan–Newman method.
girvan_newman(G, most_valuable_edge=None)Input- Function that takes a graph as input and outputs an edge.
- The edge returned by this function will be recomputed and removed at each iteration of the algorithm.
Output- Iterator over tuples of sets of nodes in G.
- Each set of node is a community, each tuple is a sequence of communities at a particular level of the algorithm.
For more see https://networkx.org/documentation/stable/reference/algorithms/assortativity.html
Run algorithm
partition_sequence=list(nx.community.girvan_newman(K))
print(len(K.nodes),len(partition_sequence))
print("N_partitions, modularity")
NP=[]; MOD=[]; count=1
for partition in partition_sequence:
NP.append(len(partition))
MOD.append(nx.community.quality.modularity(K, partition))
if(count<10):
print(len(partition),nx.community.quality.modularity(K, partition))
count+=134 33
N_partitions, modularity
2 0.3476602762317048
3 0.3423192968647514
4 0.3580611307884035
5 0.3849721706864564
6 0.37578006409175235
7 0.3594760218136841
8 0.3470699574595678
9 0.33324900208017094
10 0.31344052772624204
Plot modularity vs community size
import matplotlib.pyplot as plt
plt.plot(NP,MOD,"o")
plt.ylabel('Modularity')
plt.xlabel('Number of communities')Text(0.5, 0, 'Number of communities')
Visualize Max modularity partition
- From the curve we can see the maximum modularity occurs with
FIVEpartitions
for partition in partition_sequence:
if len(partition) == 5:
five_cluster_partition = partition
break
print("NETWORK-X SOLUTION:",five_cluster_partition)
plot_partition(K,five_cluster_partition)NETWORK-X SOLUTION: ({0, 1, 3, 7, 11, 12, 13, 17, 19, 21}, {2, 24, 25, 27, 28, 31}, {4, 5, 6, 10, 16}, {32, 33, 8, 14, 15, 18, 20, 22, 23, 26, 29, 30}, {9})
Visualize partition with two communities
- Let’s isolate the partition from the partition_sequence with only TWO communities
for partition in partition_sequence:
if len(partition) == 2:
two_cluster_partition = partition
break
plot_partition(K,two_cluster_partition)Compare with ground truth
print(two_cluster_partition)
print("MODULARITY: ", nx.community.quality.modularity(K, two_cluster_partition))
print("\n",empirical_partition)
print("MODULARITY: ", nx.community.quality.modularity(K, empirical_partition))({0, 1, 3, 4, 5, 6, 7, 10, 11, 12, 13, 16, 17, 19, 21}, {2, 8, 9, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33})
MODULARITY: 0.3476602762317048
[{0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 16, 17, 19, 21}, {32, 33, 9, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31}]
MODULARITY: 0.39143756676224206
- Pretty good – comparable to the ground truth community labels.
- We can see that the predicted community labels are pretty accurate, only differing on a couple nodes that, visually, seem like they could plausibly belong to either group.
- Zachary’s original paper even explains the practical considerations of one of these mis-predicted nodes: student 8 was very near receiving his black belt from Mr. Hi and thus did not want to leave the group even though several of his friends did.
Girvan-Newman algorithm (optional)
Coding the algorithm “from scratch”
Summary
Our task in this part will be to implement the Girvan-Newman clustering algorithm.
Since NetworkX can do the heavy lifting for us – computing betweenness centrality – the code part of the task is relatively straightforward.
Most of our effort here is spent interpreting and explaining intermediate results.
Recall from the text the Girvan-Newman clustering algorithm:
- Create a partition sequence
- Calculate the betweenness centrality for all links.
- Remove the link with largest betweenness and create a partition using connected components.
- Recalculate the betweenness centrality of the links of the resulting graph.
- Repeat from step B until no links remain.
- Evaluate each partition in the sequence and choose the one with the highest modularity.
- During this process, the number of connected components in the graph will increase monotonically as clusters are broken up. Since we are removing one link at a time, the number of connected components can increase by at most one between steps in the sequence – it’s not possible for a single edge to connect more than two nodes, and thus components.
- We hope that the resulting partition of the graph will approximate its underlying community structure. We’ll use the Karate Club graph here because we know the ground-truth community labels and can compare the result obtained from the algorithm.
Setup
G = nx.karate_club_graph()
nx.draw(G)Create a partition sequence
A. Calculate the betweenness centrality for all links
NetworkX does the heavy lifting here. All we need to do is understand the output.
nx.edge_betweenness_centrality(G){(0, 1): 0.025252525252525245,
(0, 2): 0.0777876807288572,
(0, 3): 0.02049910873440285,
(0, 4): 0.0522875816993464,
(0, 5): 0.07813428401663694,
(0, 6): 0.07813428401663695,
(0, 7): 0.0228206434088787,
(0, 8): 0.07423959482783014,
(0, 10): 0.0522875816993464,
(0, 11): 0.058823529411764705,
(0, 12): 0.04652406417112298,
(0, 13): 0.04237189825425121,
(0, 17): 0.04012392835922248,
(0, 19): 0.045936960642843,
(0, 21): 0.040123928359222474,
(0, 31): 0.1272599949070537,
(1, 2): 0.023232323232323233,
(1, 3): 0.0077243018419489,
(1, 7): 0.007422969187675069,
(1, 13): 0.01240556828792123,
(1, 17): 0.01869960105254222,
(1, 19): 0.014633732280791102,
(1, 21): 0.01869960105254222,
(1, 30): 0.032280791104320514,
(2, 3): 0.022430184194890075,
(2, 7): 0.025214328155504617,
(2, 8): 0.009175791528732704,
(2, 9): 0.030803836686189627,
(2, 13): 0.007630931160342923,
(2, 27): 0.04119203236850296,
(2, 28): 0.02278244631185807,
(2, 32): 0.06898678663384543,
(3, 7): 0.003365588659706307,
(3, 12): 0.012299465240641705,
(3, 13): 0.01492233256939139,
(4, 6): 0.0047534165181224,
(4, 10): 0.0029708853238265,
(5, 6): 0.0029708853238265003,
(5, 10): 0.0047534165181224,
(5, 16): 0.029411764705882353,
(6, 16): 0.029411764705882353,
(8, 30): 0.00980392156862745,
(8, 32): 0.0304416716181422,
(8, 33): 0.04043657867187279,
(9, 33): 0.029615482556659026,
(13, 33): 0.06782389723566191,
(14, 32): 0.024083977025153497,
(14, 33): 0.03473955238661121,
(15, 32): 0.024083977025153497,
(15, 33): 0.03473955238661121,
(18, 32): 0.024083977025153497,
(18, 33): 0.03473955238661121,
(19, 33): 0.05938233879410351,
(20, 32): 0.024083977025153497,
(20, 33): 0.03473955238661121,
(22, 32): 0.024083977025153493,
(22, 33): 0.03473955238661121,
(23, 25): 0.019776193305605066,
(23, 27): 0.010536739948504653,
(23, 29): 0.00665478312537136,
(23, 32): 0.022341057635175278,
(23, 33): 0.03266983561101209,
(24, 25): 0.0042186571598336305,
(24, 27): 0.018657159833630418,
(24, 31): 0.040106951871657755,
(25, 31): 0.04205783323430383,
(26, 29): 0.004532722179781003,
(26, 33): 0.0542908072319837,
(27, 33): 0.030477039300568713,
(28, 31): 0.0148544266191325,
(28, 33): 0.024564977506153975,
(29, 32): 0.023328523328523323,
(29, 33): 0.029807882749059215,
(30, 32): 0.01705288175876411,
(30, 33): 0.02681436210847975,
(31, 32): 0.04143394731630026,
(31, 33): 0.05339388280564752,
(32, 33): 0.008225108225108224}
The resulting dictionary has edge tuples as the keys, and each associated value is the betweenness centrality of that edge. The algorithm to compute the edge betweenness of all edges in a graph costs about the same as calculating it for a single edge, so we’ll make use of this dictionary with the computed values for every edge.
Once computed for all edges, we can easily get the associated betweenness for a single edge. For example, to get the edge betweenness of the edge between nodes 0 and 1:
my_edge_betweenness = nx.edge_betweenness_centrality(G)
my_edge_betweenness[0, 1]0.025252525252525245
Recall that dictionaries also have the .get method. This will be used in the next step.
my_edge_betweenness.get((0, 1))0.025252525252525245
Remove the link with largest betweenness
Given this dictionary of betweenness values for each edge, we can make use of Python’s builtin max function to give us the key in this dictionary with the greatest value. Since there is a key in the dictionary for each edge in the graph, the following two expressions are equivalent, but the second one is probably more explicit as to what we’re doing with this statement.
I’m using the name my_edge_betweenness to make clear that this is a dictionary we’ve named and not a NetworkX function.
max(my_edge_betweenness, key=my_edge_betweenness.get)(0, 31)
max(G.edges(), key=my_edge_betweenness.get)(0, 31)
This is then the edge we want to remove at this step in the process:
my_edge_betweenness = nx.edge_betweenness_centrality(G)
most_valuable_edge = max(G.edges(), key=my_edge_betweenness.get)
G.remove_edge(*most_valuable_edge)The “splat” in the last statement above G.remove_edge(*most_valuable_edge) performs tuple unpacking into the arguments of a function. For example, if our most valuable edge is (0, 31),
G.remove_edge(*most_valuable_edge)
is the same as
G.remove_edge(most_valuable_edge[0], most_valuable_edge[1])
or
G.remove_edge(0, 31)
Create a partition using connected components
This one is almost a gimme because the nx.connected_components() function gives us almost exactly what we want:
nx.connected_components(G)<generator object connected_components at 0x11296a730>
We just have to remember to ask for it in a list:
list(nx.connected_components(G))[{0,
1,
2,
3,
4,
5,
6,
7,
8,
9,
10,
11,
12,
13,
14,
15,
16,
17,
18,
19,
20,
21,
22,
23,
24,
25,
26,
27,
28,
29,
30,
31,
32,
33}]
Remember: a partition is a list of sets where every node is in exactly one of these sets. This is just what we have here, although it’s a bit boring since we’ve only removed one edge and so there is still one connected component. If you like, you can try running the previous two cells a few times until you have more than one connected component so you can see what that looks like.
Note that this feature whereby the connected components correspond exactly to our putative community labels is particular to the Girvan-Newman algorithm: other clustering algorithms may use different ways of generating their partitions.
Recalculate the betweenness centrality
Repeat from step B until no links remain.
This implies that we need a loop to repeat this process \(L\) times, once for each edge, and that we should keep track of the partitions generated. Straightforward stuff. We’ll start with a fresh Karate Club graph since we removed some edges above:
G = nx.karate_club_graph()
partition_sequence = []
for _ in range(G.number_of_edges()):
my_edge_betweenness = nx.edge_betweenness_centrality(G)
most_valuable_edge = max(G.edges(), key=my_edge_betweenness.get)
G.remove_edge(*most_valuable_edge)
my_partition = list(nx.connected_components(G))
partition_sequence.append(my_partition)Note the idiomatic construction of this for loop. Using _ as the name for the loop variable tells the reader that we don’t expect to do anything with the loop variable – we just want to perform a task a specific number of times. One might be tempted to use a while loop here, but that way lie dragons: a mistake in a while loop can lead to infinite loops which are a headache.
If we’ve done this right, we should have a partition for each step of the process, i.e. one for each edge in the graph:
len(partition_sequence), nx.karate_club_graph().number_of_edges()(78, 78)
Since we started with a connected graph, removing one edge probably doesn’t disconnect the graph, so our first partition probably only has one community:
len(partition_sequence[0])1
…and the last partition should also be trivial, with each node in its own community:
len(partition_sequence[-1]), nx.karate_club_graph().number_of_nodes()(34, 34)
Evaluate the modularity
Do this for each partition in the sequence
We now have a sequence of partitions and a function to calculate the modularity of a partition. This is a great time to use a list comprehension!
G = nx.karate_club_graph()
modularity_sequence = [modularity(G, p) for p in partition_sequence]
print(modularity_sequence)231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
231
[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.34766027623170476, 0.34766027623170476, 0.34766027623170476, 0.3423192968647515, 0.3423192968647515, 0.3423192968647515, 0.3423192968647515, 0.3580611307884035, 0.3580611307884035, 0.3580611307884035, 0.3580611307884035, 0.3580611307884035, 0.3580611307884035, 0.38497217068645645, 0.37578006409175246, 0.37578006409175246, 0.3594760218136842, 0.3594760218136842, 0.3470699574595679, 0.3470699574595679, 0.333249002080171, 0.333249002080171, 0.3134405277262421, 0.3134405277262421, 0.3122598901819681, 0.3122598901819681, 0.3036862127771219, 0.3036862127771219, 0.2942973332583722, 0.2942973332583722, 0.2827158411573995, 0.2827158411573995, 0.27116245947414774, 0.27116245947414774, 0.2544648713479881, 0.2544648713479881, 0.2397537527407657, 0.2397537527407657, 0.22689792170311643, 0.22299057363992422, 0.22299057363992422, 0.22299057363992422, 0.20056783043796034, 0.20056783043796034, 0.18696238826108955, 0.18696238826108955, 0.18696238826108955, 0.16091340117314143, 0.16091340117314143, 0.16091340117314143, 0.14281029216094152, 0.14281029216094152, 0.11768894885778004, 0.11088622776934466, 0.10076647738985403, 0.08837915331421826, 0.08837915331421826, 0.05623957572009519, 0.04398343359382318, 0.04398343359382318, 0.04398343359382318, 0.011515901126290725, 0.011515901126290725, -0.003504432075860656, -0.031052641442251845, -0.031052641442251845, -0.04655085174565696, -0.05110473941642774]
Modularity plot
This sequence is then the modularity of the partition at each step in the algorithm. The first several entries in this sequence are effectively zero while there is only one community/component, then it jumps up once there is more than one community. We can use pyplot to visualize this relationship:
import matplotlib.pyplot as plt
plt.plot(modularity_sequence)
plt.ylabel('Modularity')
plt.xlabel('Algorithm step')Text(0.5, 0, 'Algorithm step')
Visualize partition with highest modularity
Visually, we see a peak in the modularity sequence. This is the partition that maximizes modularity, and thus the output of the algorithm.
- Write code to isolate the partition with highest modularity.
- Then plot the resultant partition
max_index=0
for i in range(0,len(modularity_sequence)):
if(modularity_sequence[i]==max(modularity_sequence)):
max_index=i
max_modularity=modularity_sequence[i]
#CHECK
print(max_index,max_modularity,max(modularity_sequence))
best_partition = partition_sequence[max_index]23 0.38497217068645645 0.38497217068645645
print(best_partition)[{0, 1, 3, 7, 11, 12, 13, 17, 19, 21}, {2, 24, 25, 27, 28, 31}, {4, 5, 6, 10, 16}, {32, 33, 8, 14, 15, 18, 20, 22, 23, 26, 29, 30}, {9}]
plot_partition(K,best_partition)Note
- Interesting! The partition of the karate club graph with highest modularity actually has five components!
- Let’s visualize them, using our code for partition maps we wrote back at the beginning of this tutorial:
def create_partition_map(partition):
partition_map = {}
for idx, cluster_nodes in enumerate(partition):
for node in cluster_nodes:
partition_map[node] = idx
return partition_mapbest_partition_map = create_partition_map(best_partition)
node_colors = [best_partition_map[n] for n in G.nodes()]
nx.draw(G, with_labels=True, node_color=node_colors)Exactly how good is this five-community clustering?
nx.community.quality.modularity(G, best_partition)0.3849721706864564
It’s higher than the “ground truth” communities we evaluated in section 3, which is a good sign, but for the specific problem of trying to predict the post-split community membership, a clustering into five groups is useless to us.
Get the best partition with a given number of communities
One of the most useful parts of the Girvan-Newman algorithm is that it is also useful when we have a specific number of clusters we want.
In this case, we know the karate club split into two groups, so let’s get the partition in the sequence with two components:
Aside
The astute reader might note that there may be several two-cluster partitions in the partition sequence we generated. We assert the following to be true:
- For every integer 1 to N, the number of nodes, there is a partition in the sequence with that number of clusters
- Every partition in the sequence with the same number of clusters is the same
Proving these is left as an exercise to the reader, but as a consequence of these being true, optimized implementations of Girvan-Newman clustering will only store one partition for each number of clusters. This is how the implementation in NetworkX works, only providing one partition for each number of communities greater than one.