ネットワークの階層的クラスタリング

階層的クラスタリングは、ネットワーク内のコミュニティ構造を見つける方法の 1 つです。この手法では、指定された重み関数に従って、ネットワークをグループの階層に整理します。その後、データは、デンドログラムと呼ばれるツリー構造で表すことができます。階層的クラスタリングは、アルゴリズムの実行中にネットワークにリンクを追加するか、ネットワークからリンクを削除するかによって、凝集型または分裂型になります。分裂型の手法の 1 つに、Girvan–Newman アルゴリズムがあります。

階層的クラスタリング アルゴリズムでは、まずネットワーク内の頂点の各ペアに重み が割り当てられます。重みは実装によって変わる可能性があり (以下のセクションを参照)、頂点の関連性の近さを示すことを目的としています。次に、ネットワーク内のすべてのノードが切断された状態で開始し、ペア間の重みが最も高いノードから最も低いノードまでペアリングを開始します (分割の場合は、元のネットワークから開始し、重みが最も低いリンクから最も高いリンクまでを削除します)。リンクが追加されると、接続されたサブセットが形成され始めます。これらは、ネットワークのコミュニティ構造を表します。 ${\displaystyle W_{ij}}$ ${\displaystyle (i,j)}$

各反復ステップのコンポーネントは常に他の構造のサブセットです。したがって、サブセットはツリー ダイアグラムまたはデンドログラムを使用して表すことができます。特定のレベルでのツリーの水平スライスは、重みの値の上と下に存在するコミュニティを示します。

階層的クラスタリング アルゴリズムで使用できる重みは多数あります。使用される特定の重みは、データと計算速度の考慮事項によって決まります。さらに、ネットワークで見つかるコミュニティは、重み付け関数の選択に大きく依存します。したがって、コミュニティ構造が既知の現実世界のデータと比較すると、さまざまな重み付け手法がさまざまな程度の成功を収めています。

これまでさまざまな成功を収めて使用されてきた 2 つの重みは、頂点の各ペア間のノード独立パスの数と、パスの長さで重み付けされた頂点間のパスの合計数です。ただし、これらの重みの欠点の 1 つは、両方の重み付けスキームが、これらの頂点に向かうパスの数が少ないため、単一の周辺頂点を正当なコミュニティから分離する傾向があることです。このため、階層的クラスタリング手法での使用は最適とはほど遠いです。^[1]

エッジ媒介中心性は、ガーバン・ニューマンアルゴリズムの重みとして効果的に使用されています。^[1]この手法は、重みが各ステップで再計算されることを除いて、分割階層型クラスタリングアルゴリズムに似ています。

ノードの追加によるネットワークのモジュール性の変化も重みとしてうまく利用されています。^[2]この方法は、Girvan-Newmanアルゴリズムと同様の結果をもたらしながら、計算コストの低い代替手段を提供します。

• ネットワークトポロジ
• 数値分類
• ツリー構造