Statistical methods for diameter constrained reliability estimation in rare event scenarios

The object under study is a metric associated to each graph, called diameter constrained reliability. The exact evaluation of the diameter constrained reliability belongs to the class of NP-Hard problems, and becomes prohibitive in large graphs. In the literature, several estimation methods have been developed, inspired in statistics, combinatorics, algebra and other branches of knowledge. We are focused on the statistical evaluation of the diameter constrained reliability under rare event scenarios. Under these assumptions (highly reliable networks), Crude Monte Carlo method is not accurate. More sophisticated methods meet both accuracy and bounded relative error. We compare the performance of two variance reduction methods, to know, Approximate Zero Variance Importance Sampling (AZVIS) and Recursive Variance Reduction (RVR). These methods are compared to Crude Monte Carlo in terms of accuracy and computational effort. Numerical comparisons show the improvement in the global performance of these alternative statistical methods. The paper is closed with a discussion of novel hybrid methods to address network reliability analysis in robust networks, when failures represent a rare event.