On Influential Nodes Tracking in Dynamic Social Networks
-
Xiaodong Chen, Guojie Song, Xinran He, Kunqing Xie
-
SDM 2015
概要
-
動的グラフでの影響最大化
-
今のシードを交換ヒューリスティック
-
影響力の評価は上限ベースの手法も使って枝刈り
提案手法
-
[Nemhauser-Wolsey-Fisher. '78]の交換ヒューリスティック
-
あまりシード集合が変わらないはずだからという観察
-
$$ S' = S-v_s+v^* $$
-
$$ v^* \in V \setminus S $$: 一番上昇する奴
-
$$ v_s $$: 上限使って一番良さそうなの
-
|S|回ループ
-
$$v_s^*$$: 上限使って一番良い奴
-
遅延評価+適当な打切,でSを更新
-
上限を更新
上限の計算
実験
-
(n, m): (5M, 12M), (30K, 300K), (20K, 100K)
-
データセットの作り方がちょっと違う(時間窓で区切ってる)
-
辺確率: (入次数)$$^{-1}$$ (だけ. (゚Д゚)ハァ?)
-
実行時間と影響力
-
スケーラビリティ
-
類似度 vs. 更新時間
-
tとt+1のJaccard係数を計算; 変化が小さい方が速い
-
上限の計算手法の比較
まとめ
-
ヒューリスティックは面白いけれど,手法はそんなに.
SDM 動的グラフ 影響最大化
2016/02/15
最終更新:2016年02月16日 00:56