D-041 大規模社会ネットワークからのクラスタ構造の抽出(D分野:データベース)

情報処理学会

この論文をさがす

説明

Clauset, Newman, Mooreはネットワークをボトムアップかつ貪欲に解析する手法(CNMアルゴリズム)を提案し、50万ノード程度までの社会ネットワーク解析を可能としたが、それ以上の規模については実用的な時間内での解析は困難であった。そこでCNMアルゴリズムの合併の過程を観察した。その結果合併するクラスタサイズの不均衡が計算コストに大きく影響していることが明らかとなった。この観測から、合併するクラスタサイズの均衡がアルゴリズムの速度向上につながると考えた。本稿では、合併時のクラスタのサイズを考慮することにより合併比率を向上させる3種類の手法を提案する。提案手法の実験データセットとして、国内最大級のソーシャルネットワーキングサービスより2006年10月に取得した550万ユーザーの友人関係のネットワークを使用した。提案した3つの手法を用いたところ、CNMアルゴリズムに比べ劇的なスケーラビリティの向上がみられた。もっとも速度向上がみられた手法では、100万ノードに対して5分、400万ノードに対しては35分程度で解析する事に成功した。また別の手法では、50万ノードに対して50分(CNMアルゴリズムより7倍早い)で解析でき、モジュール性の向上にも成功した。

収録刊行物

詳細情報 詳細情報について

問題の指摘

ページトップへ