Maximizing the Spread of Cascades Using Network Design

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