Static Network Reliability Estimation via Generalized Splitting
- 1 February 2013
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 25 (1), 56-71
- https://doi.org/10.1287/ijoc.1110.0493
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.Keywords
This publication has 29 references indexed in Scilit:
- Combination of conditional Monte Carlo and approximate zero-variance importance sampling for network reliability estimationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2010
- Rare Event Analysis by Monte Carlo Techniques in Static ModelsPublished by Wiley ,2009
- The recursive variance-reduction simulation algorithm for network reliability evaluationIEEE Transactions on Reliability, 2003
- Monte Carlo Methods in Bayesian ComputationPublished by Springer Science and Business Media LLC ,2000
- An Evolution Model for Monte Carlo Estimation of Equilibrium Network Renewal ParametersProbability in the Engineering and Informational Sciences, 1992
- Estimation of network reliability using graph evolution modelsIEEE Transactions on Reliability, 1991
- A Monte Carlo Sampling Plan for Estimating Network ReliabilityOperations Research, 1986
- Bounds on the Reliability Polynomial for Shellable Independence SystemsSIAM Journal on Algebraic Discrete Methods, 1982
- Association of Random Variables, with ApplicationsThe Annals of Mathematical Statistics, 1967
- Bounds for Distributions with Monotone Hazard Rate, IThe Annals of Mathematical Statistics, 1964