Hierarchical clustering in minimum spanning trees.
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.
Department of Clinical Neurophysiology and MEG Center, VU University Medical Center, PO Box 1081 HV, Amsterdam, The Netherlands.
Meichen
M
Yu
Department of Clinical Neurophysiology and MEG Center, VU University Medical Center, PO Box 1081 HV, Amsterdam, The Netherlands.
Arjan
A
Hillebrand
Department of Neurology, VU University Medical Center, Amsterdam, The Netherlands.
Prejaas
P
Tewarie
Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, PO Box 5031, 2600 GA, Delft, The Netherlands.
Jil
J
Meier
Department of Clinical Neurophysiology and MEG Center, VU University Medical Center, PO Box 1081 HV, Amsterdam, The Netherlands.
Bob
B
van Dijk
Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, PO Box 5031, 2600 GA, Delft, The Netherlands.
Piet
P
Van Mieghem
Department of Clinical Neurophysiology and MEG Center, VU University Medical Center, PO Box 1081 HV, Amsterdam, The Netherlands.
Cornelis Jan
CJ
Stam
D000465:Algorithms; D016000:Cluster Analysis; D008091:Literature