New Method for Complex Network Reliability Analysis through Probability Propagation

Reliability analysis of complex networks is often limited by increasing dimensionality of the problem as the number of nodes and possible paths in the network increases. This is true particularly for reliability analysis problems that exponentially increase in computational requirements with system size. In this paper, we present a new method for complex network reliability analysis. We call this the probability propagation method (PrPm). The idea originates from the concept of belief propagation for inference in network graphs. In PrPm, the message passed between nodes is a joint probability distribution. At each step, the distribution is updated and passed as the message to its direct neighbors. After the message passes to the terminal node, an estimation of the network reliability is found. The method results in an analytical solution for system reliability. We present the derived updating rules for message passing and apply the method to two test applications: a system distribution network and general grid network. In the message passing, some approximations are made. Results from the applications show high accuracy for the proposed method compared to exact solutions where possible for comparison. In addition, PrPm achieves orders of magnitude increases in computational efficiency compared to existing approaches. This includes reducing the computational cost for analyses from an exponential increase in computation time with the size of the system to a quartic increase. The method enables the accurate and computationally tractable calculation of failure probabilities of large, generally connected systems