Fast Discovery of Reliable Subnetworks - todo314 @ ウィキ

Fast Discovery of Reliable Subnetworks

• Petteri Hintsanen, Hannu Toivonen, Petteri Sevon
• ASONAM 2010

概要

• The Most Reliable Subgraph Problemの2端子版のアルゴリズム
• ヒューリスティクス

提案手法

• 基本はランダムグラフのサンプリング
• Phase1: パスサンプリング
  • s-tパスの候補集合を集める
  • パスPを候補Cに足した時，Pr[C∨P]=Pr[C]+Pr[\bar{C}∧P]を最大化したい
    • 怪しい感じ（保証等なし）に右項を近似計算する
• Phase2: 部分グラフの構築
  • Pr[∨P]が最大となるようにCからパス部分集合を選択
  • MaxCoverageの亜種を解く
    • $$ \mathrm{max} |\bigcup_{\text{Selected }P_i} C(P_i)| $$
    • …C(P_i): P_iの出現する奴の集合（要は↑はs-tが連結な奴の個数）
    • $$ \mathrm{s.t.} |\bigcup_{\text{Selected }P_i} P_i| \leq B $$
    • …劣モジュラ的コスト
  • 単一のパスのコストで割った増加量で貪欲（理論保証無し）

実験

• The Most Reliable Subgraph Problemと比較してyeah.

まとめ

• 「MaxCoverageの亜種」だけが気になった（まぁよくありそう）

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

2016/10/17