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の計算アルゴリズム
基本的な考え
-
M←候補m頂点
-
D_1←各v∈MからG_t1上で最短経路長
-
D_2←各v∈MからG_t2上で最短経路長
-
D_1-D_2最大のtop-k対(i,j)を返す
候補端点生成
-
Pを被覆してるかも分からんがM生成のヒューリスティックをいっぱい提案
-
中心性:次数(の変化)
-
散乱:互いに離れた頂点
-
目印:L⊆V_t1を選びそれらとの距離のずれ
-
混成:散乱でLを選び,目印とする
-
分類:↑今までので頂点が良いか類別
-
発生:[14]の手法
実験
-
|V|<30K, |E|<105K
-
ヒューリスティックの挙動を見てる
-
結構ばらつくが,次数の亜種が良い?
-
最高でPの76%しかとれてない設定もある
-
計算時間の言及は無し
まとめ
-
問題は面白そう
-
論文中の手法は微妙
-
もっと頭のいい手法はありそう(枝刈りとかで
EDBT top-k収束頂点対
2015/06/23 19:47
最終更新:2015年06月23日 19:50