Maximizing the Spread of Cascades Using Network Design

Daniel Sheldon, Bistra Dilkina, Adam Elmachtoub, Ryan Finseth, Ashish Sabharwal, Jon Conrad, Carla Gomes, David Shmoys, Will Allen, Ole Amundsen, William Vaughan
Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, PMLR R8:516-525, 2010.

Abstract

We introduce a new optimization framework to maximize the expected spread of cascades in networks. Our model allows a rich set of actions that directly manipulate cascade dy- namics by adding nodes or edges to the net- work. Our motivating application is one in spatial conservation planning, where a cas- cade models the dispersal of wild animals through a fragmented landscape. We propose a mixed integer programming (MIP) formu- lation that combines elements from network design and stochastic optimization. Our ap- proach results in solutions with stochastic op- timality guarantees and points to conserva- tion strategies that are fundamentally differ- ent from naive approaches.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR8-sheldon10a, title = {Maximizing the Spread of Cascades Using Network Design}, author = {Sheldon, Daniel and Dilkina, Bistra and Elmachtoub, Adam and Finseth, Ryan and Sabharwal, Ashish and Conrad, Jon and Gomes, Carla and Shmoys, David and Allen, Will and Amundsen, Ole and Vaughan, William}, booktitle = {Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence}, pages = {516--525}, year = {2010}, editor = {Grünwald, Peter and Spirtes, Peter}, volume = {R8}, series = {Proceedings of Machine Learning Research}, month = {08--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r8/main/assets/sheldon10a/sheldon10a.pdf}, url = {https://proceedings.mlr.press/r8/sheldon10a.html}, abstract = {We introduce a new optimization framework to maximize the expected spread of cascades in networks. Our model allows a rich set of actions that directly manipulate cascade dy- namics by adding nodes or edges to the net- work. Our motivating application is one in spatial conservation planning, where a cas- cade models the dispersal of wild animals through a fragmented landscape. We propose a mixed integer programming (MIP) formu- lation that combines elements from network design and stochastic optimization. Our ap- proach results in solutions with stochastic op- timality guarantees and points to conserva- tion strategies that are fundamentally differ- ent from naive approaches.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Maximizing the Spread of Cascades Using Network Design %A Daniel Sheldon %A Bistra Dilkina %A Adam Elmachtoub %A Ryan Finseth %A Ashish Sabharwal %A Jon Conrad %A Carla Gomes %A David Shmoys %A Will Allen %A Ole Amundsen %A William Vaughan %B Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2010 %E Peter Grünwald %E Peter Spirtes %F pmlr-vR8-sheldon10a %I PMLR %P 516--525 %U https://proceedings.mlr.press/r8/sheldon10a.html %V R8 %X We introduce a new optimization framework to maximize the expected spread of cascades in networks. Our model allows a rich set of actions that directly manipulate cascade dy- namics by adding nodes or edges to the net- work. Our motivating application is one in spatial conservation planning, where a cas- cade models the dispersal of wild animals through a fragmented landscape. We propose a mixed integer programming (MIP) formu- lation that combines elements from network design and stochastic optimization. Our ap- proach results in solutions with stochastic op- timality guarantees and points to conserva- tion strategies that are fundamentally differ- ent from naive approaches. %Z Reissued by PMLR on 04 October 2026.
APA
Sheldon, D., Dilkina, B., Elmachtoub, A., Finseth, R., Sabharwal, A., Conrad, J., Gomes, C., Shmoys, D., Allen, W., Amundsen, O. & Vaughan, W.. (2010). Maximizing the Spread of Cascades Using Network Design. Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R8:516-525 Available from https://proceedings.mlr.press/r8/sheldon10a.html. Reissued by PMLR on 04 October 2026.

Related Material