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になるようにマージ
  • 何か色々頑張ってる

分散集合被覆アルゴリズム

  • 辺のパラメータがちゃんと与えられない場合用の手法らしい

まとめ

  • 伝播にかかる時間を期待時間で固定しちゃっているがいいんだろうか…

INFOCOM 情報拡散

2014-07-01 23:05:31 (Tue)

タグ:

INFOCOM 情報拡散
最終更新:2014年07月01日 23:05