「Redundancy-Aware Maximal Cliques」の編集履歴（バックアップ）一覧はこちら

「Redundancy-Aware Maximal Cliques」(2013/11/17 (日) 15:53:47) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

* 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倍以上速い

&tags()

&update()