On Budgeted Influence Maximization in Social Networks - todo314 @ ウィキ

On Budgeted Influence Maximization in Social Networks

• Huy Nguyen, Rong Zheng
• JSAC 2013

概要

• 頂点に単一でないコストがついた影響最大化
• 貪欲アルゴリズムをちょっと変形して1-1/√e近似
• σを効率良く求めるためにDAGを作って信念伝搬っぽいことをやる

Budgeted Influence Maximization

• 情報拡散モデルはIC
• max σ(S) s.t. c(S)≦b
  • c(S)はc(u)(u∈S)の総和
• [σ(S+v)-σ(S)]/c(v)で貪欲に選ぶと近似比が任意に悪くなる
  • Leskovecのでも説明してたな…
• Improved Greedy
  • ↑に従って貪欲に選んだシード集合とs = arg max σ(v)の内の良い方を返す
  • Leskovecのやつは最後まで選んでいたから下位互換な気がする…
• Improved Greedyは近似比1-1/√e(≒0.394)
  • (1-1/e)/2(≒0.316)より良い←まじか
• 高々σの計算回数はn^2
  • もしかしたらn個選ぶかもしれないから

実験

• 262K, 1.2Mが最大
• 割りと真面目な方がちゃんとした解を出している
• ヒューリスティクスで端折った方が速い

σの計算

• とりあえず難しいので辺を削ってDAGにすることを考える
• LTモデル
  • DAGなら簡単
• ICモデル
  • DAGでも#P-hard
• ↑なので，ベイジアンネットワークのBelief propagationみたいなことをする
  • Loopy BPとそれを早くしたSPBP
• DAGの構築
  • PMIAっぽいことをする（2種類）
• 必要なσの計算回数を減らす
  • 構築したDAGでなら判定できるらしい

まとめ

• 1-1/√eは謎なので調べる
• O(n^4d)回計算OKなら1-1/eもできるらしい

JSAC 影響最大化

2014-06-09 14:08:21 (Mon)