Hierarchical clustering in minimum spanning trees

Hierarchical clustering in minimum spanning trees

Yu, M.
Hillebrand, A.
Tewarie, P.
Meier, J.
Van Dijk, B.
Van Mieghem, P.
Stam, C.J.

Electrical Engineering, Mathematics and Computer Science

Network Architectures and Services

2015-02-11

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.

http://resolver.tudelft.nl/uuid:513a62c4-f7a3-4c3e-91d1-84ac27779eb8

https://doi.org/10.1063/1.4908014

AIP Publishing

1089-7682

Chaos 25, 023107 (2015)

Institutional Repository

journal article

(c) 2015 AIP Publishing LLC