Efficient message passing for cascade size distributions on finite trees
arXiv:1811.06872
Abstract
How big is the risk that a few initial failures of networked nodes amplify to large cascades that endanger the functioning of the system? Common answers refer to the average final cascade size. Two analytic approaches allow its computation: a) (heterogeneous) mean field approximation and b) belief propagation. The former applies to (infinitely) large locally tree-like networks, while the latter is exact on finite trees. Yet, cascade sizes can have broad and multi-modal distributions that are not well represented by their average. Full distribution information is essential to identify likely events and to estimate the tail risk, i.e. the probability of extreme events. Here, we lay the basis for a general theory to calculate the cascade size distribution in finite networks. We present an efficient message passing algorithm that is exact on finite trees and a large class of cascade processes. An approximation version performs well on locally tree-like networks.
References in corpus (12)
- Emergence of scaling in random networks
- Random graphs with arbitrary degree distributions and their applications
- The spread of epidemic disease on networks
- Optimal Dynamical Range of Excitable Networks at Criticality
- Survey propagation: an algorithm for satisfiability
- Containing epidemic outbreaks by message-passing techniques
- Elimination of systemic risk in financial networks by means of a systemic risk transaction tax
- Rare events and discontinuous percolation transitions
- Systemic risk in multiplex networks with asymmetric coupling and threshold feedback
- How Damage Diversification Can Reduce Systemic Risk
- A framework for cascade size calculations on random networks
- Reconstructing parameters of spreading models from partial observations