Efficient message passing for cascade size distributions.

Area of Science:

• Network science
• Complex systems analysis
• Computational modeling

Background:

• Networked systems face risks from cascading failures originating from initial node malfunctions.
• Current analysis often relies on average cascade size, which can obscure critical distribution information.
• Existing analytical methods like mean field approximation and belief propagation have limitations in accurately representing cascade size distributions in finite networks.

Purpose of the Study:

• To develop an efficient algorithm for calculating the complete cascade size distribution in finite networks.
• To provide a method for identifying likely cascade events and estimating tail risks (probability of extreme events).
• To offer solutions applicable to various network structures and cascade processes.

Main Methods:

• Development of an efficient message passing algorithm to compute cascade size distributions.
• Algorithm's exactness on finite trees and for a broad class of cascade processes.
• An approximate version of the algorithm designed for general network structures.

Main Results:

• The proposed message passing algorithm accurately calculates cascade size distributions in finite networks.
• The algorithm is exact for finite trees and specific cascade processes.
• An approximate version demonstrates good performance on locally tree-like networks.

Conclusions:

• The developed algorithm provides crucial full distribution information for assessing cascade risks in networked systems.
• This approach moves beyond average metrics to better understand and mitigate tail risks.
• The method offers a valuable tool for analyzing system resilience in diverse network configurations.