A Novel and Model Independent Approach for Efficient Influence Maximization ... - todo314 @ ウィキ

A Novel and Model Independent Approach for Efficient Influence Maximization in Social Networks

• Hemank Lamba, Ramasuri Narayanam
• WISE 2013

概要

• influence maximizationの手法は大体はモデルに強く依存する(・A・)ｲｸﾅｲ!!
• sparsificationするよ！
• 精度を落とさずに数倍高速化

提案手法

• ある頂点の近傍のスコアを出す
• スコアの出し方
  • 色々な基準を大量に持ってくる
  • 適当に重みを計算して足し合わせる
• スコアの大きい近傍をdeg(i)^eだけ残す
  • 0<=e<=1

実験

• 基準
  • 次数とか共通近傍とかJaccard係数とか色々
• e=0.9ならそこそこ大丈夫だけど実行時間半分くらい
• e=0.5だとσが減る、あんまり早くない

まとめ

• モデルのパラメータも使わないのは何か説得力に欠けるな～
• 今回はpが同じなので、次数順に選べばそこそこまともなのが得られるし
• 本質的にこの問題にはsparsificationを使うのは難しそう
  • σの概算には冗長性が効いているので

WISE influence maximization

2014-02-02 20:51:54 (Sun)