大規模ネットワークに対する 実用的クラスタ発見アルゴリズムの開発 宇野 毅明 国立情報学研究所 ＆　総合研究大学院大学（博士募集中） 2003年1月20日　アルゴリズム研究会

研究背景 ・ ある種の部分グラフを見つけ出す ・ データマイニング、ウェブマイニング、計算言語学など ・ 大量にほしい 　 ・ データマイニング、ウェブマイニング、計算言語学など ・ 大量にほしい 　　→ 　出てきたものをもう一度加工 　　→ 　統計的に処理（頻出度など） 　　→ 　何かの候補（フィルタリング） ・ 入力データは巨大 　 ・ ウェブネットワーク　 ・ 辞書　 ・ 文書データベース

対象： ウェブのネットワーク 部分グラフ： 2部クリーク リンク先： 共通の話題に関するページ リンク元： 共通の話題を持つコミュニティー 例１：ウェブコミュニティーの発見（村田） 対象：　ウェブのネットワーク 部分グラフ：　2部クリーク リンク先： 共通の話題に関するページ リンク元： 共通の話題を持つコミュニティー

対象： 単語の組合せからなる 複合語の辞書 部分グラフ： 2部クリーク ある種似た意味を持つ単語の集合 例2：類義語群の発見（中渡瀬） 関東 関西 中国 北陸 対象：　単語の組合せからなる 　　　　　複合語の辞書 部分グラフ：　2部クリーク ある種似た意味を持つ単語の集合 地方 地区 電力

対象： 論文とそのアブストラクト 部分グラフ： 情報量の多い頂点集合 （準クリーク） 語： 研究分野 論文： その分野の論文 例3：類似論文のグループ化（相澤） 論文A 論文B 論文C 論文D 対象：　論文とそのアブストラクト 部分グラフ：　 情報量の多い頂点集合 （準クリーク） 語：　研究分野 論文：　その分野の論文 語1 語2 語3

共通点 ・ 目的に合うように、ある種の目的関数を最適化する部分グラフを見つけている ・ 現在使っているシステムは、かなり遅い（なんとかしたい） ・ 厳密に最適解であることにはあまり意味がない ・ 大量に、高速に求めたい ・ モデルが変化することがありうる

今回扱った問題 u,v∈S, (u,v)∈E v∈S 入力： 大規模＆疎なグラフ 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 の頂点を、繰り返し加える 計算量：　 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－（外に出る枝数） ・ 各頂点の次数がほぼ同じになるランダムグラフ ・ f =（頂点数＊平均次数）/2－（外に出る枝数） ・ それぞれの頂点を初期解として実行（頂点数回実行）

入力グラフと実行結果 クリーク 頂点数 枝数 平均次数 総計算時間 総反復数 1万反復平均計算時間 極大 1000 30万 300 0.78 秒 6111 6.1 秒 1万 1000万 29 秒 46002 6.3 秒 準 10万 100 462 秒 239万 1.9 秒 100万 10 269　秒 799万 0.34 秒

まとめと今後の展開 ・ 高速に極大クリーク、準クリークを大量に見つけるアルゴリズムを開発し、実装した ・ 実際問題への適用 　・ web community の発見（村田） 　・ 類似語群の発見（中渡瀬） 　・ 大規模重み付きkカット問題（有限要素法計算の前処理） 　・ 論文のカテゴリー化（相澤） 　　　などなど