Yu Meichen, Hillebrand Arjan, Tewarie Prejaas, Meier Jil, van Dijk Bob, Van Mieghem Piet, Stam Cornelis Jan
Department of Clinical Neurophysiology and MEG Center, VU University Medical Center, PO Box 1081 HV, Amsterdam, The Netherlands.
Department of Neurology, VU University Medical Center, Amsterdam, The Netherlands.
Chaos. 2015 Feb;25(2):023107. doi: 10.1063/1.4908014.
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.
在复杂网络中识别聚类或群落是一个反复出现的问题。最小生成树（MST），即连接所有节点且总权重最小的树，被视为原始加权图的重要传输骨干。我们假设最小生成树的聚类揭示了加权图层次结构的见解。然而，现有理论和算法在定义和识别树中的聚类方面存在困难。在此，我们首先定义树中的聚类，然后提出一种用于检测最小生成树中聚类的树凝聚层次聚类（TAHC）方法。接着，我们证明TAHC方法能够检测人工树中的聚类，以及加权社交网络最小生成树中的聚类，这些聚类与先前报道的原始加权网络中的聚类一致。因此，我们的结果不仅表明可以在最小生成树中找到聚类，还表明最小生成树包含有关原始加权网络潜在聚类的信息。
