Identifying Converging Pairs of Nodes on a Budget - todo314 @ ウィキ

Identifying Converging Pairs of Nodes on a Budget

• Konstantina Lazaridou, Konstantinos Semertzidis, Evaggelia Pitoura, Panayiotis Tsaparas
• EDBT 2015

概要

動機付け

• グラフの動的変化に伴い最短路長が縮まった頂点対が大事
  • ソーシャルネットワーク：共通の興味・活動の出現→友達推薦
  • テロリストネットワーク：共謀
  • 蛋白質間相互作用ネットワーク：次の相互作用の候補

問題定義

• G_t: 時刻tの無向グラフ
• 頂点・辺挿入だけ考える
• G_t1とG_t2 (t1<t2)と連結な頂点u,vについて
• Δ_t1,t2 (u,v) = d_t1(u,v)-d_t2(u,v)≧0
• についてtop-kの(u,v)を見つける

提案手法

• 全探索：O(n^2)対で＼(^o^)／
• 最短経路を計算する頂点数を減らしたい
• 考え方：m回だけ↑ができるので，なるたけ沢山（精確に？）top-kを見つける

予算付き経路被覆

• 最小で何回最短経路計算がいる？
  • P∈(V×V)^k: 答え
  • C⊆V s.t. ∀(u,v)∈P u∈C∨v∈C
  • 各v∈Cから最短路を計算してtop-kをとるとPになる
  • O(nC)とかそのくらい
• Cをどうやって求めるか？
  • Pについてだけ辺を張ったグラフを考えるとその頂点被覆がC
  • 難しいのでM⊆V_t1 (|M|=m)で被覆されるPを最大化

Cの計算アルゴリズム

基本的な考え

1. M←候補m頂点
2. D_1←各v∈MからG_t1上で最短経路長
3. D_2←各v∈MからG_t2上で最短経路長
4. D_1-D_2最大のtop-k対(i,j)を返す

候補端点生成

• Pを被覆してるかも分からんがM生成のヒューリスティックをいっぱい提案

1. 中心性：次数（の変化）
2. 散乱：互いに離れた頂点
3. 目印：L⊆V_t1を選びそれらとの距離のずれ
4. 混成：散乱でLを選び，目印とする
5. 分類：↑今までので頂点が良いか類別
6. 発生：[14]の手法

実験

• |V|<30K, |E|<105K
• ヒューリスティックの挙動を見てる
• 結構ばらつくが，次数の亜種が良い？
• 最高でPの76%しかとれてない設定もある
• 計算時間の言及は無し

まとめ

• 問題は面白そう
  • 多項式時間で解けるが難しい
• 論文中の手法は微妙
  • Pの計算が難しいのでしょ～がない
• もっと頭のいい手法はありそう（枝刈りとかで

EDBT top-k収束頂点対

2015/06/23 19:47