Extracting Influential Nodes for Information Diffusion on a Social Network

Extracting Influential Nodes for Information Diffusion on a Social Network

  • Masahiro Kimura, Kazumi Saito, Ryohei Nakano
  • AAAI 2007

概要

  • influence maximizationの高速アルゴリズム
    • ICとLT

提案手法

  • ICもLTもランダムグラフを考えればいい
  • σの増加量を効率的にもとめる
  • 事前にランダムグラフを作っておく
  • シード集合: A
  • Aから到達可能な頂点を除く
  • 頂点uについて,↑で出来たグラフでuから到達可能な頂点数Fをもとめる
  • uと同じ連結成分に入っている頂点vについて,σ_i(A∪{v})=σ_i(A)+Fとする

実験

  • 250K辺のが最大
  • ICはp=0.1,LTは次数重み
  • 提案手法の方がシミュレーション回数が少なくても良い解が出せている
  • 現状のシード集合に関するσは全部同じだから依存しないため,みたいな説明
  • 最大で数千倍高速化

まとめ

  • StaticGreedyにかなり近いので驚いた,強連結成分も考慮しているのでもう少し効率が良い
  • 回数が少なくても良い解が出る説明もしているので良い

AAAI influence maximization

2014-02-15 01:20:37 (Sat)

最終更新:2014年02月15日 01:20