BMC: An Efficient Method to Evaluate Probabilistic Reachability Queries

BMC: An Efficient Method to Evaluate Probabilistic Reachability Queries

  • Ke Zhu, Wenjie Zhang, Gaoping Zhu, Ying Zhang, Xuemin Lin
  • DASFAA 2011

概要

  • $$ \mathrm{rel}_{\mathcal{G}}(s,t) > \theta? $$に答えたい
  • 適当にrel(s,t)の上限を求める手法
  • 駄目なら工夫したMonte-Carlo

提案手法

上限計算

  • out: Pr[sから距離l以上遠くへ到達可能]
  • in: Pr[tへ距離m以上遠くへ到達可能]
  • C: B(s,l)とB(t,m)の間の「互いに素」なカットの集合
    • 「カットが切られない」を独立事象にするため
  • rel(s,t) >= out Π(1-p(C)) in
  • ∵少なくとも、以下の成立が必要
    • 球の外に出る∧どのカットも消えていない∧球の内に入る
    • 間の接続関係は考えない
  • Cの計算
    • d(s,x)=i, d(s,y)=i+1は辺(x,y)をi毎にまとめる

Monte-Carlo

  • 適当な段階で枝刈りをする
  • もう到達できない/到達している

実験

  • やりました(*゚∀゚)

まとめ

  • はい。

DASFAA uncertain graphs 到達可能性

2017/01/16

最終更新:2017年01月16日 19:51