  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.
