Redundancy-Aware Maximal Cliques - todo314 @ ウィキ

Redundancy-Aware Maximal Cliques

• Jia Wang, James Cheng, Ada Wai-Chee Fu
• KDD 2013

• http://videolectures.net/kdd2013_wang_maximal_cliques/

概要

• 極大クリークの列挙の問題点
  • めっちゃ重複するので、サイズがやばい
• 極大クリークと大体かぶるように一部だけ列挙するアルゴリズムを作ったよ！
  • まさかの乱択アルゴリズム

問題

• 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)