「Information Diffusion in Mobile Social Networks: The Speed Perspective」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
* Information Diffusion in Mobile Social Networks: The Speed Perspective
- Zongqing Lu, Yonggang Wen, Guohong Cao
- INFOCOM 2014
* 概要
- 拡散（時間）最小化問題
-- できるだけ早く全体に伝わって欲しい
- k-center 問題になる
-- 近似比 log*n，時間 O(n^5)くらいしかない
- コミュニティベースのアルゴリズムを考案
- 分散集合被覆アルゴリズム（謎
* 問題定義
- 辺には重みがあって確率が決まる
- そういうのから期待遅延時間が定義できる
- max_v |(S,v)|を最小化したい！！
-- |(S,v)|はSからvに伝わる最小期待伝播時間
- これは非対称k-center問題
-- 対称だったらもっと簡単
- 近接中心性による簡単な手法も考えられるけど駄目だよね～
* コミュニティベースアルゴリズム
- まずC1,C2,…,C_lに分割
- k<lだとSに選ばれないコミュニティが出てきちゃうので
- k≧lになるようにマージ
- 何か色々頑張ってる
* 分散集合被覆アルゴリズム
- 辺のパラメータがちゃんと与えられない場合用の手法らしい
* まとめ
- 伝播にかかる時間を期待時間で固定しちゃっているがいいんだろうか…
&tags()
&update()
