Maximizing the Spread of Cascades Using Network Design
-
Daniel Sheldon, Bistra Dilkina, Adam N. Elmachtoub, Ryan Finseth, Ashish Sabharwal, Jon Conrad, Carla P. Gomes, David Shmoys, William Allen, Ole Amundsen, William Vaughan
-
UAI 2010
-
We apply our model to a sustainability problem that is part of an ongoing collaboration with The Conservation Fund to optimize the conservation of land to assist in the recovery of the Red-cockaded Woodpecker (RCW)だそうだ.
問題定義
-
影響力は一般的な集合上の関数
-
頂点では無く,行動を選ぶとする
-
予算Bが上限
-
頂点が非アクティブに戻るケースを考える
-
戻る確率はβ
-
多層なグラフにすれば,v_iからv_i+1に1-βの確率の辺を張れば良い
-
「行動」として頂点・辺の追加(というか生存?)も考える
-
頂点集合を加える(辺も同時に)
-
このへんのせいでsubmodularじゃない
-
2つの行動を同時にとって初めて値が大きく増えるとかいうケースがある
手法
-
Sample Average Approximation
-
先にカスケードグラフを生成しておく
-
混合整数計画で定式化できる
-
グラフ数を変えながら,上限とか下限とかを見積もれるらしい
-
前処理
-
事前に生成しているからできる
-
Pruning: 必要ない頂点を刈ったりする
-
Collapsing Sources
-
SCCしたりする
実験
-
比較対象
-
一様コストとしてgreedy,コストで割ったゲインを考慮するgreedyの2つ
-
データセットはめんどいので省略
-
greedyがそんなに悪くない
-
めっちゃ速くなったよ
-
提案した高速化(再利用とか前計算)を適用すると,greedyも超早くなったよ
まとめ
-
StaticGreedyは初出で無かった….
-
submodularで無いがいいんだろうか…
UAI influence maximization 影響最大化
2014-03-22 18:37:24 (Sat)
最終更新:2014年03月22日 18:37