Analysis of Two Methods for Reliability Estimation on the Static Network Model
DOI:
https://doi.org/10.19153/cleiej.29.2.4Keywords:
network model, Monte Carlo simulation, resilience estimationAbstract
This work discusses the F-Monte Carlo and the Destruction Spectrum Monte Carlo methods for unreliability estimation of the Static Network Model. The objective is to develop a fine analysis using analytical expressions for both methods, designed to work on the homogeneous case, in which the components share the same distribution. For the first time in literature, the variances of these methods are studied using explicit formulas, which are useful, for instance, to study the precision of the procedures. Also, an analytic study of the computational complexity of the algorithms is performed, based on the observation that the most time consuming operation in their implementations is the evaluation of the structure function of the system under study. Both techniques are also compared against the Standard Monte Carlo method. A number of computational experiments are performed to validate the analytic formulas developed in the paper, and thus our results, showing good agreement and cross-validating our starting observation and the simulators used.
References
J. Li, L. Duenas-Osorio, C. Chen, and C. Shi, “Connectivity reliability and topological controllability of iinfrastructure networks: A comparative assessment,” Reliability Engineering and System Safety, vol. 156, pp. 24–33, 2016.
J. Johansson, H. Hassel, and E. Zio, “Reliability and vulnerability analyses of critical infrastructures: Comparing two approaches in the context of power systems,” Reliability Engineering & System Safety, vol. 120, pp. 27 – 38, 2013.
R. Guidotti, P. Gardoni, and N. Rosenheim, “Integration of physical infrastructure and social systems in communities’ reliability and resilience analysis,” Reliability Engineering & System Safety, vol. 185, pp. 476 – 492, 2019.
D. Raad, A. Sinske, and J. Van Vuuren, “Robust multi-objective optimization for water distribution system design using a meta-metaheuristic,” International Transactions in Operational Research, vol. 16, no. 5, pp. 595–626, 2009. [Online]. Available: https://onlinelibrary.wiley.com/doi/abs/10.1111/j.1475-3995.2009.00705.x
S. Dharmaraja, R. Vinayak, and K. S. Trivedi, “Reliability and survivability of vehicular ad hoc networks: An analytical approach,” Reliability Engineering & System Safety, vol. 153, pp. 28 – 38, 2016.
M. Macchi, M. Garetti, D. Centrone, L. Fumagalli, and G. P. Pavirani, “Maintenance management of railway infrastructures based on reliability analysis,” Reliability Engineering & System Safety, vol. 104, pp. 71 – 83, 2012.
J. E. Muriel-Villegas, K. C. Alvarez-Uribe, C. E. Patino-Rodr ˜ ´?guez, and J. G. Villegas, “Analysis of transportation networks ubject to natural hazards - insights from a Colombian case,” Reliability Engineering & System Safety, vol. 152, pp. 151 – 165, 2016.
N. Goldbeck, P. Angeloudis, and W. Y. Ochieng, “Resilience assessment for interdependent urban infrastructure systems sing dynamic network flow models,” Reliability Engineering & System Safety, vol. 188, pp. 62– 79, 2019.
I. Tien and A. D. Kiureghian, “Algorithms for Bayesian network modeling and reliability assessment of infrastructure systems,” Reliability Engineering & System Safety, vol. 156, pp. 134 – 147, 2016.
S. Rath, M. Gendreau, and W. J. Gutjahr, “Bi-objective stochastic programming models for determining depot locations in disaster relief operations,” International Transactions in Operational Research, vol. 23, no. 6, pp. 997–1023, 2016. [Online]. Available: https://onlinelibrary.wiley.com/doi/abs/10.1111/itor.12163
A. Rosenthal, “Computing the reliability of complex networks,” SIAM Journal on Applied Mathematics, vol. 32, no. 2, pp. 384–393, 1977.
S. J. Provan and M. O. Ball, “The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected,” SIAM Journal on Computing, vol. 12, no. 4, pp. 777–788, 1983.
L. Schafer, S. Garc ¨ ´?a, and V. Srithammavanh, “Simplification of inclusion-exclusion on intersections of unions with application to network systems reliability,” Reliability Engineering and System Safety, vol. 173, pp. 23–33, 2018.
K. Kobayashi, H. Morohosi, and T. Oyama, “Applying path-counting methods for measuring the robustness of the network-structured system,” International Transactions in Operational Research, vol. 16, no. 3, pp. 371–389, 2009. [Online]. Available: https://onlinelibrary.wiley.com/doi/abs/10.1111/j.1475-3995.2008.00688.x
H. Kumamoto, K. Tanaka, and K. Inoue, “Efficient evaluation of system reliability by Monte Carlo method,” IEEE Transactions on Reliability, vol. R–26, no. 5, pp. 311–315, Dec. 1977.
H. Kumamoto, K. Tanaka, K. Inoue, and E. Henley, “Dagger–sampling Monte Carlo for system unavailability evaluation,” IEEE Transactions on Reliability, vol. R–29, no. 2, pp. 122–125, June 1980.
M. Easton and C. Wong, “Sequential destruction method for Monte Carlo evaluation of system reliability,” IEEE Transactions on Reliability, vol. R–29, no. 1, April 1980.
G. Fishman, “A comparison of four Monte–Carlo methods for estimating the probability of s–t connectedness,” IEEE ransactions on Reliability, vol. R–35, no. 2, pp. 145–155, June 1986.
——, “A Monte Carlo sampling plan for estimating network reliability,” Operational Research, vol. 34, 1986.
T. Elperin, I. B. Gertsbakh, and M. Lomonosov, “Estimation of network reliability using graph evolution models,” IEEE Transactions on Reliability, vol. 40, no. 5, pp. 572–581, Dec 1991.
M. Lomonosov, “On Monte Carlo estimates in network reliability,” Probability in the Engineering and Informational ciences, vol. 8, pp. 245–264, 1994.
S. M. Ross, “A new simulation estimator of system reliability,” Journal of Applied Mathematics and Stochastic Analysis, vol. 7, no. 3, 1994.
H. Cancela and M. El Khadiri, “A recursive variance–reduction algorithm for estimating communication–network reliability,” IEEE Transactions on Reliability, vol. 44, no. 4, pp. 595–602, December 1995.
——, “The recursive variance–reduction simulation algorithm for network reliability evaluation,” IEEE Transactions on Reliability, vol. 52, no. 2, pp. 207–212, June 2003.
H. Cancela, M. El Khadiri, and G. Rubino, “Rare events analysis by Monte Carlo techniques in static models,” in Rare Event Simulation using Monte Carlo Methods, G. Rubino and B. Tuffin, Eds. John Wiley & Sons, 2009, ch. 7, pp. 145–170.
P. L’Ecuyer, G. Rubino, S. Saggadi, and B. Tuffin, “Approximate Zero-Variance Importance Sampling for Statistic Network Reliability Estimation,” IEEE Transactions on Reliability - TR, vol. 60, no. 3, pp. 590–604, 2011.
L. Murray, H. Cancela, and G. Rubino, “A splitting algorithm for network reliability,” IIE Transactions,vol. 45, no. 2, pp. 177–189, 2013.
K.-P. Hui, N. Bean, M. Kraetzl, and D. Kroese, “The tree cut and merge algorithm for estimation of network reliability,” Probability in the Engineering and Informational Sciences, vol. 17, no. 1, pp. 23–45, 2003.
——, “The cross–entropy method for network reliability estimation,” Annals of Operations Research, vol. 134, pp. 101–118(18), February 2005.
Z. I. Botev, P. L’Ecuyer, R. Simard, and B. Tuffin, “Static network reliability estimation under the MarshallOlkin copula,” ACM Transactions on Modeling and Computer Simulation, vol. 26, no. 2, p. Article 14, 2016.
E. Canale, F. Robledo, P. Romero, and P. Sartor, “Monte carlo methods in diameter-constrained reliability,” Optical Switching and Networking, vol. 14, pp. 134–148, 2014, special Issue on RNDM 2013. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S1573427714000691
N. L. Dehghani, J. Song, and M. Pandey, “Adaptive surrogate-based network reliability analysis through integration of bayesian additive regression trees and monte carlo,” Reliability Engineering & System Safety, vol. 213, p. 107701, 2021.
J. Chan, “A comparative study on sampling-based algorithms for network reliability assessment,” Reliability Engineering & System Safety, vol. 230, p. 108940, 2023.
D. H. Huang, “Network reliability of a stochastic flow network by wrapping lp-based minimal-path models into monte-carlo,” European Journal of Operational Research, 2024, in press.
C. Ding, “Sampling and active-learning methods for efficient network reliability estimation,” IEEE Transactions on Reliability, 2024, early Access.
X. Zhou, Y. Li, and K. Zhang, “Dynamic reliability of infrastructure networks using augmented monte carlo simulation,” Applied Mathematical Modelling, vol. 102, pp. 532–549, 2022.
I. Bjerkebæk and T. Østerdal, “Reliability assessment combining importance resampling and the crossentropy method,” Methodology and Computing in Applied Probability, 2024, online first.
H. P´ erez-Ros´ es, “Sixty years of network reliability,” Mathematics in Computer Science, vol. 12, no. 3, pp. 275–293, 2018.
I. B. Gertsbakh and Y. Shpungin, Models of Network Reliability: Analysis, Combinatorics, and Monte Carlo, 1st ed. USA: CRC Press, Inc., 2009.
G. S. Fishman, Monte Carlo : concepts, algorithms, and applications, ser. Springer series in operations research. New York: Springer-Verlag, 1996.
I. Gertsbakh, R. Rubinstein, Y. Shpungin, and R. Vaisman, “Permutational methods for performance analysis of stochastic flow networks,” Probability in the Engineering and Informational Sciences, vol. 28, no. 1, pp. 21–38, 2014.
F. Samaniego, “On closure of the IFR class under formation of coherent systems,” Reliability, IEEE Transactions on, vol. R-34, pp. 69 – 72, 05 1985.
F. J. Samaniego, System Signatures. John Wiley & Sons, Ltd, 2008. [Online]. Available: https://onlinelibrary.wiley.com/doi/abs/10.1002/9780470061572.eqr077
Z. I. Botev, P. L’Ecuyer, and B. Tuffin, “Static network reliability estimation under the marshall–olkin dependence model,” ethodology and Computing in Applied Probability, vol. 17, no. 2, pp. 421–447, 2015.
A. Moshnikova, “Evaluation of network reliability and element importance metrics,” in CEUR Workshop Proceedings, vol. 2702, 2020, pp. 122–131.
J. Jenczyk, “Regular dodecahedron-based network structures,” Symmetry, vol. 16, no. 2, p. 300, 2024.
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Héctor Cancela, Leslie Murray, Gerardo Rubino
This work is licensed under a Creative Commons Attribution 4.0 International License.
CLEIej is supported by its home institution, CLEI, and by the contribution of the Latin American and international researchers community, and it does not apply any author charges whatsoever for submitting and publishing. Since its creation in 1998, all contents are made publicly accesibly. The current license being applied is a (CC)-BY license (effective October 2015; between 2011 and 2015 a (CC)-BY-NC license was used).
