Maximizing the Extent of Spread in a Dynamic Network

Maximizing the Extent of Spread in a Dynamic Network

  • Habiba, Tanya Y. Berger-Wolf
  • ? 2007

概要

  • 動的ネットワークでinfluence maximizationやるお!

問題定義

  • Dynamic Network
    • G_t = (V_t, E_t)の列
    • 特定の時点のものだから,辺は消えたりする
  • Independent Cascade Modelの拡張
    • uが時刻tでactiveだったら(u_t, v_t)なv_tを伝播確率でactivate
    • 成功したらvは時刻t+1でactiveになる
    • 一旦activeになったらずっとactive
    • 他の時刻で辺があったらまた試行できる
    • σ(A): 最終時刻でactiveな頂点数
  • Linear Threshold Modelも似た感じ
  • 基本的な性質は成り立つの貪欲すうr

実験

  • 高速化とかではないのでデータセットは超小さい
  1. 最適解と貪欲アルゴリズムの比較
    • 1-1/eよりはかなり良い
  2. dynamicの時とstaticの時の比較
    • dynamicの方が値を大きくするのは難しいね
    • staticとして求めるとdynamicでさらに悪くなる
      • dynamicとstaticは違うのはちゃんとやらんといけない

まとめ

  • dynamicというかtemporal?

dynamic graphs influence maximization

2014-05-22 17:14:14 (Thu)

最終更新:2014年05月22日 17:14