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