Scalable Influence Maximization in Social Networks under the Linear ... - todo314 @ ウィキ

Scalable Influence Maximization in Social Networks under the Linear Threshold Model

• Wei Chen, Yifei Yuan, Li Zhang
• In ICDM 2010

概要

• LTモデル用の高速アルゴリズム
• LTモデルでのσの計算は#P-hard
• DAGをとってきて、それの上で高速計算

#P-hardness

• 基本は単純経路の数え上げからの帰着

アルゴリズム

• LTモデルからlive-edge graphを考える
• eはw_eの確率で残ると書いてあるが、本当だろうか…？
  • Kempeのではもっと複雑なことをしていた
• こうすると、random graph上でのreachabilityになる
  • LTとかなかった…

DAG上での線形時間アルゴリズム

• 自分がactiveになる確率ap(v)
  • 上から伝播=DPしていけばいい
• v \in Sならap(v)=1と最初にする

LDAGモデル

• 各頂点についてDAGをいっぱい計算して近似
• LTモデルでは「局所的」らしい
  • マジか？
• LDAGの選び方が大事
  • できるだけap(u,v)の和がでかくなると良い（らしい
• LDAG(v): vをrootとするLDAG
• ap(v,S)はLDAG(v)だけを通ってのactivation確率
• σ(S)=Σap(v,S)
  • LDAG(v)は逆か？vが最下層になっているのか？

LDAGの構築

• 結局しきい値θで制限する
  • あんまり確率が小さいなら省略

更新

• 超頑張る

実験

データセット

• Amazon, DBLPとかで2Mが最大

伝播確率

• degree
• uniformly at random

速度

• そこそこ、DBLPで300s
• LDAG毎のノード・リンク数は小さめ、それぞれ50・150とか

influence spread

• 流石にPageRankやDDよりは相当良い
• Greedyに近い
• GreedyはRの値を変えた版もやっている
  • 100じゃ全く足りない
• DAGの選び方も変えている
  • ランダムだと駄目みたい

まとめ

• DAG上で上手くいく、というのはよくあるけど、誰もやっていないのでいいか
• PMAIもそうだけど、θのようなパラメータで制御する、というのは、精度と時間のトレードオフを制御できる、という面でいいのかなあ
• しかし、このpaperでは（まえじっけんしただけで）どう変わるか見てないからなあ
  • PMIAはやってた

ICDM influence maximization

2013-10-27 21:58:19 (Sun)