Cascade Size Distributions: Why They Matter and How to Compute Them Efficiently

Authors

  • Rebekka Burkholz Harvard T.H. Chan School of Public Health, Boston, MA 02115
  • John Quackenbush Harvard T.H. Chan School of Public Health, Boston, MA 02115 Harvard Medical School, Boston, MA 02115

DOI:

https://doi.org/10.1609/aaai.v35i8.16844

Keywords:

Probabilistic Graphical Models, Graph-based Machine Learning, Graph Mining, Social Network Analysis & Community

Abstract

Cascade models are central to understanding, predicting, and controlling epidemic spreading and information propagation. Related optimization, including influence maximization, model parameter inference, or the development of vaccination strategies, relies heavily on sampling from a model. This is either inefficient or inaccurate. As alternative, we present an efficient message passing algorithm that computes the probability distribution of the cascade size for the Independent Cascade Model on weighted directed networks and generalizations. Our approach is exact on trees but can be applied to any network topology. It approximates locally tree-like networks well, scales to large networks, and can lead to surprisingly good performance on more dense networks, as we also exemplify on real world data.

Downloads

Published

2021-05-18

How to Cite

Burkholz, R., & Quackenbush, J. (2021). Cascade Size Distributions: Why They Matter and How to Compute Them Efficiently. Proceedings of the AAAI Conference on Artificial Intelligence, 35(8), 6840-6849. https://doi.org/10.1609/aaai.v35i8.16844

Issue

Section

AAAI Technical Track on Machine Learning I