大規模2部グラフに対する
極大クリーク列挙アルゴリズムの
改良と実装
宇野 毅明
国立情報学研究所
& 総合研究大学院大学(博士入学者募集
中)
2003年3月14日 アルゴリズム研究会
新旧アルゴリズムの比較2
10000
8000
既存 r=10
提案 r=10
既存 r=30
提案 r=30
次数巨大あり
6000
4000
2000
0
10
00
33
50
66 7
01
98 5
52
13 1
10
16 27
35
19 33
60
22 41
85
47
1万個あたりの計算時間(秒)
既存と提案手法の比較
頂点数
列挙がしたい
・ ある種の部分グラフを見つけ出す
データマイニング、ウェブマイニング、計算言語学など
・ 大量にほしい
→ 出てきたものをもう一度加工
→ 統計的に処理
→ 出現数を調べる(グラフマイニング)
→ クラスタの種にする(計算言語学)
・ 入力データは巨大
・ ウェブネットワーク ・ 辞書 ・ 文書データベース
可能であれば、全部列挙したい
グラフマイニング
・ 与えられた大きなグラフ、あるいはたくさんのグラフの中か
ら、頻出する部分グラフを出力する
・ 部分グラフ =
木、サイクル、クリークなど
・ 候補を作り、列挙して勘定する
アルゴリズムが一般的
・ クリーク、2部クリークは、
極大なものを列挙すれば、後が簡単
問題の定義
・ 与えられたグラフ G = (V,E ) に対して、
「 G の全ての極大クリーク(極大2部クリーク)を、ちょうど一度
ずつ出力せよ(列挙せよ)」
・ G の補グラフを G' とすると、上記の問題は G' の極大安定集
合を列挙する問題と等価
・ G の極大安定集合: 築山らのアルゴリズムで、ひとつあたり
O(|V||E| ) 時間で列挙できる
極大安定集合列挙
・ 極大安定集合列挙アルゴリズムは、斬新なアイディアで作られ
ている
※ それまでのアルゴリズムは、分割法とバックトラッキング
極大安定集合は列挙できない (出力多項式時間では)
・ 95年にAvis・福田が提案した逆探索と同じ探索をしている
・ 00-01年中野により、いくつかのグラフオブジェクトに対し、この
アルゴリズムと同じ方法の、効率良い列挙アルゴリズムが提
案されている
しかし、
問題が基礎的な割には、計算量が大きい
しかし、改良は難しい
今回の研究テーマ
・ データマイニングなどでは、疎なグラフを扱うこと
が多い
(しかも極端に疎、
頂点数=1万、 平均次数=10、 など )
 入力グラフが疎である場合に(実用的に)高速
なアルゴリズムを開発したい
極大クリークの逆探索
・ 築山らの列挙法を、極大クリークに適用
V = { v1,…,vn }, Vi = { v1,…,vi } とする
グラフ Gi =(Vi, E ) の極大クリークを
i 極大クリーク と呼ぶ
全ての i 極大クリークを列挙する、という問題を考える
(そして、普通の極大クリークだけ出力する)
逆探索による列挙
・ (ある1つの以外の)任意の解に, 親(他の解)を定義
( i 極大クリークの親を( i-1 )極大クリークで定める )
・ ただし, 各解が自分自身の真の先祖にならないこと
この親子関係は 列挙木 を導出する
…
V1 ={v1}
V2 ={v1,v2} ,…, Vn-1 ={v1,…,vn-1} V ={v1,…,vn}
列挙木を深さ優先探索してすべての解を出力する
極大クリークの親
i 極大クリーク S に対してその親を
(i-1) 極大クリーク S' で定める。ただし、
1. vi が S に含まれなければ S' = S
2. そうでなければ S' = S \ { vi } に極大クリークに
なるまで、添え字の昇順で頂点を加えたもの
・ だれも、自分の真の先祖にならない
・ 1 極大クリーク{v1} だけ親を持たない
親子関係は {v1} を根とする木になる (列挙木)
列挙木を探索
列挙木を(深さ優先)探索し、全ての頂点を訪れれば、すべ
ての i-極大マッチングが列挙できる
(  逆探索)
木自体をメモリに持つ
 極大マッチングを
列挙しなければならない
 指数メモリが必要
・ 深さ優先探索をするには、
今訪れている頂点の子供が得られれば十分
与えられた親の子供を見つけるアルゴリズムを考える
子供を求める
・ i 極大クリーク S に対して
1. vi+1 が S のすべての頂点に隣接する : S' = S∪{vi+1} 、
隣接しない頂点がある : S' = S
 i+1 極大クリーク S' は S の子供になる
( type1 )
( type 1 の子供は必ず存在する )
2. S' = (S ∪{ vi+1 } から vi+1 に隣接しない頂点を取り除いたもの)
 S' が極大クリーク&親が S ならば
i+1 極大クリーク S' は S の子供
( type2 )
・ i+1 極大クリーク S' が S の子供であれば、
必ずどちらかの方法で求められる
1反復の計算時間
・ i 極大クリーク S に対して
type 1 S' = S か S' = S ∪{ vi+1 }
type 2 S' = ( S ∪{vi+1 } から vi+1 に隣接しない頂点を取
り除く)
 O(Δ) 時間で得られる
type 2 の子供であるかどうかのチェック
 O(Δ2)
( ※ Δはグラフの最大次数)
計算量を算定
任意の i極大クリークは ( i<|V| なら ) 子供を1人は持つ
 高々|V| 回反復すれば、ひとつ極大クリークが出力される
 1つあたりの計算時間は O(Δ2|V|)
もう少し詳しく解析すると、 O(|V| |E| )
・ type 1 の子供をたどり、一番下まで行くには O(Δ2) 時間しか
かからない
・ type 2の子供に関する作業を高速化したい
反復数を少なくする
・ type 2 S' = (S ∪{ vi+1 } から vi+1 に
隣接しない頂点を取り除く)
・ vi+1 が S のどの頂点とも隣接してない
 S' = { vi+1 }
type 2 子供になっている1頂点の i極大クリークは別口で列挙
 vi+1が S に隣接してないなら、 type 2 子供のチェック不要
 type 2 の子供のチェックは、 S に隣接する頂点のみにつ
いて行えばよい
Type 2 の子供の計算時間
・ type 2 子供のチェックは、 S に隣接する頂点のみ
・ type 2 子供を求める時間
 Δ × ( vi+1 に隣接する S の頂点数)
・ S の頂点に接続する枝数  高々Δ2
・ type 1 子供をたどる反復の中で、
・ vi+1 が S に隣接する  高々Δ2 個
 必要な反復は O(Δ2 )
・ type 2 子供候補を求める総時間  O(Δ3 )
極大クリーク1つあたり、 O(Δ4 ) 時間
( 実際は O(Δ2 ) 程度であろう )
2部クリーク
・ 2部グラフに定義
・ 頂点集合1の頂点同士、頂点集合2の頂点同士には枝
がなくてよい
・ 任意の頂点集合1の頂点同士、
頂点集合2の頂点同士に枝をはると
一般のクリークの問題に帰着される
 グラフが疎でなくなるので、ダメ
特別扱いをする必要がある
自明なクリーク
・ 頂点集合1、頂点集合2の部分集合はクリークになる
(自明なクリーク)
頂点数が多いので、反復にかかる時間が増大
(これらが type 2 子供の候補になりうる)
・ 自明なクリークは探索しない
 親が自明なクリークであるものを、見つけそこなう
親が自明なクリークの場合
・ 添え字のつけ方を、
まず頂点集合1
次に頂点集合2
という順番でつける
・親が自明なクリーク
 v ∈ 頂点集合2 と、 v に隣接する頂点集合1の頂点のみ
か、自分も自明なクリーク
こういうものだけ、別口で列挙する
反復の省略
・ vi+1 がi 極大2部クリーク S に隣接しない
 type 2 の子供は(存在すれば)必ず
v ∈ 頂点集合2 と、 v に隣接する頂点集合1の頂点のみ
 これらは別口で発生
・ vi+1 が S に隣接するときのみ、 type 2 の
子供のチェックをすればよい
計算時間の算定
・ vi+1 に関する type 2 の子供チェックの時間
vi+1 と S に接する枝数 × Δ
・ S に接する枝数  高々Δ2
極大2部クリーク1つあたり、 O(Δ3 ) 時間
1部頂点の次数が大きい
・ 一部の頂点 X の次数がとても大きい
( |X| は小さいとする)
・ X のみからなるクリークは別口で
 現在の解S ⊆ X ならやめる
 S には X 以外の頂点あり
 S の全てに隣接する頂点 ≦ Δ
X に隣接行列用意すれば、計算量は変わらず
計算実験
・言語:
・ マシン:
・ OS&コンパイラ:
C
パソコン PentiumIII 500MHz
Linux、gcc
・ 一般グラフ、2部グラフの問題を解いた
・ 通常のランダムグラフでは面白い実験ができないので、
添え字が近い頂点にしか枝を張らないランダムグラフを作っ
た。
新旧アルゴリズムの比較
30000
25000
既存 r=10
提案 r=10
既存 r=30
提案 r=30
次数巨大あり
20000
15000
10000
5000
0
10
00
30
00
50
00
70
00
90
00
16
00
64 0
00
25 0
60
00
1万個あたりの計算時間(秒)
既存と提案手法の比較
頂点数
新旧アルゴリズムの比較2
10000
8000
既存 r=10
提案 r=10
既存 r=30
提案 r=30
次数巨大あり
6000
4000
2000
0
10
00
33
50
66 7
01
98 5
52
13 1
10
16 27
35
19 33
60
22 41
85
47
1万個あたりの計算時間(秒)
既存と提案手法の比較
頂点数
3500
3000
2500
既存
提案
既存
提案
2000
1500
1000
500
0
10
00
30
00
50
00
70
00
90
00
16
00
0
64
00
25 0
60
00
1万個あたりの計算時間(秒)
2部グラフの場合
頂点数
r=10
r=10
r=30
r=30
次数の変化に対する挙動
1000
100
10
1
10
20
40
80
0.1
※ だいたい、次数の2乗に比例
160
320
現実のデータに適用
・ とある計算言語学のデータに適用
頂点数およそ2万:2万、枝数24万(平均次数6)の2部グラフ
(次数に偏りあり) 極大クリーク数270万
計算時間=1500秒 (1万個あたり6秒)
(既存=4000時間くらい?)
・ とあるデータマイニングのデータに適用
頂点数およそ6万:500、枝数15万の2部グラフ
(次数に偏りあり) 極大クリーク数14万
計算時間=266秒 (1万個あたり19秒)
(既存=30時間くらい?)
まとめと今後の展開
・ 疎グラフの極大クリーク、極大2部クリークを列挙するアル
ゴリズムを提案した
・ 1つあたりの計算量が O(|V| |E|) から O(Δ4 ) に改良(?)
された
・ 実際問題への適用
・ グラフマイニング
・ web community の発見
・ 類似語群の発見
・ 論文のカテゴリー化
などなど
ダウンロード

power point