The Most Reliable Subgraph Problem - todo314 @ ウィキ

The Most Reliable Subgraph Problem

• Petteri Hintsanen
• PKDD 2007

概要

• K辺だけ除いて信頼度all-,two-,k-terminal 信頼度を最大化
  • どの辺が貢献度高い／どうでも良い？
• 直並列グラフ上の2端子信頼度に対する厳密アルゴリズム
• ほかはヒューリスティック

最信頼部分グラフ問題 (Most Reliable Subgraph Problem)

• 信頼度の指標
  • 無向／有向グラフで全体，頂点対，k頂点が連結となる確率
• 問題定義
  • 以下を満たす部分グラフHを見つけよ
    • Hの信頼指標が最大となる
    • $$|E[H]| = |E|-K$$
• 信頼度の値の計算はいらないので簡単かも？→NO
• 定理: $$ \mathrm{Rel}_k $$についてNP-hard

提案手法

直並列グラフの場合

• 確率的グラフGについて頂点s,tが直並列である…以下のreductionを繰り返し，単一辺(s,t)にできる
  • 直列: $$u,w$$を隣接する頂点とする次数2の頂点$$ v \not \in \{s,t\} $$について，
  • $$ e=(u,v), f=(v,w) $$を$$ g=(u,w) $$に置き換え$$ p_g=p_ep_f $$
  • 並列: $$ e=(u,v), f=(u,v) $$があるならば，$$ g=(u,v) $$に置き換え$$ p_g=1-(1-p_e)(1-p_f) $$
• 操作の順番は関係ない
• $$ S(e) := $$ eにreduceした辺集合
• $$ S(e=(u,v),i) := G[S(e)], K=i, U=\{u,v\}$$の最適解
  • ある頂点対に着目して，そいつの間の中での最適解を考えている
• 補題1: $$S(e,i), S(f,i)$$が分かっていると$$S(g,i)$$全体が$$O(K^2)$$時間で計算できる
  • gはeとfのreductionでできる辺
  • DPするだけ
• 定理2: 総計算時間は$$ O(K^2|E|) $$
  • reductionは|E|-1回

一般のグラフ

• ランダムグラフ生成
• MRSPを解くのは非自明→$$ \mathrm{Rel}_2(G-e) $$の大きい順に辺を選ぶ

実験

• 直並列グラフを生成
• ベースライン…辺自身の確率順
• 10^6シミュレーションで確率は計算（でかい

まとめ

• 直並列グラフは確かにこういう時に便利なのね
• 特にオモシロさは無し

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

2015/11/27