import random
import scipy
import math
import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
from networkx.algorithms.community import k_clique_communities
from networkx.algorithms.community import greedy_modularity_communities
from networkx.algorithms.community import louvain_communities, louvain_partitions
from sklearn.metrics.cluster import adjusted_rand_score
from sklearn.metrics.cluster import mutual_info_score
plt.rcParams.update({
“figure.facecolor”: (1.0, 1.0, 1.0, 1.0), # red with alpha = 30%
“axes.facecolor”: (1.0, 1.0, 1.0, 1.0), # green with alpha = 50%
“savefig.facecolor”: (1.0, 1.0, 1.0, 1.0), # blue with alpha = 20%
Part 1: Centrality [30 points]¶
def load_graphs():
G_airport: NetworkX Graph Object
G_yeast: NetworkX Graph Object
return G_airport, G_yeast
def top_10_nodes(G):
G: NetworkX Graph Object
top_10_nodes_dict: dict[list[int]]
top_10_nodes_dict = {
‘eigen’: eigen,
‘katz’: katz,
‘page_rank’: page_rank,
‘closeness’: closeness,
‘harmonic’: harmonic,
‘betweeness’: betweeness
return top_10_nodes_dict
def calculate_similarity_matrix(top_nodes_dict):
top_nodes_dict: dict[list[int]]
similarity_matrix: np.array
return similarity_matrix
def plot_similarity_heatmap(similarity_matrix, data_name, save=False):
similarity_matrix: np.array
data_name: str
plt.figure(figsize=(7, 7))
plt.show()
plt.savefig(f'{data_name}_similarity_matrix.png’)
plt.close()
# Load the networks
G_airport, G_yeast = load_graphs()
# Get the top nodes
top_airport_nodes = top_10_nodes(G_airport)
top_yeast_nodes = top_10_nodes(G_yeast)
# Generate the similarity matrcies
node_similarity_airport = calculate_similarity_matrix(top_airport_nodes)
node_similarity_yeast = calculate_similarity_matrix(top_yeast_nodes)
# Generate the heatmaps
plot_similarity_heatmap(node_similarity_airport, ‘Airport’)
plot_similarity_heatmap(node_similarity_yeast, ‘Yeast’)
Written Response for 1.4¶
Part 2: Community Detection with Zachary’s Karate Club [25 points]¶
def compute_cfinder_communities(G, k):
Inputs: G: NetworkX Graph Object
community_assignments: list[int]
return community_assignments
def compute_greedy_communities(G):
Inputs: G: NetworkX Graph Object
community_assignments: list[int]
return community_assignments
def compute_louvain_communities(G):
Inputs: G: NetworkX Graph Object
community_assignments: list[int]
return community_assignments
def plot_network_communities(G, community_assignments, algorithm_name, save=False):
G: NetworkX Graph Object
community_assignments: list[int]
algorithm_name: str
random.seed(1)
np.random.seed(1)
plt.figure(figsize=(5, 5))
plt.show()
plt.savefig(f’karate_communities_{algorithm_name}.png’)
plt.close()
G = nx.karate_club_graph()
ground_truth = [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]
# Chose a reasonable value for k in the cfinder algorithm
cfinder_assignments = compute_cfinder_communities(G, k=4)
greedy_assignments = compute_greedy_communities(G)
louvain_assignments = compute_louvain_communities(G)
# Compare resulting community assignments with the ground truth
plot_network_communities(G, ground_truth, ‘Ground Truth’)
plot_network_communities(G, cfinder_assignments, ‘C-Finder’)
plot_network_communities(G, greedy_assignments, ‘Greedy Modularity’)
plot_network_communities(G, louvain_assignments, ‘Louvain’)
Written Response for 2.3¶
Part 3: Community Detection with LFR Networks [25 points]¶
# Generating the LFR Benchmark Network
def generate_lfr_benchmark(mu):
G: NetworkX Graph Object
community_assignments: list[int]
tau1 = 2.5
min_degree = 3
min_community = 40
return G, community_assignments
def normalized_mutual_information(y_true, y_pred):
y_true: list[int]
y_pred: list[int]
NMI: float
return NMI
def sweep_mu_values():
greedy_nmis: list[float]
louvain_nmis: list[float]
return greedy_nmis, louvain_nmis
def plot_nmi_values(greedy_nmis, louvain_nmis, save=False):
greedy_nmis: list[int]
louvain_nmis: list[int]
plt.figure(figsize=(8,6))
plt.show()
plt.savefig(‘3_4.png’)
plt.close()
greedy_nmis, louvain_nmis = sweep_mu_values()
plot_nmi_values(greedy_nmis, louvain_nmis)
Written Response for 3.5¶
Part 4: Community Detection on Real World Data [15 points]¶
def calculate_community_sizes(G):
G: NetworkX Graph Object
greedy_sizes: list[int]
louvain_sizes: list[int]
return greedy_sizes, louvain_sizes
def plot_community_size_distributions(greedy_sizes, louvain_sizes, data_name, save=False):
greedy_sizes: list[int]
louvain_sizes: list[int]
data_name: str
plt.figure(figsize=(8,6))
plt.show()
plt.savefig(‘4_2.png’)
plt.close()
G_airport, G_yeast = load_graphs()
greedy_sizes, louvain_sizes = calculate_community_sizes(G_airport)
plot_community_size_distributions(greedy_sizes, louvain_sizes, ‘Airport’)
greedy_sizes, louvain_sizes = calculate_community_sizes(G_yeast)
plot_community_size_distributions(greedy_sizes, louvain_sizes, ‘Yeast’)
Written Response for 4.3¶
Response for 5¶
Partition 1:¶
Modularity:
Partition 2:¶
Modularity:
Partition 3:¶
Modularity:
Partition 4:¶
Modularity: