Fast Discovery of Reliable k-terminal Subgraphs - todo314 @ ウィキ

Fast Discovery of Reliable k-terminal Subgraphs

• Melissa Kasari, Hannu Toivonen, Petteri Hintsanen
• PAKDD 2010

概要

• Uncertain graphがもらえるので、
• クエリ頂点集合の連結確率を最大化する辺数に制限のついた部分グラフが欲しい
• 謎ヒューリスティクス提案
  • Path coveringを元に
  • [Hintsanen-Toivonen-Sevon Fast discovery of reliable subnetworks]多分ASONAM

動機付け・問題定義

• グラフがデカイので抽出するのが目的
  • 興味があるもの（遺伝子とか）に関連あるのだけで良い
• 入力
  • Q⊆V, B
• 出力
  • $$ \mathrm{argmax}_{|E[H]|\leq B} \mathrm{R}(H,Q) $$
  • 出力部分グラフ上でのQの連結確率を最大化

提案手法

Path covering

• 2-terminalの場合の手法
• 経路標本
  • 互いに独立で確率が高い経路の集合Cをとってくる
• 部分グラフ構築
  • Cの部分集合Sで$$ \Pr[\bigvee_{P \in S} P] $$を最大化
    • 下限にはなるね
  • 辺当たりの確率の増加量で貪欲に経路をSに追加
    • 制約ギリギリまで

アルゴリズム

• k頂点Qを結ぶ全域木を考える

1. C←Q中の頂点対を結ぶ最高確率の経路を計算
   • nC2の経路ができる、これをそれぞれ少しずつ伸ばしてQの全域木にする
2. ループ
   1. ランダムグラフを標本
   2. C中の各Ci（木の成り損ない）について
   3. ランダムグラフにCiが出現∧CiがQを結んでいない
      1. u∈Q∩V[Ci]からv∈Q-V[Ci]に向けて伸ばす

実験

• はい

まとめ

• アルゴリズムはまぁ…
• どうでもいいけど、辺より頂点数で制限したほうが良くない？
  • 頂点は無限に足しても良いので…

PAKDD uncertain graphs ネットワーク信頼性

2015/12/25