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の確率で残ると書いてあるが、本当だろうか…?
-
こうすると、random graph上でのreachabilityになる
DAG上での線形時間アルゴリズム
-
自分がactiveになる確率ap(v)
-
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の構築
更新
実験
データセット
伝播確率
-
degree
-
uniformly at random
速度
-
そこそこ、DBLPで300s
-
LDAG毎のノード・リンク数は小さめ、それぞれ50・150とか
influence spread
-
流石にPageRankやDDよりは相当良い
-
Greedyに近い
-
GreedyはRの値を変えた版もやっている
-
DAGの選び方も変えている
まとめ
-
DAG上で上手くいく、というのはよくあるけど、誰もやっていないのでいいか
-
PMAIもそうだけど、θのようなパラメータで制御する、というのは、精度と時間のトレードオフを制御できる、という面でいいのかなあ
-
しかし、このpaperでは(まえじっけんしただけで)どう変わるか見てないからなあ
ICDM influence maximization
2013-10-27 21:58:19 (Sun)
最終更新:2013年10月27日 21:58