Static Network Reliability Estimation via Generalized Splitting

Static Network Reliability Estimation via Generalized Splitting

0.00 Avg rating0 Votes
Article ID: iaor20131718
Volume: 25
Issue: 1
Start Page Number: 56
End Page Number: 71
Publication Date: Dec 2013
Journal: INFORMS Journal on Computing
Authors: , , , ,
Keywords: graphs, networks, quality & reliability
Abstract:

We propose a novel simulation‐based method that exploits a generalized splitting (GS) algorithm to estimate the reliability of a graph (or network), defined here as the probability that a given set of nodes are connected, when each link of the graph fails with a given (small) probability. For large graphs, in general, computing the exact reliability is an intractable problem and estimating it by standard Monte Carlo methods poses serious difficulties, because the unreliability (one minus the reliability) is often a rare‐event probability. We show that the proposed GS algorithm can accurately estimate extremely small unreliabilities and we exhibit large examples where it performs much better than existing approaches. It is also flexible enough to dispense with the frequently made assumption of independent edge failures.

Reviews

Required fields are marked *. Your email address will not be published.