Abstract—Graph-theoretic clustering is one method of clustering where dataset is represented with a connected undirected graph having the distance between these points as the weights of the links between them. One approach is the construction of the Minimum Spanning Tree of said graph where the connected subgraphs formed after the removal of an inconsistent edge are the clusters. However, such methods suffer with drawbacks including partitioning without sufficient evidence and robustness to outliers. Hence, this work aims to modify the Prim’s MST-based clustering algorithm to produce a spanning tree of the dataset infusing the small-world network thereby invoking its properties (i.e. small mean shortest path length and high clustering coefficient) which manifest inherent or natural clustering characteristics.
Index Terms—Graph-theoretic clustering, minimum spanning tree, small world networks, clustering coefficient.
S. R. Lingaya is with the Technological Institute of the Philippines, Quezon City, Philippines (e-mail: srlingaya@tau.edu.ph, bobby.gerardo@gmail.com, ruji.medina@tip.edu.ph).
Cite: Small-World-Like Structured MST-Based Clustering Algorithm, "Sheila R. Lingaya, Bobby D. Gerardo, and Ruji P. Medina," International Journal of Machine Learning and Computing vol. 9, no. 4, pp. 477-482, 2019.
Copyright © 2019 by the authors. This is an open access article distributed under the Creative Commons Attribution License which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited (CC BY 4.0).