Influence Maximization in Continuous Time Diffusion Networks
-
Manuel Gomez-Rodriguez, Bernhard Schölkopf
-
ICML 2012
概要
問題定式化
-
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)
最終更新:2014年05月21日 23:12