中国の噂（クラスタリング法）
チャイニーズ・ウィスパーズは、ネットワーク科学において用いられるクラスタリング手法の一種で、有名なウィスパリングゲームにちなんで名付けられました。[ 1 ]クラスタリング手法は、基本的に、特定のネットワーク内のノードまたはリンクのコミュニティを識別するために使用されます。このアルゴリズムは、2005年にクリス・ビーマンとスヴェン・テレスニアックによって設計されました。 [ 1 ]この名称は、このプロセスが、ノードが互いに同じ種類の情報を送信するコミュニティの分離としてモデル化できることに由来しています。 [ 1 ]
チャイニーズ・ウィスパーズは、ハードパーティショニング、ランダム化、フラットクラスタリング（クラスター間の階層関係がない）手法です。[ 1 ]ランダム性は、同じネットワーク上でプロセスを複数回実行した場合に異なる結果が生じる可能性があることを意味します。一方、ハードパーティショニングでは、1つのノードは特定の時点で1つのクラスターにしか属することができません。元のアルゴリズムは、無向グラフ、重み付きグラフ、重みなしグラフに適用できます。チャイニーズ・ウィスパーズは線形時間で実行されるため、ネットワーク内に非常に多くのノードとリンクがあっても非常に高速です。[ 1 ]
アルゴリズム
このアルゴリズムは無向無重みグラフでは次のように動作する：[ 1 ]
- すべてのノードは個別のクラスに割り当てられるため、初期クラスの数はノードの数と等しくなります。
- すべてのネットワークノードがランダムな順序で1つずつ選択されます。選択された各ノードのクラスターラベルは、そのノードとの接続数が最も多いクラスターに変更されます。接続数が同じ場合は、同じクラスターの中からランダムに1つが選択されます。
- ステップ2は、所定の反復回数に達するか、プロセスが収束するまで繰り返されます。最終的に、出現したクラスはネットワークのクラスターを表します。
反復回数に閾値を設けておく必要があるのは、プロセスが収束しない可能性があるためです。一方、約10000ノードのネットワークでは、収束しない場合でも、40～50回の反復処理後にはクラスターに大きな変化は見られません。[ 1 ]
強みと弱み
チャイニーズ・ウィスパーの最大の強みは、その時間線形性にあります。処理時間はノード数に比例して増加するため、このアルゴリズムはネットワーク内のコミュニティを非常に高速に識別することができます。このため、チャイニーズ・ウィスパーは、非常に多くのノードを持つグラフ内のコミュニティ構造を分析するのに適したツールです。ネットワークがスモールワールド特性を持つ場合、この手法の有効性はさらに高まります。[ 1 ]
一方、ノード数が少ない場合、このアルゴリズムは決定論的ではないため、結果として得られるクラスターは互いに大きく異なることがよくあります。これは、小規模なネットワークでは反復処理をどのノードから開始するかがより重要になるのに対し、大規模ネットワークでは開始点の関連性が失われるためです。[ 1 ]このため、小規模なグラフでは他のクラスタリング手法が推奨されます。
アプリケーション
チャイニーズ・ウィスパーズはネットワーク科学の多くの分野で利用されています。特に自然言語処理の問題の文脈でよく言及されています。[ 2 ] [ 3 ]一方、このアルゴリズムはネットワークフレームワークに関連するあらゆる種類のコミュニティ識別問題に適用可能です。チャイニーズ・ウィスパーズは、ネットワーク分析用に設計されたオープンソースプログラムであるGephi [ 4 ]の拡張パッケージとして個人利用が可能です。
参考文献
- ^ a b c d e f g h iクリス・ビーマン、「Chinese Whispers - 効率的なグラフクラスタリングアルゴリズムと自然言語処理問題への応用」、2006年
- ^ Antonio Di Marco - Roberto Navigili、「グラフベースの語義誘導によるWeb検索結果のクラスタリングと多様化」、2013年
- ^イオアニス・コルコンツェロス - スレシュ・マナンダール、「複数語表現における構成性の検出」、2009年
- ^ "「Gephiマーケットプレイス」. 2015年9月23日時点のオリジナルよりアーカイブ。2015年6月2日閲覧。
外部リンク
