Influence Maximization in Continuous Time Diffusion Networks - todo314 @ ウィキ

Influence Maximization in Continuous Time Diffusion Networks

• Manuel Gomez-Rodriguez, Bernhard Schölkopf
• ICML 2012

概要

• Uncovering the Temporal Dynamics of Diffusion Networksの続き
• 連続時間モデル上の影響最大化を提案
• 影響拡散がシミュレーション以外の方法で効率的に求められる
• 1-1/e近似が可能
• 実験したよ

問題定式化

• f(t_j | t_i; α_{i,j}) ∝ exp(-α_{i,j}(t_j-t_i))
  • つまり，遅延時間の分布が指数関数
  • 他の関数でも使える
• 情報拡散過程は普通
  • 時間遅延があるから，全く意味ない辺や頂点も出てくる
• 時刻T以内に活性化する頂点数の期待値を最大化したい

提案手法

• 1986の結果を使う
  • Shortest paths in networks with exponentially distributed arc lengths
  • それっぽい名前のタイトル
• 頂点集合をブロックする（消す）ことでターゲット頂点に到達不可能になる頂点集合を考えたりする
• 最終的に行列計算でできるらしい
  • #P-hardなのに？と思ったが何らかのパラメータが指数的になるかもしれないらしい
  • しかし，それは実際のネットワークでは小さいらしい
• 高速化
  • Leskovecの遅延評価
  • 各頂点について遠い頂点を枝刈り
    • やばそう

実験

• 1K頂点くらいの小さいグラフで実験しているぽい
• 何故かGreedyが思い切り負けている，どういうこと？

ICML 影響最大化 情報拡散 情報拡散モデル

2014-05-21 23:12:56 (Wed)