Top-k Reliable Edge Colors in Uncertain Graphs

Top-k Reliable Edge Colors in Uncertain Graphs

  • Arijit Khan, Francesco Gullo, Thomas Wohler, Francesco Bonchi
  • CIKM 2015

概要

  • 各辺に色とその出現確率がついたuncertain graphsを考える
  • s-tの連結確率が最大となるようなk色を求める問題
    • (残りの色に対応する確率は0)
  • 難しいのでヒューリスティック

動機付け

  • 応用
  • 生物学的ネットワーク上の経路生成
  • トピック付き情報カスケード
    • よさ気な特徴を見つけるために使う

問題定義

  • 各辺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
    • Maximum Coverageからの帰着
  • 色集合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