Print Email Facebook Twitter Hierarchical clustering in minimum spanning trees Title Hierarchical clustering in minimum spanning trees Author Yu, M. Hillebrand, A. Tewarie, P. Meier, J. Van Dijk, B. Van Mieghem, P. Stam, C.J. Faculty Electrical Engineering, Mathematics and Computer Science Department Network Architectures and Services Date 2015-02-11 Abstract The identification of clusters or communities in complex networks is a reappearing problem. The minimum spanning tree (MST), the tree connecting all nodes with minimum total weight, is regarded as an important transport backbone of the original weighted graph. We hypothesize that the clustering of the MST reveals insight in the hierarchical structure of weighted graphs. However, existing theories and algorithms have difficulties to define and identify clusters in trees. Here, we first define clustering in trees and then propose a tree agglomerative hierarchical clustering (TAHC) method for the detection of clusters in MSTs. We then demonstrate that the TAHC method can detect clusters in artificial trees, and also in MSTs of weighted social networks, for which the clusters are in agreement with the previously reported clusters of the original weighted networks. Our results therefore not only indicate that clusters can be found in MSTs, but also that the MSTs contain information about the underlying clusters of the original weighted network. To reference this document use: http://resolver.tudelft.nl/uuid:513a62c4-f7a3-4c3e-91d1-84ac27779eb8 DOI https://doi.org/10.1063/1.4908014 Publisher AIP Publishing ISSN 1089-7682 Source Chaos 25, 023107 (2015) Part of collection Institutional Repository Document type journal article Rights (c) 2015 AIP Publishing LLC Files PDF Chaos2015_Hierarchical_cl ... g_MSTs.pdf 1.78 MB Close viewer /islandora/object/uuid:513a62c4-f7a3-4c3e-91d1-84ac27779eb8/datastream/OBJ/view