Selecting Shortcuts for a Smaller World
-
Nikos Parotsidis, Evaggelia Pitoura, Panayiotis Tsaparas
-
SDM 2015
動機付け
-
Small world性
-
情報提供とかバイラルマーケティングとかの効果の指標
-
↑のために小さくしたくなる
応用
生長するネットワーク
-
ソーシャルネットワーク
-
犯罪者ネットワーク
-
物理(輸送・通信)ネットワーク
-
リンク推薦
問題定義
-
入力
-
無向グラフ G=(V,E)
-
候補辺 C (C∩E=∅)
-
整数k
-
問題
-
S⊆C (|S|=k)を選び
-
R_G(S) = L(G)-L(G∪S)を最大化
-
$$ L(G) = {n \choose 2}^{-1} \sum_{x,y \in V} d_G(x,y) $$
-
加えると平均最短経路長を最小化するものが欲しい
-
V×V\E全体から選択する問題は[Papagelis, Bonchi, Gionis. CIKM'11]
困難さ
-
NP-hard
-
最大被覆問題からの帰着
-
じゃぁ,劣モジュラだったり優モジュラだったりしそう?
-
補題:R_G(S)は劣モジュラでも優モジュラでもない
単一辺の効果の(効率的)計算
-
[Ausiello, Italiano, Speccamela, Nauni. J. Algorithms 1991]を変更
-
フェーズ1
-
辺を追加することで最短経路長が変わりうる頂点対を特定
-
フェーズ2
-
e=(x,y): 追加する辺
-
d_old(u,v): e追加前のuからvへの距離
最終更新:2015年06月12日 18:27