MST-Based Clustering A minimum spanning tree of a weighted graph may be used for clustering with the following logic: a tree is acyclic and every edge of a tree is a bridge. Thus, removing an edge from the MST of a graph G divides G into two clusters and continuing in this manner provides clusters. We need to remove k − 1 heaviest edges from the MST of the graph to obtain k clusters. Since it is difficult to guess the value of k, a threshold τ may be used such that all edges that have a weight larger than τ are removed from the MST to form the clusters. The following steps of this algorithm can now be stated. 1. Input: A weighted graph G = (V, E, w), threshold τ . 2. Output: C = {C1,C2,...,Ck }, k clusters of G. 3. Find MST T of G. 4. Remove all edges from G that have a weight larger than τ . 5. Find the components of GN which are the clusters of G. Make Python Implementation
MST-Based Clustering
A minimum spanning tree of a weighted graph may be used for clustering with the
following logic: a tree is acyclic and every edge of a tree is a bridge. Thus, removing
an edge from the MST of a graph G divides G into two clusters and continuing in
this manner provides clusters. We need to remove k − 1 heaviest edges from the
MST of the graph to obtain k clusters. Since it is difficult to guess the value of k,
a threshold τ may be used such that all edges that have a weight larger than τ are
removed from the MST to form the clusters. The following steps of this algorithm
can now be stated.
1. Input: A weighted graph G = (V, E, w), threshold τ .
2. Output: C = {C1,C2,...,Ck }, k clusters of G.
3. Find MST T of G.
4. Remove all edges from G that have a weight larger than τ .
5. Find the components of GN which are the clusters of G.
Make Python Implementation
Step by step
Solved in 3 steps
