assignment_3.zip (https://gatech.instructure.com/courses/485354/files/66888595?wrap=1)
(https://gatech.instructure.com/courses/485354/files/66888595/download?download_frd=1)
In the zip file above you will find:
A3.ipynb
: a Jupyter notebook (.ipynb) file
data/
: a directory called ‘data’ with one or more files
To complete this assignment, follow the steps below:
1.
Extract the contents into a local working directory (which we’ll refer to as LWD) on your machine
2.
Open your Conda CLI and navigate to your LWD
3.
Open Jupyter from the Conda CLI (a Jupyter interface should open in your default browser)
4.
Within the Jupyter interface, open the Jupyter notebook (.ipynb) file and follow the instructions provided there
5.
When you have completed all the work possible/desired:
with the exception of cells that include a single function definition that you added as utility function in the appropriatesection, delete any cells that you added that were not already part of the notebook (such as testing cells).
Extra cellscan sometimes trip up the autograder and require manual intervention. The smoother all the notebooks run, the soonerstudents can receive feedback.
run and rerun your entire notebook several times to make sure that there are no fatal errors such as improper syntax,etc
10/8/25, 10:59 AM Assignment 3
https://gatech.instructure.com/courses/485354/assignments/2133112 1/3
Assignment 3 Centrality and Community Detection
Do not add any additional cells in this assignment. If you write additional functions or print statements for testing, please remove them before submitting the assignment. Any additional functions must be defined inside the existing code cell, either as nested functions or inline with the current code. All code and comments should be written in between the lines ####IMPLEMENTATION STARTS HERE#### and ####IMPLEMENTATION ENDS HERE####. Please do not remove cell tags (e.g. ‘export’ and ‘test’).
Last updated: 2025 09 24
Imports
import copy
import math
import matplotlib.pyplot as plt # new since A1, A2
import networkx as nx
import numpy as np
import random
import scipy as sp
import seaborn as sns # new since A1, A2
from sklearn.metrics.cluster import normalized_mutual_info_score
Prepared Utility Functions
This section contains pre-written utility functions that you will use at certain points in the assignment. Please do not modify them.
def prep_util_custom_draw_basic(G:nx.Graph) -> None:
nx.draw_kamada_kawai(G, with_labels=True, node_size=700, font_size=7, node_color="#0f0f0f", edge_color="#909090", font_color="#f1f1f1")
plt.show()
def prep_util_erase_edge_data(G) -> None:
for u,v,data in G.edges(data=True):
data.clear()
def prep_util_load_lesson_graphs() -> (nx.Graph, nx.Graph, nx.Graph, nx.Graph):
"""
return
G_lesson_6 nx.Graph graph from CS 7280 Lesson 6: Eigenvector and The Katz Centrality
G_lesson_8 nx.Graph graph from CS 7280 Lesson 8: Overlapping Communities and CFinder Algorithm
G_lesson_8_a nx.Graph graph from CS 7280 Lesson 8: Critical Density Threshold in CFinder
G_lesson_8_b nx.Graph graph from CS 7280 Lesson 8: Critical Density Threshold in CFinder
"""
G_lesson_6 = nx.read_edgelist("data/lesson_6_graph_data.txt")
G_lesson_8 = nx.read_edgelist("data/lesson_8_graph_data.txt", nodetype=str)
G_lesson_8_a = nx.read_edgelist("data/lesson_8_graph_a_data.txt", nodetype=str)
G_lesson_8_b = nx.read_edgelist("data/lesson_8_graph_b_data.txt", nodetype=int)
return G_lesson_6, G_lesson_8, G_lesson_8_a, G_lesson_8_b
# DELETE BELOW FOR BLANK STUDENT NOTEBOOK
#for G in prep_util_load_lesson_graphs():
# print(G)
pass
def prep_util_jacaard_index(setA:set, setB:set) -> float:
"""
"""
return float(len(setA & setB))/float(len(setA | setB))
def prep_util_visualize_similarity_cent(G, n:int=1, net_name="", show_net=False, cmap_name="rocket") -> None:
"""
params
sim_mat
net_name
cmap_name
return
"""
if show_net:
prep_util_custom_draw_basic(G=G)
ticks = ['eigen','katz','page_rank','closeness','harmonic','betweenness','degree']
sim_mat = np.zeros(shape=(len(ticks),len(ticks)))
sim_mat = get_similarity_matrix_centrality(G=G, n=n)
cmap = sns.color_palette(cmap_name, as_cmap=True)
hm = sns.heatmap(sim_mat, annot=True, cmap=cmap, vmin=0., vmax=1.)
hm.set_xticklabels(ticks, fontsize=9)
hm.set_yticklabels(ticks, fontsize=9)
plt.xticks(rotation=90)
plt.yticks(rotation=0)
plt.title("Heatmap of Jaccard Similarity\n"+net_name+" network"+"\ntop "+str(n)+" nodes", fontsize=12)
plt.show()
def prep_util_visualize_similarity_comm_detect(
G,
k:int=2,
resolution=1.0,
net_name="",
show_net=False,
cmap_name="rocket"
) -> None:
"""
params
sim_mat
net_name
cmap_name
return
"""
if show_net:
prep_util_custom_draw_basic(G=G)
ticks = [
'greedy',
'k-clique',
'label_prop',
'louvain'
]
sim_mat = get_similarity_matrix_comm_detect(G=G, k=k, resolution=resolution)
cmap = sns.color_palette(cmap_name, as_cmap=True)
hm = sns.heatmap(sim_mat, annot=True, cmap=cmap, vmin=0., vmax=1.)
hm.set_xticklabels(ticks, fontsize=9)
hm.set_yticklabels(ticks, fontsize=9)
plt.xticks(rotation=90)
plt.yticks(rotation=0)
plt.title("Community Detection similarity (NMI)\n"+net_name+" network"+"\nk="+str(k)+" res="+str(resolution), fontsize=12)
plt.show()
def prep_util_visualize_similarity_comm_detect_ext(
G,
k:int=2,
resolution=1.0,
net_name="",
true_labels = [],
show_net=False,
cmap_name="rocket"
) -> None:
"""
params
sim_mat
net_name
cmap_name
return
"""
if show_net:
prep_util_custom_draw_basic(G=G)
ticks = [
'greedy',
'k-clique',
'label_prop',
'louvain',
'true',
]
sim_mat = get_extended_sim_mat_comm_detect(G=G, k=k, resolution=resolution, true_labels=true_labels)
cmap = sns.color_palette(cmap_name, as_cmap=True)
hm = sns.heatmap(sim_mat, annot=True, cmap=cmap, vmin=0., vmax=1.)
hm.set_xticklabels(ticks, fontsize=9)
hm.set_yticklabels(ticks, fontsize=9)
plt.xticks(rotation=90)
plt.yticks(rotation=0)
plt.title("Community Detection similarity (NMI)\n"+net_name+" network"+"\nk="+str(k)+" res="+str(resolution), fontsize=12)
plt.show()
def prep_util_visualize_nmis(network_ct:int=3) -> None:
color_greedy = '#fdae61'
color_k_clique = '#66c2a5'
color_label_prop = '#d53e4f'
color_louvain = '#3288bd'
value_dict = get_nmi_for_sweep(network_ct=network_ct)
mus = value_dict['mu']
nmis_greedy = value_dict['greedy']
nmis_k_clique = value_dict['k-clique']
nmis_label_prop = value_dict['label_prop']
nmis_louvain = value_dict['louvain']
plt.figure(figsize=(8,6))
plt.plot(mus, nmis_greedy, label="Greedy Modularity", color=color_greedy)
plt.plot(mus, nmis_k_clique, label="K-Clique", color=color_k_clique)
plt.plot(mus, nmis_label_prop, label="Label Propagation", color=color_label_prop)
plt.plot(mus, nmis_louvain, label="Louvain", color=color_louvain)
plt.scatter(mus, nmis_greedy, label="Greedy Modularity", color=color_greedy)
plt.scatter(mus, nmis_k_clique, label="K-Clique", color=color_k_clique)
plt.scatter(mus, nmis_label_prop, label="Label Propagation", color=color_label_prop)
plt.scatter(mus, nmis_louvain, label="Louvain", color=color_louvain)
plt.title("Normalized Mutual Information\nover mu sweep for\n" + str(network_ct) + " LFR benchmark networks")
plt.xlabel("mu (parameter in LFR benchmark)")
plt.ylabel("NMI (algorithm labels vs ground truth)")
plt.legend()
plt.show()
def prep_util_custom_draw_from_centrality(G:nx.Graph, centrality_fcn:callable, highlight_edges:list=[], pos:dict={}) -> None:
#G = copy.deepcopy(G)
G_nodes = list(G.nodes)
# Get edge colors before relabeling
edge_color_default = "#909090"
edge_color_highlight = "#ff0000"
edge_color = copy.deepcopy(edge_color_default)
if len(highlight_edges) > 0:
edge_color = []
G_edges = list(G.edges)
for e in G_edges:
#print("e : ", e, " : highlight_edges ", highlight_edges)
if e in highlight_edges or (e[1], e[0]) in highlight_edges:
edge_color.append(edge_color_highlight)
else:
edge_color.append(edge_color_default)
# Get the node : centrality value dictionary
node_val_dict = centrality_fcn(G)
# Relabel the nodes
relabeling_mapping = copy.deepcopy(node_val_dict)
for node in relabeling_mapping:
value = str(round(float(relabeling_mapping[node]),2)) + "\n" + str(node)
relabeling_mapping[node] = value
#nx.relabel_nodes(G, relabeling_mapping, copy=False)
# Get values of the dictionary and normalize (from 0.0 to 0.75 for node/label contrast)
vals = np.array(list(node_val_dict.values())).astype(float)
val_min = np.min(vals)
val_max = np.max(vals)
vals -= val_min
vals *= 0.75
vals /= (val_max-val_min)
# Initialize colormap
cmap = plt.cm.magma
# Get list of node colors based on normalized values
node_color_list = cmap(vals)
# Get list of node sizes based on normalized values
node_size_list = 1200*vals + 500
fig, ax = plt.subplots()
ax.axis('off')
if len(list(pos.keys())) > 0:
#new_pos = {}
#for node in G_nodes:
# new_pos[relabeling_mapping[node]] = pos[node]
nx.draw_networkx(G, pos=pos, ax=ax, with_labels=True, labels=relabeling_mapping, node_size=node_size_list, font_size=7, node_color=node_color_list, edge_color=edge_color, font_color="#f1f1f1")
else:
nx.draw_kamada_kawai(G, ax=ax, with_labels=True, labels=relabeling_mapping, node_size=node_size_list, font_size=7, node_color=node_color_list, edge_color=edge_color, font_color="#f1f1f1")
#ax.axis('off')
plt.show()
def prep_util_get_unique_communities(G) -> list:
node_community_dict = nx.get_node_attributes(G,'community')
communities = list(node_community_dict.values())
for i in range(len(communities)):
communities[i] = list(communities[i])
communities_unique = []
for community in communities:
if community not in communities_unique:
communities_unique.append(community)
return communities_unique
Part 1 [30 pts] Centrality metrics (similarity via Jacaard index)
In this part of the assignment, you will:
- set up tools to compare centrality metrics using Jacaard similarity
- use the tools to investigate the differences between the metrics
1.1 [4 pts] Setup -finder (for Katz centrality)
In the body of the function below,
- Return the eigenvalue of the parameter graph
Gwith the largest absolute value (ie, magnitude)
def compute_lambda(G) -> float:
"""
params
G nx.Graph or nx.DiGraph networkx graph (possibly directed, possibly weighted)
return
lamb float absolute value of the leading eigenvalue of G
"""
####IMPLEMENTATION STARTS HERE####
# This is a placeholder
lamb = 0.0
####IMPLEMENTATION ENDS HERE####
return lamb
Sanity check
Running the cell below should display the following:
Graph with 7 nodes and 8 edges : 2.832066…
Graph with 8 nodes and 12 edges : 3.282062…
Graph with 19 nodes and 26 edges : 3.361587…
Graph with 20 nodes and 41 edges : 4.729946…
# Run but do not modify
for G in prep_util_load_lesson_graphs():
print(G, " : ", compute_lambda(G))
1.2 [10 pts] Getting centrality values
In the body of the function below,
- Compute the eigenvector centrality of each node using NetworkX’s
eigenvector_centralityfunction. Store a dictionary with keys being the nodes and values being the eigenvector centrality of the node as the value in thecentrality_dictassociated with the keyeigen. Use theweight='weight'option, - Compute the Katz centrality of each node with NetworkX’s
katz_centrality_numpyfunction. Store a dictionary with keys being the nodes and values being the Katz centrality of the node as the value in thecentrality_dictassociated with the keykatz. Note that this function makes use of thecompute_lambdafunction from a subpart above. Use thealphavalue provided in the body of the function for the alpha argument in thekatz_centrality_numpyfunction. This is the only centrality metric where you will need to use the providedalpha. - Use the
prep_util_erase_edge_datafunction from the Prepared Utilities section to remove all edge data from the parameter graphG - Compute the PageRank of each node using NetworkX’s
pagerankfunction. Create and store a dictionary analogously to steps 1 and 2. - Compute the closeness centrality of each node using NetworkX’s
closeness_centralityfunction. Create and store a dictionary analogously to steps 1 and 2. - Compute the harmonic centrality of each node using NetworkX’s
harmonic_centralityfunction. Create and store a dictionary analogously to steps 1 and 2. - Compute the betweenness centrality of each node using NetworkX’s
betweenness_centralityfunction. Create and store a dictionary analogously to steps 1 and 2. - Compute the degree centrality of each node using NetworkX’s
degree_centralityfunction. Create and store a dictionary analogously to steps 1 and 2.
def get_centralities(G) -> dict:
"""
params
G nx.Graph or nx.DiGraph networkx graph (possibly directed, possibly weighted)
return
centrality_dict dictionary a dictionary of dictionaries
"""
# Do not modify the following two lines
lamb = compute_lambda(G)
alpha = (1./lamb)*0.9972
####IMPLEMENTATION STARTS HERE####
# This is a placeholder
centrality_dict = {
'eigen': {},
'katz': {},
'page_rank': {},
'closeness': {},
'harmonic': {},
'betweenness': {},
'degree':{},
}
####IMPLEMENTATION ENDS HERE####
return centrality_dict
1.3 [6 pts] Getting top values
In the body of the function below:
- Using the
get_centralitiesfunction from the subsection above, compute dictionaries for each of the keys'eigen', … - For each key (
'eigen', …), find thennodes with the largest corresponding centrality value usingnp.argpartition. Note: We recommend setting the appropriatekthparameter inargpartitionto move thenlargest valued nodes to the end of the result, then index the result to retrieve thosenlargest valued nodes - Store the
nnodes as a value in thetop_nodes_dictvariable associated with the appropriate key, with the nodes being stored in a set
def top_nodes(G, n:int=1) -> dict:
"""
params
G NetworkX Graph an arbitrary undirect graph
n int top n nodes to consider
return
top_nodes_dict dictionary a dictionary with
key : centrality algorithm name
value : a set of n nodes with the largest values for that algorithm
"""
####IMPLEMENTATION STARTS HERE####
# This is a placeholder
top_nodes_dict = {
'eigen': set(),
'katz': set(),
'page_rank': set(),
'closeness': set(),
'harmonic': set(),
'betweenness': set(),
'degree' : set(),
}
####IMPLEMENTATION ENDS HERE####
return top_nodes_dict
Sanity check
Running the cell below should yield the following output:
{9, 4, 15}
# Run but do not modify this cell
G_6, G_8, G_8a, G_8b = prep_util_load_lesson_graphs()
G_8b_top_nodes = top_nodes(G_8b,n=3)
print(G_8b_top_nodes['page_rank'])
1.4 [7 pts] Similarity matrix of centrality measures via Jacaard index
In the body of the function below:
- For each pair of centrality measures, compute the Jacaard similarity using the
prep_util_jacaard_indexstored in the Prepared Utility section of this assignment. - For each pair, store the computed value in the
sim_matvariable at the corresponding position based on the centrality measure pair. For example, the Jacaard index of the pair'eigen','page_rank'would be stored insim_mat[0,2]since the index of'eigen'in thetickslist is 0 and the index of'page_rank'in thetickslist is 2.
def get_similarity_matrix_centrality(G, n:int=3) -> np.array:
"""
params
G NetworkX Graph an arbitrary undirect graph
n int top n nodes to consider
return
sim_mat np.array similarity matrix (7 x 7 matrix)
"""
####IMPLEMENTATION STARTS HERE####
# These are placeholders
ticks = ['eigen','katz','page_rank','closeness','harmonic','betweenness','degree']
tick_ct = len(ticks)
sim_mat = np.zeros(shape=(tick_ct,tick_ct))
####IMPLEMENTATION ENDS HERE####
return sim_mat
Sanity check
Running the cell below should display the following:
[1. 1. 0.5 0.5 0.5 0.5 0.2]
[1. 1. 0.5 0.5 0.5 0.5 0.2]
[0.5 0.5 1. 1. 1. 1. 0.5]
[0.5 0.5 1. 1. 1. 1. 0.5]
[0.5 0.5 1. 1. 1. 1. 0.5]
[0.5 0.5 1. 1. 1. 1. 0.5]
[0.2 0.2 0.5 0.5 0.5 0.5 1. ]
# Run but do not modify this cell
G_6, G_8, G_8a, G_8b = prep_util_load_lesson_graphs()
sim_mat = get_similarity_matrix_centrality(G_8b,n=3)
for i in range(sim_mat.shape[0]):
print(sim_mat[i,:])
1.5 [3 pts] Conceptualization of similarity among centrality metrics
Run the cell below to setup small example graphs
# Run but do not modify
G_6, G_8, G_8a, G_8b = prep_util_load_lesson_graphs()
Run the cell below to see examples of how the centrality metrics compare via Jacaard similarity. Feel free to change the top number of nodes n and comment/uncomment the graph that you are interested in.
# Run and modify only in the ways indicated
############ choose a positive integer ###############
n = 1
############ comment/uncomment one line ##############
G, net_name = (G_6, "Lesson 6")
#G, net_name = (G_8, "Lesson 8")
#G, net_name = (G_8a, "Lesson 8a")
#G, net_name = (G_8b, "Lesson 8b")
########### do not modify below ######################
prep_util_visualize_similarity_cent(G=G, n=n, net_name=net_name, show_net=True)
Question: By choosing some n value of 1 or more (where n represents the top n nodes), it is possible to get a uniformly colored heatmap of Jacaard similarity among centrality metrics for a graph.
By uniformly colored, we mean that the Jacaard similarity between every pair of metrics is the same (all 1, or perfect overlap, for instance).
def response_1_5_uniform() -> str:
"""
return
return string statement that best answers the question
"""
# Uncomment the line below that best answers the question above
#return "False, because the value of n must be 0 or less"
#return "False, because the Katz and Eigenvalue centrality will always differ by at least one node"
#return "False, because the degree centrality is always larger than each other centrality"
#return "True, because if n is chosen to be large enough, the top n nodes will be all nodes for each metric"
#return "True, because connected graphs/networks will always have the same value ranking among their nodes no matter the centrality metric"
#return "True, because if a graph/network has a small enough diameter then each centrality will converge to the same value"
# Do not modify the line below (it will be overridden by whatever is uncommented above)
return "Yo"
Question: When n is set to 3 and the Lesson 8a network is examined, we see that the Jacaard similarity of the degree centrality and closeness centrality is 1 (the maximum possible value), meaning perfect overlap. This means that:
def response_1_5_deg_close() -> str:
"""
return
return string statement that best answers the question
"""
# Uncomment the line below that best answers the question above
#return "Whenever n is set to 3 in a graph with 3 or more nodes, the Jacaard similarity of degree and closeness centrality will be 1"
#return "The similarity is 1 only because the number of nodes n was chosen to be less than half of the total number of nodes"
#return "Closeness and degree similarity is a distinct feature of the Lesson 8 a graph and won't be aligned for every graph/network"
# Do not modify the line below (it will be overridden by whatever is uncommented above)
return "Yo"
Question: Consider the four lesson graphs loaded in this subsection. If n is kept at 3, the two distinct metrics that are most often in full alignment are:
def response_1_5_often_align() -> str:
"""
return
return string statement that best answers the question
"""
# Uncomment the line below that best answers the question above
#return "eigenvalue and Katz"
#return "eigenvalue and pageRank"
#return "eigenvalue and closeness"
#return "Katz and betweenness"
#return "Katz and pageRank"
#return "Katz and degree"
#return "degree and closeness"
#return "degree and betweenness"
#return "closeness and pageRank"
# Do not modify the line below (it will be overridden by whatever is uncommented above)
return "Yo"
Part 2 [30 pts] Community detection algorithms (similarity via NMI)
In this part of the assignment, we will set up tools for:
- Computing a suite of community partitions for any arbitrary network using various community detection algorithms, and
- Comparing the similarity of the algorithms using the normalized mutual information score on the partitions that the algorithms generate
2.1 [4 pts] Getting community partitions
In the body of the function below:
- For each of the indicated algorithms(Greedy modularity, K-clique, Label Propagation, and Louvain), use the associated
NetworkX community detection algorithmto compute the resulting communities and store them in a list in the indicated dictionary. Ignore the weight parameter in computing communities (let the default be used per Networkx).
def get_community_partitions(G:nx.Graph, k:int=6, resolution=1.0) -> dict:
"""
params
G NetworkX Graph an arbitrary undirected graph
k int argument for K-clique algorithm
resolution float argument used for greedy modularity and louvain algorithms
return
comm_part_dict dictionary dictionary with
key : community detection algorithm name
value : list of sets, with each set containing one or more node names
"""
####IMPLEMENTATION STARTS HERE####
# This is a placeholder
comm_part_dict = {
'greedy' : [],
'k-clique' : [],
'label_prop' : [],
'louvain' : [],
}
####IMPLEMENTATION ENDS HERE####
return comm_part_dict
Sanity check
Running the cell below should display the following
{2, 8, 9, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33}
{0, 1, 3, 4, 5, 6, 7, 10, 11, 12, 13, 16, 17, 19, 21}
# Run but do no modify
G_karate = nx.karate_club_graph()
comm_part_karate = get_community_partitions(G_karate, k=3, resolution=0.5555)
for part in comm_part_karate['greedy']:
print(part)
2.2 [10 pts] Getting community labels
In the body of the function below:
- Use the
get_community_paritionsfunction from the previous subsection to retrieve community lists for each of the four community detection algorithms at thekandresolutionvalues passed as arguuments, - For each community detection algorithm, iterate through
G_nodes. For each node, find the index of the community the node is contained in and store the community index in a list.- For example, if the communities of a graph were stored in a list as
[{"A", "D", "E"}, {"C"}, {"F","G","B"}], then the community index of node"B"would be 2, while the community index of node"A"would be 0. - If a node is not stored in any community, store a value of -1
- If a node is stored in multiple communities, store a value that is equal to the number of communities. For example, if the communities of a graph were stored in a list as
[{"A", "D", "E"}, {"C","D","B"}, {"F","G","B"}], then the community index of node"D"would be 3.
- For example, if the communities of a graph were stored in a list as
def get_community_labels(G:nx.Graph, k:int=6, resolution=1.0) -> dict:
"""
params
G NetworkX Graph an arbitrary undirected graph
k int argument for K-clique algorithm
resolution float argument used for greedy modularity and louvain algorithms
return
comm_label_dict dictionary dictionary with
keys : algorithm name
values : list of community labels for nodes
list length equal to number of nodes of G
"""
####IMPLEMENTATION STARTS HERE####
# Do not modify the line directly below
G_nodes = list(G.nodes)
# This is a placeholder
comm_label_dict = {
'greedy' : [],
'k-clique' : [],
'label_prop' : [],
'louvain' : [],
}
####IMPLEMENTATION ENDS HERE####
return comm_label_dict
Sanity check
Running the cell below should display the following
greedy : [1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] : 34
k-clique : [3, 0, 0, 0, 1, 1, 1, 0, 0, -1, 1, -1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 2, 2, 0, 0, 0, 0, 0, 3, 0, 0] : 34
label_prop : [0, 0, 1, 0, 0, 2, 2, 0, 1, 1, 0, 0, 0, 0, 1, 1, 2, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1] : 34
louvain : [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] : 34
# Run but do not modify
G_karate = nx.karate_club_graph()
comm_part_karate = get_community_labels(G_karate, k=3, resolution=0.5555)
for algo in comm_part_karate:
print()
print(algo, " : ", comm_part_karate[algo], " : ", len(comm_part_karate[algo]))
2.3 [8 pts] Similarity matrix of community partitions via NMI
In the body of the function below:
- Use the
get_community_labelsfunction to retrieve and store community labels for each of the four indicated community detection algorithms - Compute and return a matrix such that the -th entry is the normalized mutual information score between the labels of the -th and -th algorithms.
- For example, the -entry of the matrix would be the NMI between the K-clique and Label Propagation algorithms
- Use the
normalized_mutual_info_scorefunction from the SciKit-Learn library. This can be used after the Imports section cell has been run.
def get_similarity_matrix_comm_detect(G:nx.Graph, k:int=3, resolution:float=1.0) -> np.array:
"""
params
G NetworkX Graph an arbitrary undirected graph
k int argument for K-clique algorithm
resolution float argument used for greedy modularity and louvain algorithms
return
sim_mat np.array similarity matrix (4 x 4 matrix)
"""
####IMPLEMENTATION STARTS HERE####
# Don't modify the lines immediately below
ticks = [
'greedy',
'k-clique',
'label_prop',
'louvain'
]
tick_ct = len(ticks)
sim_mat = np.zeros(shape=(tick_ct,tick_ct))
####IMPLEMENTATION STARTS ENDS####
return sim_mat
Sanity check
Running the cell below should display the following
[[1. 0. 0.40742565 ??? ]
[0. 1. 0. 0. ]
[0.40742565 0. 1. ??? ]
[??? 0. ??? 1. ]]
# Run but do not modify
sim_mat = get_similarity_matrix_comm_detect(G=nx.karate_club_graph(), k=2, resolution=1.0)
print(sim_mat)
2.4 [6 pts] Extended similarity matrix
In the body of the function below
- Extend the
get_similarity_matrix_comm_detectmatrix by one row and one column to include NMI comparisons between the community detection algorithm labels and the true labels
def get_extended_sim_mat_comm_detect(G:nx.Graph, k:int=2, resolution:float=1.0, true_labels=[]):
"""
params
G NetworkX Graph an arbitrary undirected graph
k int argument for K-clique algorithm
resolution float argument used for greedy modularity and louvain algorithms
true_labels list true community labels (length equal to number of nodes of G)
return
ext_sim_mat np.array extended similarity matrix (5 x 5 matrix)
"""
####IMPLEMENTATION STARTS HERE####
# Do not modify the lines immediately below
algos = [
'greedy',
'k-clique',
'label_prop',
'louvain',
'true',
]
ext_sim_mat = get_similarity_matrix_comm_detect(G=G, k=k, resolution=resolution)
ext_sim_mat = np.append(ext_sim_mat, [[0,0,0,0]], axis=0)
ext_sim_mat = np.append(ext_sim_mat, [[0],[0],[0],[0],[0]], axis=1)
####IMPLEMENTATION ENDS HERE####
return ext_sim_mat
2.5 [2 pts] Community detection algorithm similarity to ground truth
Run the code cell below, modifying only the k and resolution arguments as indicated in the cell comments. Use the resulting visualization to answer the question in the response function below the visualization cell.
# Run
########### These values may be modified #############
k = 4
resolution = 0.8
########### Do not modify the lines below ############
G_karate = nx.karate_club_graph()
true_labels = [G_karate.nodes[v]['club'] for v in G_karate.nodes()]
prep_util_visualize_similarity_comm_detect_ext(
G=G_karate,
k=k,
resolution=resolution,
true_labels=true_labels,
)
Question: Through experimentation and observation, we find that the community detection algorithm which seems to best capture the ground truth communities of the Zachary’s Karate Club network is:
def response_2_5_best_for_zkc() -> str:
"""
return
return string statement that best answers the question
"""
# Uncomment the line below that best answers the question above
#return "Greedy modularity algorithm because no other algorithm manages to achieve higher NMI with the true labels"
#return "Greedy modularity algorithm because modifying the resolution allows it to achieve a NMI of 0.0"
#return "Greedy modularity algorithm because all greedy algorithms achieve a global maximum"
#return "K-clique algorithm because it uses the k parameter while the others use the inferior resolution"
#return "K-clique algorithm because there exists a certain k value greater than 2 and less than 10 such that it achieves the highest NMI with the true labels"
#return "K-clique algorithm because K-clique will achieves the highest NMI with true labels"
#return "Label propagation algorithm because it is conceptually related to message passing in graph neural networks"
#return "Label propagation algorithm because it passing information across edges"
#return "Label propagation algorithm because its NMI with the true labels is always larger than all the others for any given choice of k and resolution"
#return "Louvain algorithm because it achieves the highest NMI with the true labels over various reasonable selections of k and the resolution"
#return "Louvain algorithm because it uses the resolution parameter"
#return "Louvain algorithm because it always has a strictly larger NMI with the true labels than all the other algorithms"
# Do not modify the line below (it will be overridden by whatever is uncommented above)
return "Yo"
Part 3 [10 pts] Network centralization
In a previous part, we considered local centrality metrics, ie, the assignment of values to individual nodes. However, it would be useful if we could assign some kind of centrality measure to the network as a whole so that we can more directly compare networks. One such method was proposed by Freeman (1979).
3.1 [6 pts] Centralization algorithm
For three different centrality metric algorithms, we will follow Freeman’s method to compute the the corresponding centralization value of that algorithm.
In short, the Freeman method follows the steps below for a network and centrality metric :
- Compute the centrality metric value of all nodes in under
- Find the sum of differences between the centrality metric value of the highest value node in under and each other node in , calling the sum-difference
- Construct a star graph with the same number of nodes as
- Find the sum of differences for , calling it
- The centralization of is
In the body of the function below, compute the centralization value for each of the three listed algorithms, storing that value in the appropriate place in the output dictionary.
def get_centralization_values(G:nx.Graph) -> dict:
"""
params
G NetworkX Graph
return
network_cent_values dictionary dictionary with
keys : centrality algorithm names
values : centralization values for the algorithm
"""
####IMPLEMENTATION STARTS HERE####
# This is a placeholder
network_cent_values = {
'betweenness' : -1.0,
'closeness' : -1.0,
'degree' : -1.0,
}
####IMPLEMENTATION ENDS HERE####
return network_cent_values
Sanity check
If the function above has been completed properly, then the code cell below should produce the following output:
{'betweenness': 0.5111111111111112, 'closeness': 0.43952991452991447, 'degree': 0.4}
{'betweenness': 1.0, 'closeness': 1.0, 'degree': 1.0}
# Run but do not modify the contents of this cell
G_lesson_6 = prep_util_load_lesson_graphs()[0]
G_star_6 = nx.star_graph(len(list(G_lesson_6))-1, create_using=nx.Graph)
cent_vals_lesson_6 = get_centralization_values(G_lesson_6)
cent_vals_star_6 = get_centralization_values(G_star_6)
print()
print(cent_vals_lesson_6)
print()
print(cent_vals_star_6)
3.2 [1 pt] Node centrality versus network centraliztion (betweenness)
Run the code cell below to visualize:
- a graph shown in one of the lessons and
- the correponding star graph with the same number of nodes
with nodes colored and sized according to their betweenness centrality value (warmer colors and larger node size indicating a larger value). Use these visualizations to uncomment the correct answer to the response function of this sub-part.
# Run but do not modify the contents of this cell
G_lesson = prep_util_load_lesson_graphs()[0]
G_star = nx.star_graph(len(list(G_lesson))-1, create_using=nx.Graph)
prep_util_custom_draw_from_centrality(G_star, nx.betweenness_centrality)
print()
print("Lesson 6 graph")
print()
prep_util_custom_draw_from_centrality(G_lesson, nx.betweenness_centrality)
cent_vals_lesson = get_centralization_values(G_lesson)
print()
print("Betweenness centralization of the graph : ", cent_vals_lesson['betweenness'])
print()
# Run but do not modify the contents of this cell
G_lesson = prep_util_load_lesson_graphs()[1]
G_star = nx.star_graph(len(list(G_lesson))-1, create_using=nx.Graph)
prep_util_custom_draw_from_centrality(G_star, nx.betweenness_centrality)
print()
print("Lesson 8 graph")
print()
prep_util_custom_draw_from_centrality(G_lesson, nx.betweenness_centrality)
cent_vals_lesson = get_centralization_values(G_lesson)
print()
print("Betweenness centralization of the graph : ", cent_vals_lesson['betweenness'])
print()
In the body of the function below, uncomment the line that you think best answers the following question:
Question: We can see that the Lesson 8 graph has a higher betweenness centralization than the Lesson 6 graph. Why does this seem to be the case?
def response_3_2() -> str:
"""
return
return string statement that best answers the question
"""
# Uncomment the line below that best answers the question above
#return "Because the Lesson 8 graph has more nodes"
#return "Because the Lesson 8 graph has more edges"
#return "Because the Lesson 6 graph has a greater proportion of nodes with betweenness centrality close to the maximum value"
#return "Because the Lesson 6 graph has a greater proportion of nodes with betweenness centrality close to the minimum value"
#return "Because the two graphs have approximately equal maximum values"
#return "Because the characteristic path length of the Lesson 6 graph is 2"
#return "Because the characteristic path length of the Lesson 8 graph is 1"
# Do not modify the line below (it will be overridden by whatever is uncommented above)
return "Yo"
3.3 [1 pt] Node centrality versus network centraliztion (closeness)
Run the code cell below to visualize:
- a graph shown in one of the lessons and
- the correponding star graph with the same number of nodes
with nodes colored and sized according to their closeness centrality value (warmer colors and larger node size indicating a larger value). Use these visualizations to uncomment the correct answer to the response function of this sub-part.
# Run but do not modify the contents of this cell
G_lesson = prep_util_load_lesson_graphs()[0]
G_star = nx.star_graph(len(list(G_lesson))-1, create_using=nx.Graph)
prep_util_custom_draw_from_centrality(G_star, nx.closeness_centrality)
print()
print("Lesson 6 graph")
print()
prep_util_custom_draw_from_centrality(G_lesson, nx.closeness_centrality)
cent_vals_lesson = get_centralization_values(G_lesson)
print()
print("Closeness centralization of the graph : ", cent_vals_lesson['closeness'])
print()
# Run but do not modify the contents of this cell
G_lesson = prep_util_load_lesson_graphs()[3]
G_star = nx.star_graph(len(list(G_lesson))-1, create_using=nx.Graph)
prep_util_custom_draw_from_centrality(G_star, nx.closeness_centrality)
print()
print("Lesson 8b graph")
print()
prep_util_custom_draw_from_centrality(G_lesson, nx.closeness_centrality)
cent_vals_lesson = get_centralization_values(G_lesson)
print()
print("Closeness centralization of the graph : ", cent_vals_lesson['closeness'])
print()
In the body of the function below, uncomment the line that you think best answers the following question:
Question: We can see that the Lesson 8 b graph has a much lower closeness centralization than the Lesson 6 graph. Why does this seem to be the case?
def response_3_3() -> str:
"""
return
return string statement that best answers the question
"""
# Uncomment the line below that best answers the question above
#return "Because the Lesson 8 b graph has more nodes"
#return "Because the Lesson 8 b graph has more edges"
#return "Because the maximum value of the Lesson 6 graph is larger than the maximum of the Lesson 8 b graph"
#return "Because there are a greater proportion of nodes in the Lesson 8 b graph with values very close to the maximum"
#return "Because the diameter of the Lesson 6 graph is strictly less than the diameter of the Lesson 8 b graph"
#return "Because the radius of the Lesson 6 graph is strictly less than the diameter of the Lesson 8 b graph"
# Do not modify the line below (it will be overridden by whatever is uncommented above)
return "Yo"
3.4 [1 pt] Node centrality versus network centraliztion (degree)
Run the code cell below to visualize:
- a graph shown in one of the lessons and
- the correponding star graph with the same number of nodes
with nodes colored and sized according to their degree centrality value (warmer colors and larger node size indicating a larger value). Use these visualizations to uncomment the correct answer to the response function of this sub-part.
# Run but do not modify the contents of this cell
G_lesson = prep_util_load_lesson_graphs()[0]
G_star = nx.star_graph(len(list(G_lesson))-1, create_using=nx.Graph)
prep_util_custom_draw_from_centrality(G_star, nx.degree_centrality)
print()
print("Lesson 6 graph")
print()
prep_util_custom_draw_from_centrality(G_lesson, nx.degree_centrality)
cent_vals_lesson = get_centralization_values(G_lesson)
print()
print("Degree centralization of the graph : ", cent_vals_lesson['degree'])
print()
# Run but do not modify the contents of this cell
G_lesson = prep_util_load_lesson_graphs()[2]
G_star = nx.star_graph(len(list(G_lesson))-1, create_using=nx.Graph)
prep_util_custom_draw_from_centrality(G_star, nx.degree_centrality)
print()
print("Lesson 8 a graph")
print()
prep_util_custom_draw_from_centrality(G_lesson, nx.degree_centrality)
cent_vals_lesson = get_centralization_values(G_lesson)
print()
print("Degree centralization of the graph : ", cent_vals_lesson['degree'])
print()
In the body of the function below, uncomment the line that you think best answers the following question:
Question: We can see that the Lesson 8 a graph has a much lower degree centralization than the Lesson 6 graph. Why does this seem to be the case?
def response_3_4() -> str:
"""
return
return string statement that best answers the question
"""
# Uncomment the line below that best answers the question above
#return "Because the Lesson 8 a graph has more nodes"
#return "Because the Lesson 8 a graph has more edges"
#return "Because the Lesson 6 graph has more than one node with a maximum value whereas the Lesson 8 a graph only has one"
#return "Because the maximum value of the Lesson 6 graph is larger than the maximum of the Lesson 8 a graph"
#return "Because the diameter of the Lesson 6 graph is strictly less than the diameter of the Lesson 8 a graph"
#return "Because the radius of the Lesson 6 graph is strictly less than the diameter of the Lesson 8 a graph"
# Do not modify the line below (it will be overridden by whatever is uncommented above)
return "Yo"
3.5 [1 pt] Comparison of empirical networks using centralization
In body of the function below, using NetworkX’s read_weighted_edgelist function:
- Load the yeast network into the
G_yeastusing the specifications shown below in the table - Load the US airplane network into the
G_airportsusing the specifications shown below in the table - Return the two networks as a tuple (the yeast network first)
| Network | Relative filepath | create_using= |
|---|---|---|
| Yeast | "data/yeast_data.txt" |
nx.Graph |
| Airport | "data/airports_us_data.txt" |
nx.Graph |
def load_empirical_graphs() -> (nx.Graph, nx.Graph):
"""
return
G_yeast NetworkX Graph yeast network
G_airport NetworkX Graph US airport network
"""
####IMPLEMENTATION STARTS HERE####
# These are placeholder lines
G_yeast, G_airport = nx.Graph(), nx.Graph()
####IMPLEMENTATION ENDS HERE####
return G_yeast, G_airport
Sanity check
Running the cell below should display the following
Graph with 688 nodes and 1078 edges
Graph with 1574 nodes and 17215 edges
# Run this cell and compare to the sanity check above
for G in load_empirical_graphs():
print(G)
Run the cell below to see the centralization values of two empirical networks (Yeast network and US Airports network) for three different centrality algorithms (betweenness, closeness, and degree).
# Run this cell but do not modify its contents
G_yeast, G_airport = load_empirical_graphs()
centralizations_yeast = get_centralization_values(G_yeast)
centralizations_airport = get_centralization_values(G_airport)
print()
print("Centralizations of the YEAST network")
for metric in centralizations_yeast:
print(metric, " : ", centralizations_yeast[metric])
print()
print("Centralizations of the AIRPORT network")
for metric in centralizations_airport:
print(metric, " : ", centralizations_airport[metric])
For each of the questions below, use the centralization values found for the two empirical networks to uncomment the line in the function that best answers the corresponding question.
Question: The betweenness centralization values of the two empirical networks are relatively close in value. This means that:
def response_3_5_betweenness() -> str:
"""
return
return string statement that best answers the question
"""
# Uncomment the line below that best answers the question above
#return "There is nothing we can say about how the two networks compare"
#return "The two networks have the same number of nodes"
#return "The two networks have the same number of edges"
#return "The two networks have the same maximum betweenness value"
#return "The two networks have the same minimum betweenness value"
#return "The two networks have similar profiles in terms of the percentage of their nodes that are most often found along shortest paths"
# Do not modify the line below (it will be overridden by whatever is uncommented above)
return "Yo"
Question: The closeness centralization value of the airport network is much larger than that of the yeast network. This means that:
def response_3_5_closeness() -> str:
"""
return
return string statement that best answers the question
"""
# Uncomment the line below that best answers the question above
#return "There is nothing we can say about how the two networks compare"
#return "The two networks have the same number of nodes"
#return "The two networks have the same number of edges"
#return "The two networks have the same maximum closeness value"
#return "The two networks have the same minimum closeness value"
#return "There are more distinctive hubs in the airport network"
#return "There are more distinctive hubs in the yeast network"
# Do not modify the line below (it will be overridden by whatever is uncommented above)
return "Yo"
Question: The degree centralization value of the airport network is much larger than that of the yeast network. This means that:
def response_3_5_degree() -> str:
"""
return
return string statement that best answers the question
"""
# Uncomment the line below that best answers the question above
#return "It is likely that, when compared to the yeast network, the airport network has a small number of nodes with far larger degree than all the rest of the nodes"
#return "The two networks have the same number of nodes"
#return "The two networks have the same number of edges"
#return "The two networks have the same maximum degree value"
#return "The two networks have the same minimum degree value"
# Do not modify the line below (it will be overridden by whatever is uncommented above)
return "Yo"
Part 4 [30 pts] Community detection algorithms (comparison using LFR networks)
When comparing community detection algorithms to one another, there are broadly two ways to approach it:
- No info about ground truth communities. Compare the algorithms to one another without any reference to ground truth communities. This has some value, naturally, but it’s core strength comes from it being the sole thing one can do in the absence of information about such (ground truth) communities,
- Ground truth community info available. When ground truth community information is available, one can compare the resulting community assignments of the algorithms to the ground truth communities.
It might be clear at this point (or become clear as you work with more empirical networks), that (like most interesting things) ground truth communities are often not known. For instance, one cannot easily ask a dolphin what dolphin community they belong to. Thus, when it comes to comparing community detection algorithms, if we had a way to consistently access ground truth community information, that would be immensely helpful! It turns out that there is a network generation method that inherently provides ground truth community information as part of its generative process. Sweet!
4.1 [14 pts] Generate LFR network
The network generation method we will use was developed by Lancichinetti, Fortunato, and Radicchi ref 1, ref 2. The generation of the network is done to fit a set of pre-determined community parameter values and as such, provides a set of ground truth community assignments at the end of the generative process.
In the body of the function below:
- Generate a LFR network using NetworkX’s
LFR_benchmark_graphfunction with themuargument and all the hardcoded values in the body of the function already, such asn=500,tau1=2.5, and so on. - For each generated LFR network, compute and return community labels as such:
- Retrieve unique communities by running
prep_util_get_unique_communities(G)and store the result in a variableunique_communities - Iterate over each node in G.nodes. For each node, check which community in
unique_communitiescontains it - Append the index of that community to a list called
community_labels. - Note: Make sure only one community is appended for each node (the first community the node is found in)
def generate_lfr_network_and_labels(mu:float=0.1) -> (nx.Graph, list):
"""
params
mu float float between 0.1 and 1.0, used to generate LFR graph
return
G NetworkX graph LFR benchmark graph generated from mu, n, tau1, etc
community_labels list list of length equal to the number of nodes of G
"""
###########################################
# Do not modify the lines in this block
n = 500
tau1 = 2.5
tau2 = 2
min_degree = 3
min_community = 40
seed = 10
###########################################
####IMPLEMENTATION STARTS HERE####
####IMPLEMENTATION ENDS HERE####
return G, community_labels
Sanity check
Running the cell below should print the following:
Graph with 500 nodes and 2133 edges
[0, 1, 2, 1, 2, 3, 4]
# Run this cell but do not modify its contents
G, community_labels = generate_lfr_network_and_labels(mu=1.0)
print(G)
print(community_labels[:7])
4.2 [8 pts] Sweep of LFR networks over parameter
In the body of the function below:
- Compute a set of values based on the value of
network_ct.- The minimum value should be
0.1 - The maximum value should be
1.0 - Any additional networks should be evenly spaced between these values
- Numpy’s
linspacefunction is recommended
- The minimum value should be
- For each value, generate a LFR network and ground truth lavels using the
generate_lfr_network_and_labelsfunction from the preceeding subsection. Store themuvalue and network labels in their respective lists. - Return a list consisting of
(mu, network_label)pairs.
def sweep_of_lfr_networks_over_mu(network_ct:int=2) -> list:
"""
params
network_ct int number of different LFR networks in the sweep
return
mu_label_list list each entry is a tuple (mu, labels) where
mu is used to generate the LFR network and labels
labels are the resulting ground truth labels of the LFR network
"""
####IMPLEMENTATION STARTS HERE####
# This is a placeholder
mus, networks_labels = [], []
mu_label_list = []
####IMPLEMENTATION ENDS HERE####
return mu_label_list
Sanity check
Running the cell below should print the following:
0.55
Graph with 500 nodes and 2166 edges
[0, 1, 2, 1, 2, 3, 4]
# Run this cell but do not modify the contents
sweep = sweep_of_lfr_networks_over_mu(network_ct=3)
mu, G, labels = sweep[1][0], sweep[1][1][0], sweep[1][1][1]
print(mu)
print(G)
print(labels[:7])
4.3 [6 pts] Comparison of community detection algorithms over LFR sweep
In the body of the function below:
- Use the
sweep_of_lfr_networks_over_mufunction from the sub part above to get a set ofmuvalues and corresponding networks and their ground truth community labels. Store themuvalue in themusvariable. - For each
mu/network/label set, use theget_community_labelsfunction from Part 2 to get a set of community labels for each of the four algorithms (greedy modularity, k-clique, label propagation, and Louvain). - For each algorithm, compute the NMI between the ground truth labels and the algorithm labels. Store each NMI in the respective variable. For example, store the NMIs between the ground truth labels and greedy modularity algorithm in the
nmis_greedyvariable.
def get_nmi_for_sweep(network_ct:int=2) -> dict:
"""
params
network_ct int number of networks that will be generated
return
value_dict dictionary dictionary with
keys : 'mu', 'greedy', 'k-clique', 'label_prop', 'louvain'
values : lists of length network_ct
"""
####IMPLEMENTATION STARTS HERE####
# Do not modify the variable below
algos = [
'greedy',
'k-clique',
'label_prop',
'louvain'
]
# Do not modify these parameters
k, resolution = 4, 0.5555
# These are placeholders
mus = []
nmis_greedy = []
nmis_k_clique = []
nmis_label_prop = []
nmis_louvain = []
value_dict = {
'mu' : mus,
'greedy' : nmis_greedy,
'k-clique' : nmis_k_clique,
'label_prop' : nmis_label_prop,
'louvain' : nmis_louvain,
}
####IMPLEMENTATION ENDS HERE####
return value_dict
Sanity check
Running the cell below should yield the following output:
[0.1, 0.325, 0.55, 0.775, 1.0]
[0.7933061309658491, 0.2060860220561134, 0.0, 0.0, 0.0]
# Run but do not modify the contents of this cell
value_dict = get_nmi_for_sweep(network_ct=5)
print(value_dict['mu'])
print(value_dict['greedy'])
4.4 [2 pts] Algorithm performances over sweep
Run the cell below and observe how well the various algorithms align with the ground truth communities.
# Run this cell, but do not modify its contents
prep_util_visualize_nmis(network_ct=20)
Use the visualization above to answer the question below.
Question: Overall, the community detection algorithm that seems to best capture the ground truth communities is:
def response_4_4_best_perf() -> str:
"""
return
return string statement that best answers the question
"""
# Uncomment the line below that best answers the question above
#return "Greedy modularity because it tends to perform in the middle of all the other algorithms"
#return "Greedy modularity because it starts at a ranking of 3rd place when mu=0.1"
#return "K-Clique because it has a slower approach toward 0.0 NMI than all the other algorithms"
#return "K-Clique because it starts with the lowest NMI at mu=0.1"
#return "Label propagation because it reaches 0 NMI faster than all the others"
#return "Label propagation because it starts out with a relatively high NMI and maintains a high NMI for a short amount of time"
#return "Louvain because because it is not the last one to reach an effective NMI of 0"
#return "Louvain because it starts above the others and stays significantly above the rest for a moderate portion of the mu values"
# Do not modify the line below (it will be overridden by whatever is uncommented above)
return "Yo"
