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

Area of Science:

• Network Science
• Computational Epidemiology
• Information Propagation Modeling

Background:

• Cascade models are crucial for understanding epidemic and information spread.
• Current methods for analyzing cascade models, such as sampling, are often inefficient or inaccurate.
• Optimization tasks like influence maximization and parameter inference depend on accurate cascade model analysis.

Purpose of the Study:

• To present an efficient message passing algorithm for computing cascade size probabilities.
• To address the limitations of sampling-based approaches in cascade modeling.
• To provide an accurate and scalable method for analyzing cascade dynamics on various network topologies.

Main Methods:

• Developed an efficient message passing algorithm.
• Applied the algorithm to the Independent Cascade Model on weighted directed networks.
• Algorithm computes the exact probability distribution of cascade size.

Main Results:

• The algorithm is exact on tree networks.
• It provides good approximations for locally treelike networks.
• The method scales efficiently to large networks and performs well on dense networks.

Conclusions:

• The proposed message passing algorithm offers an efficient and accurate alternative to sampling for cascade model analysis.
• This approach enhances the study of epidemic spreading and information propagation.
• The algorithm's scalability and performance on real-world data demonstrate its practical utility.