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})] $$
-
この辺りは当たり前のことを言っているようにみえたが、
-
重要なのは、このやり方の方が分散が小さい、ということ
-
単純に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)
Efficient Local Greedy Algorithm (ELGA)
-
wから逆にたどれば、各頂点から到達可能かをまとめて計算できる
Local Cascade Algorithm (LCA)
-
最短路木っぽいのを持っておく?
-
オンライン向けらしい
実験
比較対象
データセット
-
Epinions、Wikipedia(何で?)
-
WPは(2M,5M)
結果
-
まぁよいよね
-
LGAは重すぎるらしい
-
ELGAも1000secくらい?
まとめ
-
この問題だとまぁ早くしやすいわな
-
特定個人に注目するのはいいんだけど、1人だけだったら、その人に直接宣伝すればいいんじゃね?
-
ちゃんと読まんとモチベーションが分からんのかも?
-
直接やっちゃいけなくて、裏から攻めていくみたいな、何かがあるのか?
-
解析は分散が小さくなるってところが面白かった、ほかは普通
-
アルゴリズムは普通だった
-
実験はLiveJournalとかやらんのかね…
CIKM influence maximization
2013-11-04 19:59:41 (Mon)
最終更新:2013年11月04日 19:59