On minimizing budget and time in influence propagation over social networks - todo314 @ ウィキ

On minimizing budget and time in influence propagation over social networks

• Amit Goyal, Francesco Bonchi, Laks V. S. Lakshmanan
• Social Network Analysis and Mining (SNAM) 2012

MINTSS (minimum target set selection)

• 入力: 閾値η
• 出力: σ(S)≧ηなる最小サイズのS
• 提案手法: 貪欲算法
  • σ(S)＜η-εの間，増量（min{σ(S+t),η}で考える）が最大の頂点をSに追加
• 定理1: 貪欲算法で双基準近似
  • σ(S)≧η-ε
  • |S|≦(1+ln(n/ε))OPT
• 関連
  • real-valued submodular set cover

MINTIME

• 入力: 閾値η，予算k
• 出力: S (|S|=k)と最小のt
  • 時刻tでは期待値的にσ(S)≧η
• 定理4: 双基準近似は難しい
  • k以下の予算
  • (1-1/e)η以上被覆
• 定理5も似た感じ？
• 定理6: 三基準近似
  • σ^R(S: 時刻Rでの影響拡散
  • 以下の貪欲算法を考える
  1. R=0 to n-1
     1. σ^R()について貪欲
• (時間，予算，被覆)の近似比として(1,1+ln(n/ε), 1-ε/n)が得られる

実験

• 貪欲の良さ
• ヒューリスティクスとの乖離，次数とかPMIAとか
• MINTSS
  • 確率がで解法がGapがでかいっぽい
• MINTIME
  • ↑と同じ感じ

まとめ

• 最適化したいものが沢山あるのも大変だなあ
  • 予算と時間と被覆があるから

SNAM 影響最大化 情報拡散

2015/05/18 15:18