Fast Reliability Search in Uncertain Graphs
-
Arijit Khan, Francesco Bonchi, Aristides Gionis, Francesco Gullo
-
EDBT 2014
概要
-
信頼性検索…確率η以上でSから到達可能な頂点集合
-
索引RQ-tree
-
クエリ評価
-
精度>0.95、再現率>0.75で爆速
提案手法
クエリ処理:候補生成
-
Rout(S,C) := Sから「Cの外の頂点」へ到達する確率
-
Rout(S,C)<ηならR(S,t)<η (t∈V-C)
-
上限: Rout(S,C) ≦ 1-((S,V-C)カットの最大発生確率)
-
SからV-Cへ到達不可な確率の良い下限が欲しいから
-
辺重み-log(1-p(e))な最大流で計算(C+N(C)の誘導部分グラフだけなので速い)
-
単一始点の場合
-
クエリは{s}とη
-
RQ-treeを葉{s}から上に辿りながら、Rout(S,ノードの集合)の上限を計算
-
Rout(S,C*)<ηとなったC*で止まれば、(i)C*は最小、(ii)t∈V-C* R({s},t)<η
-
複数始点の場合
クエリ処理:検証
-
R(S,t)の下限が欲しい
-
①高精度検証
-
下限 := Sからtの最尤経路の発生確率
-
いつもの感じで最短経路計算
-
②高再現率
-
サンプリングする
RQ-tree の構築
-
$$ \mathsf{RQ\mathrm{-}tree} \; \mathcal{T} $$に求められる条件
-
バランスして頂点集合を分割していく
-
ある程度の高さがあると良い
-
Rout({s},C)は小さいと良い
-
ので、並行分割
-
本当にやりたいこと: 二分割した時、Rout(S,C1/C2)と|C1|/|C2|の観点でバランスして欲しい
-
実際: 難しいので、METISに投げまーす
実験
-
やったこと…
-
索引構築の時間/空間
-
クエリ処理の精度/効率: 流石にMonte-Carloより速い、簡単な下限で端折れるのが強い
-
RQ-treeの枝刈り: η大→#解減→枝刈り良
-
始点集合の大きさ・性能・スケーラビリティ: クエリ時間=O(|始点集合|)くらい?
-
影響最大化への応用: 一応10倍速くなった
まとめ
-
手法がごつすぎる割には、あまり最終的な保証が無い
-
こんな単純な問題ですら実用的にでも満足に解けない現状は、(個人的には)つらぽよ感ある
EDBT uncertain graphs 信頼性 影響最大化
2016/12/12
最終更新:2016年12月12日 18:47