Cascade Size Distributions: Why They Matter and How to Compute Them Efficiently
This work addresses a bottleneck in optimizing cascade-related tasks such as epidemic spreading and information propagation, offering a more efficient alternative to sampling methods.
The paper tackled the problem of inefficient or inaccurate sampling for cascade models, which are crucial for tasks like influence maximization and epidemic control, by presenting an efficient message passing algorithm that computes cascade size distributions exactly on trees and approximates them well on other networks, scaling to large networks and showing good performance on real-world data.
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.