「On Budgeted Influence Maximization in Social Networks」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
* 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もできるらしい
&tags()
&update()
