Top-k Reliable Edge Colors in Uncertain Graphs
-
Arijit Khan, Francesco Gullo, Thomas Wohler, Francesco Bonchi
-
CIKM 2015
概要
-
各辺に色とその出現確率がついたuncertain graphsを考える
-
s-tの連結確率が最大となるようなk色を求める問題
-
難しいのでヒューリスティック
動機付け
-
応用
-
生物学的ネットワーク上の経路生成
-
トピック付き情報カスケード
問題定義
-
各辺e各色cについて,その出現確率 $$ = p_e^c $$
-
色集合Cについて辺の出現確率$$ p_e^C = 1-\prod_{c \in C} (1-p_e^c) $$
-
これを元に辺色で制約した到達可能性$$ R_{C_1}(s,t) $$を考える
-
Top-k Reliable Color Set Problem
-
$$ \mathcal{G} = (V,E,C,p), s, t, k $$
-
$$ \mathop{\mathrm{argmax}}_{C_1 \subseteq C} R_{C_1}(s,t) $$
-
$$ \mathrm{such\ that} \ |C_1| = k $$
難しさ
-
NP-hard
-
色集合C1について劣モジュラでも優モジュラでも無い
-
2色足さないと到達可能にならない,1色で到達可能になる,みたいなケースを考える
提案手法
Individual Top-k: ベースライン1
-
$$ R_{\{c\}}(s,t) $$でソートしてtop-k色を出力
-
確率の計算をMonte Carloシミュレーション
-
$$ \mathcal{O}(|C|T(n+m)+|C|\log k) $$時間
Iterative Hill-Climbing: ベースライン2
-
貪欲アルゴリズム(適応的)
-
$$ \mathcal{O}(|C|kT(n+m)) $$時間
最信頼経路ヒューリスティック (Most-Reliable-Path based Heuristic)
-
s-t間の経路を出現確率が高い順にtop r列挙
-
$$-\log p_e^c$$ とした多重グラフにEppsteinのアルゴリズム
-
r経路から,選んだ経路の総色の数≦kとなるような,出現確率最大の経路集合を選ぶ
-
難しいので,経路を貪欲に選ぶ
-
色数に余裕があったらランダムに選ぶ
-
$$ \mathcal{O}(r^2(n'+m')T) $$時間
実験
-
3つ目が最速
-
1と2はk倍しか違わないと思うが,めっちゃ差が有るように見えるぞ…?
-
2つ目が高品質
まとめ
-
問題提議は無くもないのかなという感じ
-
アルゴリズムはクオリティが低い
-
どっちももっと面白げでないとダメそう…
CIKM uncertain graphs
2015/12/14
最終更新:2015年12月14日 23:36