Influence Maximization with Novelty Decay in Social Networks - todo314 @ ウィキ

Influence Maximization with Novelty Decay in Social Networks

• Shanshan Feng, Xuefeng Chen, Gao Cong, Yifeng Zeng, Yeow Meng Chee, Yanping Xiang
• AAAI 2014

概要

• 目新しさの減衰を考慮した情報拡散モデル
• 非単調だし非劣モジュラ

Novelty Decay

• 実データセットを調査
• n人の友達が既に影響されているとする
• nが大きい程，その人自信は影響されやすいけれど，徐々にその効果が弱まるはず
• (nの時の確率 / n-1の時の確率)みたいなものを計算すると，f(n) = γ^{n-1}くらい
• これを根拠

IC Model with Novelty Decay

• 各辺には時間がある
• 時間に沿って活性化試行が行われていく
• u→vの成功確率はp_uv×f(n)
  • 既にvはn回試行されているとする
• 後は同じ
• 条件は|S|≦K

性質

• f(n)とすればただのIC
• 非単調
• 非劣モジュラ

提案手法

• R-Greedy Algorithm
  • (Lu and Lakshmanan 2012)のU-Greedyを改造
  • とりあえず，増大する頂点とっていって一番よさげなのをとってくる
• 適当な枝刈り

σの計算方法

• Monte-Carloシミュレーションか伝播経路を限ってる(っぽい?)

まとめ

• 手法自体に面白みは無いなあ
• 実際のデータから根拠を取ってきた点が評価されたんだろうか…
• これ以降，微妙に性質を満たさないモデルとかが乱発されるんだろうか…

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

2014-08-20 19:28:34 (Wed)