Redundancy-Aware Maximal Cliques
-
Jia Wang, James Cheng, Ada Wai-Chee Fu
-
KDD 2013
概要
-
極大クリークの列挙の問題点
-
極大クリークと大体かぶるように一部だけ列挙するアルゴリズムを作ったよ!
問題
-
Redundancy-Aware Maximal Cliques
-
S: 極大クリークの部分集合
-
$$ vis(C) = \max_{C' \in S} \frac{|C \cap C'|}{|C|} $$
-
τ-visible summary
-
∀C∈M, vis(C)≧τ
-
つまり、どんなクリークともτ位かぶっているのが有る
-
できるだけサイズの小さいτ-visible summary Sを見つけたい
アルゴリズム
-
MCEのバックトラックアルゴリズムを元にした
-
各クリークを確率的にとっておくか決める
-
前とかぶっていない方が選ばれやすい???
-
importance samplingのアナロジー
-
∀C, E[vis(C)]≧τ
実験
-
サイズも時間も乱択版の方が(非乱択版よりも)良い
-
Top-k に使うと全部列挙するより10倍以上速い
KDD enumeration maximal clique
2013-11-17 15:53:47 (Sun)
最終更新:2013年11月17日 15:53