「Selecting Shortcuts for a Smaller World」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
* 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
-- 本当に経路長が減るのか決定する
-
* 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への距離
