Finding Top-k Maximal Cliques in an Uncertain Graph - todo314 @ ウィキ

Finding Top-k Maximal Cliques in an Uncertain Graph

• Zhaonian Zou, Jianzhong Li, Hong Gao, Shuo Zhang
• ICDE 2010

概要

• uncertain graphでtop-k極大クリーク列挙を考えるよ
• 難しいけど，探索するよ

Top-k 極大クリーク問題

• 頂点・辺に確率が付与
• 入力: G, k, s
• 出力: 大きさs以上かつ極大クリーク確率が上位kの頂点集合の族
• 極大クリーク列挙を含む
• $$ C \subseteq C' $$なら$$ \Pr[\mathrm{cliq}(C)] \geq \Pr[\mathrm{cliq}(C')] $$
• $$C$$: クリーク
• $$C_i$$: Cに1頂点足してできるクリーク
• $$ \frac{\Pr[\mathrm{cliq}(C_i)]}{\Pr[\mathrm{cliq}(C)]} = \Pr[\mathrm{cliq}(C_i)\mid\mathrm{cliq}(C)] $$
• $$ \Pr[\mathrm{mcliq}(C)] = \Pr[\mathrm{cliq}(C)] \prod_{i} ( 1-\frac{\Pr[\mathrm{cliq}(C_i)]}{\Pr[\mathrm{cliq}(C)]} ) $$
  • Cが成功してかつCの周りが全部失敗する確率が必要

提案手法

• 各頂点から始めて（予め決めた順番で）頂点を足していく
• 2つのヒープを持つ
  1. top-k: $$ \Pr[\mathrm{mcliq}(C)] $$順
  2. ext: $$ \Pr[\mathrm{cliq}(C)] $$
     • 各頂点（クリーク）を突っ込んでいく
• 性質: $$ \Pr[\mathrm{mcliq}(C)] \leq \Pr[\mathrm{cliq}(C')] \leq \Pr[\mathrm{cliq}(C)] $$

1. extからCを取り出す
2. 枝刈り
   • top-kの一番しょぼいのと比較すると，「性質」からC（とそのsuperset）がtop-kに成り得るか分かる
3. 極大クリーク確率計算
4. 展開
   • 1頂点足してextに追加
5. 更新
   • Cがtop-kに入りそうだったら挿入

• 高速化
  • 大きさ枝刈り: 近傍足してs頂点未満ならそもそも要らん
  • 先読み枝刈り: それっぽい感じに何か見積もる
  • 単調性枝刈り
• 二段階探索
  • 途中まで深さ優先で，それから最良優先

まとめ

• 「極大」とすることで自ら難していく
• 枝刈りしまくってる（ICDEっぽい）
• フルペーパーで出てもありそう，という感じに思うが
• 極大クリーク全列挙してからやったほうが早かったりはしない・・・？

ICDE uncertain graphs 極大クリーク

2015/12/16