Real-Time Influence Maximization on Dynamic Social Streams - todo314 @ ウィキ

Real-Time Influence Maximization on Dynamic Social Streams

• Yanhao Wang, Qi Fan, Yuchen Li, Kian-Lee Tan
• VLDB 2017

概要

• クエリ Stream Influence Maximization
  • sliding windowモデルで考える
• Influential Checkpoints
  • 途中途中で結果をとっておいて ε-近似
• Sparse Influential Checkpoints
  • チェックポイントの数が多すぎるので、対数個くらいにまで減らす
  • (log N)/β個で、ε(1-β)/2-近似

問題定式化

• 行動 $$ a_t = \langle u, a_{t'} \rangle $$
  • 意味：uは$$a_{t'}$$に影響を受けて$$a_t$$した。
• ある種のトピック毎の行動を分類できる
• で、I_t(S) := （適当なtime windowでの）Sから（どれかの行動の木を辿って）到達可能な頂点数
  • トピックごとのグラフの到達可能頂点集合のunionってだけでは？
• 本当には単調劣モジュラ関数f(I_t(S))で考えるけど、論文ではf(A)=|A|のみ
• ∴確率的拡散過程は以後考えない or blackbloxとする

アルゴリズム

• 行動が来るたびに、一番古いのを消す
• ストリーム劣モジュラ最大化を信託として、途中の結果を保持しておく感じ
• 途中結果が多いと嫌なので、疎にする

実験

• 比較手法：IMM, UBI, 貪欲, Influential Checkpoints, Sparse Influential Checkpoints
• 指標：WC設定の影響拡散をMonte-Carloで推定（何故？）

まとめ

• [Ohsaka-Akiba-Yoshida-Kawarabayashi. VLDB'16]について、 In fact, the state-of-the-art dynamic IM solution [30] can only process several hundred updates per second, which is far lower than the update rates of real-world social networks
• と言っているが、モデルが全然違う(´・ω・`)

VLDB 影響最大化

2017/10/01