Network Reliability Analysis and Complexity Quantification Using Bayesian Network and Dual Representation

Abstract

Modern society operates upon various lifeline networks such as transportation networks, power networks, and gas distribution networks. To secure their reliable operations, it is critical to evaluate their reliability. However, as those networks become more complex and larger-scale, their reliability analysis faces increasing computational cost. That is, reliability methods often suffer from exponential increase in their computational complexity with regard to the number of components. While such exponential increase can be circumvented by employing simulation-based approaches, they are bound to become inefficient with low failure probabilities. In such cases, they often require a large number of samples (i.e., many network evaluations) or face the risk of adopting biased estimates.

In this study, we propose an efficient method of reliability analysis for networks whose performance is evaluated by maximum flow analysis (one of whose special case is connectivity analysis). The idea is that by employing Bayesian network (BN), structural failures and functional failures of network components (i.e., edges and/or nodes) are separately modelled. Thereby, analysis complexity no longer depends simply on network size (i.e., the number of component events), but also on network topology. Once a BN model is established, one can employ existing BN inference algorithms to carry out reliability analysis.

The advantages of the proposed method are three-fold. First, it can compute exact failure probability of large-scale networks that were previously considered to be too large for an exact analysis. Second, by using existing BN algorithms whose general-purpose software programs are readily available, its implementation remains accessible. Finally, it enables us to quantify complexity of network topology (from the perspective of reliability analysis), which remains a challenging task.

The primary constraint of the proposed method is that a given network should include no cycles. However, we present a scheme that enables us to handle a network with, though not many, a few cycles. We also present tactics to address dependence between component events. As a numerical example, a large-scale road network is analyzed to demonstrate the efficiency and utility of the proposed method.