Efficient computation of marginal reliability-importance for reducible(+) networks

Abstract

Marginal reliability importance (MRI) of a link with respect to terminal-pair reliability (TR) is the rate to which TR changes with the modification of the success probability of the link. It is a quantitative measure reflecting the importance of the individual link in contributing to TR of a given network. Computing MRI for general networks is an NP-complete problem. Attention has been drawn to a particular set of networks (reducible networks), which can be simplified to source-sink (2-node) networks via 6 simple reduction rules (axioms). The computational complexity of the MRI problem for such networks is polynomial bounded. This paper proposes a new reduction rule, referred to as triangle reduction. The triangle reduction rule transforms a graph containing a triangle subgraph to that excluding the base of the triangle, with constant complexity. Networks which can be fully reduced to source-sink networks by the triangle reduction rule, in addition to the 6 reduction rules, are further defined as reducible(+) networks. For efficient computation of MRI for reducible(+) networks, a 2-phase (2-P) algorithm is given. The 2-P algorithm performs network reduction in phase 1. In each reduction step, the 2-P algorithm generates the correlation, quantified by a reduction factor, between the original network and the reduced network. In phase 2, the 2-P algorithm backtracks the reduction steps and computes MRI, based on the reduction factors generated in phase 1 and a set of closed-form TR formulas. As a result, the 2-P algorithm yields a linearly bounded complexity for the computation of MRI for reducible+ networks. Experimental results from real networks and benchmarks show the superiority, by two orders of magnitude, of the 2-P algorithm over the traditional approach.