大規模ネットワークに対する実用的クラスタ発見アルゴリズムの開発宇野毅明国立情報学研究所＆総合研究大学院大学（博士募集中） 2003年1月20日アルゴリズム研究会研究背景・ある種の部分グラフを見つけ出す・データマイニング、ウェブマイニング、計算言語学など・大量にほしい → 出てきたものをもう一度加工 → 統計的に処理（頻出度など） → 何かの候補（フィルタリング）・入力データは巨大・ウェブネットワーク・辞書・文書データベース例１：ウェブコミュニティーの発見（村田）対象：ウェブのネットワーク部分グラフ： 2部クリークリンク先：共通の話題に関するページリンク元：共通の話題を持つコミュニティー例2：類義語群の発見（中渡瀬）対象：単語の組合せからなる複合語の辞書部分グラフ： 2部クリーク関東地方関西地区中国電力北陸ある種似た意味を持つ単語の集合例3：類似論文のグループ化（相澤）対象：論文とそのアブストラクト部分グラフ：情報量の多い頂点集合（準クリーク）論文A 論文B 論文C 論文D 語：研究分野論文：その分野の論文語1 語2 語3 共通点・目的に合うように、ある種の目的関数を最適化する部分グラフを見つけている・現在使っているシステムは、かなり遅い（なんとかしたい）・厳密に最適解であることにはあまり意味がない・大量に、高速に求めたい・モデルが変化することがありうる今回扱った問題入力：大規模＆疎なグラフ G=(V,E) 問題１：高速かつ大量に極大（2部）クリークを求めよ問題２：高速かつ大量に評価値の大きい部分グラフ S を求めよ（最適でなくても良い：（準クリークと呼ぶ））枝重み wE ,頂点重み wV, 頂点数の関数 g(|S|) 評価値 f(S) ＝ ΣwE (u,v) + ΣwV (v) + g(|S|) u,v∈S, (u,v)∈E v∈S いろいろな評価値クリークにどれだけ近いか： 2 × S 内部の枝数／（頂点数） ×（頂点数－1）カット容量：頂点v の重み：＝－（ v に接続する枝のコストの総和）枝 e の重み：＝（ e のコストの2倍） S の重み＝ S から出て行く枝重みの総和（ S 内の枝 (u,v) の枝重みと、 u,v のコストがキャンセル）貪欲解法問題１の極大クリークは、貪欲解法で求められる・S=φ ・ S の全ての頂点に隣接するV＼S の頂点を、繰り返し加える・加えられなくなったら S を出力計算量： O(|E| |S|) 単純に計算すると、枝数が100万、 |S|=30 程度だと、 10 秒程度大量に計算するには時間がかかる貪欲解法の改良 U(S) ： S のすべての頂点に隣接する頂点の集合・S=φ ・ U(S) の頂点を Sに繰り返し加え、 U(S) を更新・ U(S) = φとなったら S を出力 U（S∪｛v｝） = ｛ u | ∀u∈U(S), (v,u)∈E ｝計算量： O（ Δ|S| ） (Δ ：最大次数 ) ・ Δ は高々100程度であるので、1/1000秒程度・ 2部クリークも、同じ方法でできる局所探索問題2の準クリークは、局所探索で求めると効率が良い N(S) ： S の近傍の集合 N(S) = ｛ X| ∃v, X=S∪v or X=S＼v ｝・S=φ ・ f(S') < f(S) になる S'∈N(S) に対して S=S’ とし、繰り返す・ S' が存在しなければ S を出力 1反復の計算量： O(|V|Δ) 頂点数が 10万くらいだと、 1反復 1秒程度最良の近傍を選ぶ・補助のデータを用意する（改善値と呼ぶ） f+(S,v) = wV(v) + Σ wE((u,v)) u∈S ・ S' ∈ N(S) に対して f(S') - g(|S'|) = f(S) - g(|S|) + f+(S,v) if S'=S∪ v f(S) - g(|S|) - f+(S,v) if S'= S＼v ・ S に含まれる頂点で f+(S,v) を最小にする頂点・ S に含まれない頂点で f+(S,v) を最大にする頂点のどちらかが N(S) 内で f() を最大化する ⇒ ヒープで保持すれば O(log |V|) 時間で見つかる改善値の変化・ S=S∪w か S= S＼w と更新したとする f+(S,v) = wV(v) + Σ wE((u,v)) u∈S ・ w及び w に隣接しない頂点は改善値が変化しない・ w に隣接する頂点 v は f+(S,v) + wE ((w,v)) に変化する ⇒ 更新にかかる時間は O( Δlog |V|) ・頂点数 10万なら log |V| ≦ 20、Δが100程度とすると 1反復の計算時間は1/500秒程度・ 2部グラフでも、同様にできる余談：タブーサーチへの応用・近傍の中から最良のものを短時間で見つけられるので、高速なタブーサーチが作れる計算実験・ C で作ってみると、おおよそ予想通りの計算時間で動いた・マシン：パソコン PentiumIII 500MHz ・ OS＆コンパイラ： Linux、gcc ・一般グラフでの問題を解いた（2部クリークではない）・解の精度は不明（そもそも最適解は求められない。原点は、「巨大なグラフで、どのようなことができるか」なので、気にしない）入力グラフと実行結果・一般のグラフ・各頂点の次数がほぼ同じになるランダムグラフ・ f =（頂点数＊平均次数）/2－（外に出る枝数）・それぞれの頂点を初期解として実行（頂点数回実行）入力グラフと実行結果クリーク頂点数枝数平均総計算次数時間総反復数極大 1000 30万 300 0.78 秒 6111 1万反復平均計算時間 6.1 秒極大 1万 1000万 1000 29 秒 46002 6.3 秒準 10万 1000万 100 462 秒 239万 1.9 秒準 100万 1000万 10 269 秒 799万 0.34 秒まとめと今後の展開・高速に極大クリーク、準クリークを大量に見つけるアルゴリズムを開発し、実装した・実際問題への適用・ web community の発見（村田）・類似語群の発見（中渡瀬）・大規模重み付きkカット問題（有限要素法計算の前処理）・論文のカテゴリー化（相澤）などなど