Document

大規模2部グラフに対する
極大クリーク列挙アルゴリズムの
改良と実装
宇野毅明
国立情報学研究所
＆総合研究大学院大学（博士入学者募集
中）
2003年3月14日アルゴリズム研究会
新旧アルゴリズムの比較２
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 極大クリークを列挙する、という問題を考える
（そして、普通の極大クリークだけ出力する）
逆探索による列挙
・（ある１つの以外の）任意の解に, 親（他の解）を定義
（ 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部グラフに定義
・頂点集合１の頂点同士、頂点集合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万個あたりの計算時間(秒)
既存と提案手法の比較
頂点数
新旧アルゴリズムの比較２
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
※ だいたい、次数の２乗に比例
160
320
現実のデータに適用
・とある計算言語学のデータに適用
頂点数およそ2万：2万、枝数24万（平均次数6）の2部グラフ
（次数に偏りあり）極大クリーク数270万
計算時間＝1500秒（1万個あたり6秒）
（既存＝4000時間くらい？）
・とあるデータマイニングのデータに適用
頂点数およそ6万：500、枝数15万の2部グラフ
（次数に偏りあり）極大クリーク数14万
計算時間＝266秒（1万個あたり19秒）
（既存＝30時間くらい？）
まとめと今後の展開
・疎グラフの極大クリーク、極大2部クリークを列挙するアル
ゴリズムを提案した
・１つあたりの計算量が O(|V| |E|) から O(Δ4 ) に改良（？）
された
・実際問題への適用
・グラフマイニング
・ web community の発見
・類似語群の発見
・論文のカテゴリー化
などなど

Download Report