Document

擬似クリークを列挙する
多項式時間遅延アルゴリズム
宇野 毅明 (国立情報学研究所
&総合研究大学院大学)
2007年3月9日 第111回アルゴリズム研究会
問題定義と動機
密な部分構造
・ グラフから密な構造を見つけ出す、という手法は、データマイニングや
データ工学を始めとする情報学の分野で非常に基礎的であり、多くの研
究で用いられている
(クラスタリング・webコミュニティー、
グループ化、カテゴリー発見...)
・ 従来、密な構造としてクリーク(特に極大)が重宝されてきた
 クリーク・極大クリークは、十分速く列挙できるようになった
・ 次のステップとして、よりモデルを豊かにするため、あるいはエラーやあ
いまいさ、不完全さに対して頑強な結果を得るため「クリークっぽいもの」
の発見が注目されつつある
(いくつもの重なり合う極大クリークが1つになる、データにノイズやエラー
があっても大丈夫)
応用:クラスタリング
対象: データの関連を現すグラフ
(データの項目が頂点、関係のある、類似する項目間に枝)
類似する、あるいは互いに
関連するグループ
互いに背反だが、
立場が同じ項目のグループ
・ データの種類・規模で大きさが変わる
・ 通常、それほど密ではない(次数高々100)
・ 局所的に密な部分が存在
・ パワー則、スモールワールドが成り立つことが多
Web コミュニティ発見
Webコミュニティ: 内容や嗜好が似ているweb サイトの集合
モデル: webページ、又はwebサイトのリンク構造からグラフを作る
このグラフのクリーク・2部クリークは、webコミュニティになっている
だろう
(リンクは、似た内容・嗜好のページに貼られるから)
サイト
趣味バイク
バイク好き
サイト
ホンダ
カワサキ
バイク万歳
バイク人生
ラーメン
好き
ラーメン
命
博多
ラーメン
札幌
ラーメン
ヤマハ
・ ごみページを除いた後のグラフの大きさは100万~1億程度
・ 平均次数10程度、パワー則が成り立ち、局所的に密
類義語群の発見
対象: 単語ネットワーク
(単語が頂点、単語AとB を組合せて
複合語ができるとき、枝を張る)
関東
地方
関西
地区
中国
電力
北陸
2部クリークの片側が、
似た意味を持つ単語の集合
・ 大きなものでも、15万語程度
・ 通常、それほど密ではない(次数高々200)
・ 局所的に密な部分が存在
・ パワー則、スモールワールドが成り立つ
類似論文のグループ化
対象: 論文・アブストラクトグラフ
(論文が片側の頂点、単語がもう
片側の頂点で、論文のアブストラクト
が単語を含むときに枝を張る)
論文A
論文B
論文C
語1
語2
語3
論文D
語: 研究分野を表す単語群
論文: その分野の論文のグループ
・ 大きなものでも、10万語程度
・ 通常、それほど密ではない(平均次数高々200)
・ 局所的に密な部分が存在
・ パワー則、スモールワールドが成り立つ
擬似クリーク(密部分グラフ)
・ 頂点部分集合 S に対して、S の枝密度を
(S の頂点誘導グラフの枝数)
(|S|-1)|S| /2
クリークの
枝数
- S がクリーク  枝密度は 1
- S が独立集合  枝密度は 0
頂点の組のうち
結ばれているも
 S の枝密度が高ければ、クリークに近くなる
のの割合
閾値 θに対して S が擬似クリーク  (Sの枝密度) ≧ θ
与えられたグラフの擬似クリークを全て見つける問題を扱う
擬似クリークに関わる既存の結果
・ 1つ見つけるのは簡単
 空集合、1頂点の集合、枝の両端点が必ず擬似クリークになる
・ 大きさ k の擬似クリークを見つける問題はNP完全
 θ= 1 とすると、大きさ k のクリークを見つける問題になる
・ 最も枝密度の高い頂点数 k の部分グラフを見つける問題はNP完全
- O(|V|1/3-ε) の近似率のアルゴリズムがある
- 最適解がある程度濃い、とい条件では O((n/k)ε) 近似 [鈴木徳山]
- 枝数が Ω(n2) ならPTASがある[Aroraら]
・データマイニングなどの分野で、擬似クリークを発見するアルゴリズムはいく
つか提案されているが、いずれも完全性がなく、列挙問題として捉えている研
究はない
分割法によるアプローチは困難
・ 列挙アルゴリズムの基本的な構築の仕方として、分割法
(分枝限定法)がある
・ 各反復で、ある頂点を含むものと
含まないものに解集合を分割し、
できた集合が空でなければ、
再帰的に列挙を行う
v
v1
1
v1, v2
解があるか判定
する問題がNP完全
v1, v2
v1, v2
v1, v2
困難性の証明
Theorem 1 与えられたグラフ G と閾値 θ、頂点部分集合 U
に対して、U を含む擬似クリークが存在するかどうかを判定
する問題はNP完全である
証明: 大きさkのクリークの存在判定を帰着
入力グラフ
G=(V,E)
|V|2 -1
枝密度 =
|V|2
2|V|2 個の
頂点を追加
し、Uとする
θ=
|V|2 -1
|V|2 +ε
・ (U + クリーク) のみが擬似クリーク
・ 大きくなると枝密度が真に増加)
・ εを適当に設定すると、大きさが
k 以上のクリークのみが擬似
クリークになる
果たして本当に困難か?
・ この証明は「とても濃い」グラフの判定問題が難しいことを
証明しただけ
 密度が中くらいのところについては、良くわからない
 出力多項式時間アルゴリズムはできるかもしれない
θ= 1
出力多項式時間 計算時
間が入力の大きさと出力の
大きさに対して多項式
簡単
簡単
θ= 0
困難
?????
多項式時間(遅延)アルゴリズム
逆探索法によるアプローチ
・ 列挙する対象の間に、非巡回的な親子関係を定義
objects
親子関係が導く根付き木を深さ優先探索することで列挙
探索は、再帰的に子どもを見つけることで行えるので、
子どもを見つけるアルゴリズムがあれば十分
擬似クリークの親
・ v*(K) : G[K] の最小次数頂点の中で最小添え字のもの
・ 擬似クリーク K の親を K\v*(K) で定義
K
K の親
・ K の枝密度 = G[K] の平均次数 ÷(|K|-1)
・ 親は、K から最も枝密度の薄い部分を取り除いたものなので、
やはり擬似クリークになる
・ 親は大きさがちょうど1小さい  親子関係は非巡回的
子どもの発見
・ 擬似クリークの親は、頂点を1つ取り去って得られる
 擬似クリークの子どもは頂点を1つつけることで得られる
(子どもの候補 |V| 個しかない)
・ K∪v が K の子どもである 
① 擬似クリークであり
② K∪v の親が K (つまりはv*(K∪v) = v )
・ この条件を各頂点について素朴に評価するとO(|V|+|E|) 時間
・ もう少し速くしましょう
子どもである条件
・ degK(v): v に隣接する K の頂点の数
 degK(v) がある一定値以上であるときのみ、 K∪v は擬似ク
リークになる (① の条件)
・各反復でdegK(v)を更新し(O(deg(v)) 時間)、その値ごとに分類
しておくことで、 ① の条件を満たすものを1つあたり定数時間で
見つけられる
・②の条件 v*(K∪v) = v も、degK(v)の値で場合分けするとクリア
- degK(v) < K の最小次数  K∪v は必ず Kの子ども
- degK(v) > K の最小次数+1  K∪v は Kの子どもでない
子どもである条件 (2)
・ S(K): K の最小次数の頂点を、添え字順に並べた列
・ degK(v) = K の最小次数 or +1  v が、
- v より degK、添え字ともに小さい頂点はない
- degK(u) = degK(v) かつ添え字が v より小さい u 、および
degK(u) = degK(v)-1 かつ添え字が v より大きい u
は必ず v と隣接
・ K の頂点を次数順・添え字順に見て、隣接リストをスキャンし、
K に含まれない各頂点に対して「隣接しない初めての頂点」 を
見つける  それと、自分の添え字を比べればよい
1反復のチェック・データ更新時間は O(Δ(Δ+log |V|)) となる
計算機実験
実装
実験環境: Pentium M 1.1GHz、256MBメモリ + cywin & C
・ 実装は、単純なものを用いた
- degK(v) の更新とグループ分けはするが、並び替えはしない
- degK(v)= Kの最小添え字 or +1 となる頂点に対して、素
朴にチェックをする
 この条件を満たす頂点はそれほど多くないだろう
 隣接しない頂点がすぐ見つかって、頂点1つに対する
チェックも結局は短時間でできるだろう
実験に用いたグラフ
- 通常のランダムグラフ
(確率 p で枝をはる)
- 局所的に密なランダムなグラフ
(自分と添え字が近い頂点のみに
確率1/2で枝を張る)
- ランダムに作成したスケールフリーグラフ
(頂点を順に追加し、次数に比例する確率で
他の頂点を定数本選び、枝を張る)
- 現実のデータ
(ソーシャルネットワークデータ)
ランダムグラフ
・ 枝の確率が 0.1 で、頂点数が 200-2000。閾値は90%。時間は
百万個あたり。クリーク列挙と比べると10倍程度遅い
r a ndom gr a ph p=0.1
#clique
time per 1M clique
time clique
#p-clique 0.9
time per 1M 0.9
time 0.9
#p-clique 0.8
time per 1M 0.8
time 0.8
1000000000
100000000
10000000
1000000
100000
1000
100
10
1
0.1
6400
4524
3200
2262
1600
1131
800
565
400
282
0.01
200
time (sec) & #cliques
10000
#vertices
次数が大きくなるにつれて、ほぼ線形に時間が伸びる
局所的に密なランダムグラフ
・ 自分の回り±30頂点に確率が 0.5で枝を張る
・ 100~25600 頂点、閾値は90%。同じくクリークより10倍遅い
locally dense random graph
#clique
1000000000
time per 1M clique
100000000
10000000
time clique
1000000
#p-clique 0.9
time per 1M 0.9
10000
1000
time 0.9
100
#p-clique 0.8
10
time per 1M 0.8
1
0.1
time 0.8
3E+05
64000
16000
4000
0.01
1000
time (sec) & #cliques
100000
#vertices
次数が変化しないので、時間は伸びない
ランダムに作成したスケールフリーグラフ
・ 大きさ10のクリークに1つずつ頂点を加える
・ 次数に比例する確率で他の頂点を10個選び、枝をはる
10000000
1000000
100000
#clique
time per 1M clique
time clique
#p-clique 0.9
time per 1M 0.9
time 0.9
#p-clique 0.8
time per 1M 0.8
time 0.8
10000
1000
100
1
0.1
16
00
0
32
00
0
64
00
12 0
80
0
25 0
60
00
80
00
40
00
20
00
0.01
10
00
time & #cliques
10
時間は非常にゆっくりと増加
#vertices
現実問題
・ 論文の共著関係を表すグラフ
・ 頂点数は3万、枝数は12万5千、スケールフリー
1000000000
real-world data
100000
#p-clique
time
time per 1M
1000
10
0.83
0.85
0.88
0.9
0.93
0.95
0.98
1
0.1
1
time & #p-cliques
10000000
threshold
1個あたりの計算時間は閾値によらないようだ
閾値を変化させる
・ 10000頂点の局所的に密なグラフで、閾値を変化させる
change of threathold
次数が小さくなると、候補が増えるため時間が増大
2
5
8
11
1
14
epsilon
10
20
10
25
40
55
70
85
1
100
17
10
time(sec) per 1M
100
10
0
time(sec) per 1M
change of threathold
epsilo
考察+α
・ 実際の列挙の時間は、ひとつあたりほぼ定数時間
・ 理論的なバウンド、最大次数の2乗よりはるかに小さい
・ なぜ現実的には速いのか?
- データの更新の時間は、追加された頂点の次数に線形
 degK を小さくする頂点の次数が大きいとは思えない
- 子どもかどうかチェックしなければならない頂点は少ない
 子どもの数の定数倍
まとめ
・ 擬似クリーク(枝密度の高い部分グラフ)を列挙する初の多項式時間ア
ルゴリズムを提案
・ 分枝限定法的なアプローチは難しいであろうと思われることを、子問題
がNP困難となることで証明
・ 計算実験により、現実的な、疎なグラフに対して有効に働くことを実証
将来の課題:
・ 計算量と現実的な計算時間のギャップを、より良く説明できないか
・ 計算量は減らせないか
・ 困難性の証明を、より小さい閾値に適用できるよう、改良できないか
・ 極大な擬似クリーク、またはそれに類するものが効率良く列挙可能か