Personalized Influence Maximization on Social Networks - todo314 @ ウィキ

Personalized Influence Maximization on Social Networks

• Jing Guo, Peng Zhang, Chuan Zhou, Yanan Cao, Li Guo
  • 中国科学院の人たち
• CIKM 2013

概要

• influence maximizationの亜種を考案
• 特定のノードにinfluenceする確率を上げたい
• この問題設定における性質とかを挙げてアルゴリズムを設計
• 普通のと、それの高速化と、ヒューリスティクスっぽいの
• ベースラインを比較していいことを示した

問題

• 目的関数
• $$ R_w(U) = \mathbb{E}^U[1_{\{w \in X\}}] $$
  • ターゲットwがUによりinfluenceされる確率（indicatorの期待値）
• wだけを抜いたグラフを考える
• 特定の事象についてwのある近傍vがactivateされたら、あとはp_vwを考えれば良い
• $$ \mathbb{E}^U[1-\prod_{v\ in Y}(1-p_{vw})] $$
  • Yはactivateされた頂点集合
• この辺りは当たり前のことを言っているようにみえたが、
• 重要なのは、このやり方の方が分散が小さい、ということ
  • 単純にwに到達可能か（一番上の式）、よりも、近傍まで到達可能かかつ近傍からwへの確率（2番めの式）、での計算のほうが良い
  • $$ \mathbb{D}^U[1-\prod_{v \in Y}(1-p_{vw})] < \mathbb{D}^U[1_{\{w \in X\}}] $$
  • ただこれは、この問題だからこそ適用できる
• その他性質
  • 最大化はNP-hard
  • influenceの計算は#P-hard

アルゴリズム

Local Greedy Algorithm (LGA)

• Monte-Carloを愚直に試す
  • O(knRm)

Efficient Local Greedy Algorithm (ELGA)

• wから逆にたどれば、各頂点から到達可能かをまとめて計算できる
  • O(kD(m+m*))

Local Cascade Algorithm (LCA)

• 最短路木っぽいのを持っておく？
• オンライン向けらしい

実験

比較対象

• 次数、ランダム、最大次数の近傍

データセット

• Epinions、Wikipedia（何で？）
• WPは(2M,5M)

結果

• まぁよいよね
• LGAは重すぎるらしい
• ELGAも1000secくらい？

まとめ

• この問題だとまぁ早くしやすいわな
• 特定個人に注目するのはいいんだけど、1人だけだったら、その人に直接宣伝すればいいんじゃね？
  • ちゃんと読まんとモチベーションが分からんのかも？
  • 直接やっちゃいけなくて、裏から攻めていくみたいな、何かがあるのか？
• 解析は分散が小さくなるってところが面白かった、ほかは普通
• アルゴリズムは普通だった
• 実験はLiveJournalとかやらんのかね…

CIKM influence maximization

2013-11-04 19:59:41 (Mon)