Selecting Shortcuts for a Smaller World - todo314 @ ウィキ

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への距離