Minimum Spanning Tree¶
The following is the input to the phylogeny example we saw in class. The distance matrix is given as an edge list and is stored in the csv file '1mst_data.csv'. We will use the csv package to use the file.
Following that, we will store the information into a networkx graph datastructure. The edges will be iterated over the iterator 'datareader', where each 'row' is a list containing the from_edge, to_edge and the value of the distance between them.
import warnings
warnings.filterwarnings('ignore')
import csv
import networkx as nx
G = nx.Graph()
with open('1mst_data.csv', newline='') as csvfile:
datareader = csv.reader(csvfile, delimiter=',')
for row in datareader:
G.add_edge(row[0],row[1],d=float(row[2]))
Let us now plot the input graph $G$.
import matplotlib.pyplot as plt
nx.draw_networkx(G,with_labels=True)
plt.show()
Next, we will find the minimum spanning tree $T$ of the graph $G$ and plot it. This will be done using network's inbuilt function, which uses Kruskal's algorithm. Note that the MST we find in this exercise is different from the one in the slides. The one from the slides is taken from another source, which is incorrect.
T = nx.minimum_spanning_tree(G,weight = 'd')
print(sum([T[i][j]['d'] for (i,j) in T.edges()]))
nx.draw_networkx(T,with_labels=True)
plt.show()
print("Number of edges in G is",len(G.edges()))
print("Number of edges in T is",len(T.edges()))
print("Is G a tree?",nx.is_tree(G))
print("Is T a tree?",nx.is_tree(T))
As seen in class, the number of edges in the tree is one less than the number of nodes.
Q1. Execute the clustering algorithm desribed in class. For a given value of $k$, find $k$ clusters in the minimum spanning tree.¶
Given $n$ nodes (=genes) and distance between all pairs of nodes, the clustering problem aims to partition the nodes into $k$ groups, such that the nodes in the same group are closer compared with nodes in different groups. Consider a clustering $C = \{C_1, \dots, C_k\}$, where $C$ partitions the nodes into $k$ groups. Then we can formulate the clustering problem as
maximize $D(C)$, where $D(C) = min_{i,j} D(C_i,C_j)$ and $D(C_i,C_j) = min_{u\in C_i, v\in C_j} d(u,v)$
The algorithm must be a function of the minimum spanning tree and $k$. Extract the clusters corresponding to the nodes in the connected components of the tree. The input values for $k$ are $\{3,4,5\}$, and the output must of $cluster_k$, which is a list of sets containing the $k$ clusters.
import csv
import networkx as nx
G = nx.Graph()
with open('1mst_data.csv', newline='') as csvfile:
datareader = csv.reader(csvfile, delimiter=',')
for row in datareader:
G.add_edge(row[0],row[1],d=float(row[2]))
T = nx.minimum_spanning_tree(G, 'd')
# ------- Your code here ---------
# ----------------
# print('3 clusters = \n',cluster(T,3))
# print('4 clusters = \n',cluster(T,4))
print('5 clusters = \n',cluster(T,5))
Q2. Test the accuracy of clustering algorithm using randomly generated graphs¶
We now test the algorithms using randonly generated graphs instances. These instances will follow a Stochastic Block Model. The idea behind SBM is that each instance created will have naturally ocurring clusters, and so it is useful to check to use SBMs to check how well the clustering algorithms can compute the predefined clusters.
Let the number of nodes $N=20$, and let $k=2$. Let nodes labelled $1$ through $10$ be in one cluster, while nodes labelled $11$ to $20$ be in another. We generate graphs such that for every pair of nodes, there exists an edge between them with a certain probability $p$. This probability is as follows: $p_{ij} = \frac{1}{2} + \alpha$ if nodes $i$ and $j$ are in the same cluster; and $\frac{1}{2} - \alpha$ otherwise. Further, we can also define the distance matrix as the following. For every pair of nodes $i$ and $j$, the distance $d_{ij}$ between them is the number of shared neighbors between them.
The first step is generate the graph using this model. The distances will be stored as an edge attribute to the graph datastructure. The input must be $N$ and $\alpha$.
import networkx as nx
import random
# --------- Your code here -----------
# -----------------------------
Next, generate the Minimum Spanning Tree and run the clustering algorithm in Q1.
G = generate_graph(20,0) # N=20, alpha = 0
T = nx.minimum_spanning_tree(G, 'd')
print(cluster(T,2))
The accuracy of the clustering algorithm will be measured by the following simple metric. $$\textrm{Accuracy} = \dfrac{\textrm{Number of nodes that are correctly clustered}}{N}.$$
Execute this below. The output must be a number between 0 and 1.
# ----- Your code here ------
# -----------------------
For different values of $\alpha \in \{0,0.125,0.25,0.375,0.5\}$, find the accuracies of the clustering algorithm. Plot the accuracy vs $\alpha$ in a graph.
alpha_list = [0,0.125,0.25,0.375,0.5]
acc_list = []
N = 20
# ----- Your code here ------
# -----------------------
plt.scatter(alpha_list, acc_list)
plt.show()
