Influence Maximization in Near-Linear Time: A Martingale Approach
-
Youze Tang, Yanchen Shi, Xiaokui Xiao
-
SIGMOD 2015
概要
TIMの問題点
-
最悪時には下限が最適値よりn/k倍悪い
-
下限の計算自体が結構(シード選択段階よりも)遅い
提案手法 Influence Maximization via Martingales (IMM)
-
違い
-
RR集合を使いまわしていい
-
必要なRR集合の個数が少し改善(見た目が複雑だけど)
-
直接OPT_kの下限を推定
-
HINT:「最適値が大きい?」の検証に必要なRR集合の個数は小さい
-
アルゴリズム
-
下限の候補値$$ x = n, n/2, n/4, \ldots $$
-
$$ \lambda' / x $$個になるまでRR集合をサンプル
-
$$ ``下限 > x?'' $$を検証
-
貪欲した解の影響拡散(の推定値)が(1+ε')x以上か確認
-
yesだったら下限を適当に計算して抜ける
-
$$ \theta = \lambda^* / 下限 $$としていつものをやる
そのた
-
Reverse Influence Setを提案
-
連続時間モデルへの適用例
-
RI集合は距離T以内で行ける所、なので、Dijkstra的な事をすればOK
実験
-
辺確率:1/入次数 ٩(๑òωó๑)۶
-
比較手法:TIM,TIM+,IRIE,SIMPATH
-
ε=0.5ってでかくね?
まとめ
SIGMOD 影響最大化
2017/10/01
最終更新:2017年10月01日 19:42