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)|を最小化したい!!
-
これは非対称k-center問題
-
近接中心性による簡単な手法も考えられるけど駄目だよね~
コミュニティベースアルゴリズム
-
まずC1,C2,…,C_lに分割
-
k<lだとSに選ばれないコミュニティが出てきちゃうので
-
k≧lになるようにマージ
-
何か色々頑張ってる
分散集合被覆アルゴリズム
-
辺のパラメータがちゃんと与えられない場合用の手法らしい
まとめ
-
伝播にかかる時間を期待時間で固定しちゃっているがいいんだろうか…
INFOCOM 情報拡散
2014-07-01 23:05:31 (Tue)
最終更新:2014年07月01日 23:05