最小スパニングツリーでの階層クラスタリング

複雑なネットワークでのクラスターまたはコミュニティの識別は、再び登場する問題です。最小スパニングツリー（MST）、すべてのノードを最小合計重量で接続するツリーは、元の加重グラフの重要な輸送バックボーンと見なされます。MSTのクラスタリングは、加重グラフの階層構造の洞察を明らかにすると仮定します。ただし、既存の理論とアルゴリズムには、木のクラスターを定義および識別するのが困難です。ここでは、最初に木のクラスタリングを定義し、次にMSTSのクラスターを検出するためのツリー凝集階層クラスタリング（TAHC）メソッドを提案します。次に、TAHCメソッドが人工木のクラスターを検出し、また、クラスターが元の加重ネットワークの以前に報告されたクラスターと一致している加重ソーシャルネットワークのMSTを検出できることを実証します。したがって、我々の結果は、クラスターがMSTSで見つけることができることを示しているだけでなく、MSTには元の加重ネットワークの基礎となるクラスターに関する情報が含まれていることも示しています。

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.