Abstract
Many civil infrastructure systems that deliver resources from source points to sinks, e.g., power distribution and gas pipeline networks, can be described as acyclic directed networks comprising nodes and links. Reliability assessment of these systems can be challenging, particularly for systems of increasing size and complexity and if the probabilities of rare events are of interest. This paper proposes a new analytical probability propagation method for reliability assessment of acyclic directed networks called the directed probability propagation method (dPrPm). Through a link-adding sequence to propagate a message consisting of the marginal and pairwise node reliabilities from source nodes to sink nodes, the method results in the upper and lower bounds of all sink node reliabilities. Reliability of a sink node is measured by the probability of reaching that node from a source node. Compared with previous methods, dPrPm addresses the case of multiple-sink networks, results in guaranteed reliability bounds, and analyzes acyclic directed networks as relevant for infrastructure systems. Proofs are provided guaranteeing the accuracy of dPrPm, and computation time is significantly reduced from typical exponential increases with system size to a polynomial increase. To assess performance, the proposed method was applied to three test applications: a directed grid network, a power distribution network, and a more complex gas pipeline network under seismic hazard. Results were compared with the exact solution and Monte Carlo simulations to evaluate accuracy and computational cost. Results showed that dPrPm performs equally well in terms of accuracy across network reliabilities and achieved order-of-magnitude increases in computational efficiency to obtain exact bounds on reliability assessments at all system sink nodes.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
Support for this work by the National Science Foundation through Grant No. CNS-1541074 is acknowledged.
References
Ambraseys, N. N., and J. M. Menu. 1988. “Earthquake-induced ground displacements.” Earthquake Eng. Struct. Dyn. 16 (7): 985–1006. https://doi.org/10.1002/eqe.4290160704.
Applegate, C., and I. Tien. 2019. “Framework for probabilistic vulnerability analysis of interdependent infrastructure systems.” J. Comput. Civ. Eng. 33 (1): 04018058. https://doi.org/10.1061/(ASCE)CP.1943-5487.0000801.
Barber, D. 2012. Bayesian reasoning and machine learning. Cambridge, UK: Cambridge University Press.
Birolini, A., 2004. Reliability engineering: Theory and practice. 4th ed. Berlin: Springer.
Bulteau, S., and M. El Khadiri. 1998. “A Monte Carlo simulation of the flow network reliability using importance and stratified sampling.” Ph.D. dissertation, Dept. of RAIRO-Operations Research, INRIA.
California Energy Commission. 2018. “California energy commission: GIS open data.” Accessed June 25, 2018. https://cecgis-caenergy.opendata.arcgis.com/.
Cheng, L., Z. Lu, and L. Zhang. 2015. “Application of rejection sampling based methodology to variance based parametric sensitivity analysis.” Reliab. Eng. Syst. Saf. 142: 9–18. https://doi.org/10.1016/j.ress.2015.04.020.
Cheng, W., J. Cox, and P. Whitlock. 2017. “Random walks on graphs and Monte Carlo methods.” Math. Comput. Simul. 135: 86–94. https://doi.org/10.1016/j.matcom.2015.12.006.
Coughlan, J. 2009. A tutorial introduction to belief propagation. San Francisco: Smith-Kettlewell Eye Research Institute.
Der Kiureghian, A., and J. Song. 2008. “Multi-scale reliability analysis and updating of complex systems by use of linear programming.” Reliab. Eng. Syst. Saf. 93 (2): 288–297. https://doi.org/10.1016/j.ress.2006.10.022.
Dotson, W., and J. O. Gobien. 1979. “A new analysis technique for probabilistic graphs.” IEEE Trans. Circuits Syst. 26 (10): 855–865. https://doi.org/10.1109/TCS.1979.1084573.
Dueñas-Osorio, L. 2017. “Reliability of grid networks and recursive decomposition algorithms.” Accessed April 14, 2017. https://duenas-osorio.rice.edu/sites/g/files/bxs2181/f/docs/tutorial_grid25.html.
Ebeling, C. E. 2010. An introduction to reliability and maintainability engineering. 2nd ed. Long Grove, IL: Waveland.
Kim, Y., and W. Kang. 2013. “Network reliability analysis of complex systems using a non-simulation-based method.” Reliab. Eng. Syst. Saf. 110: 80–88. https://doi.org/10.1016/j.ress.2012.09.012.
Lanzano, G., E. Salzano, F. Santucci de Magistris, and G. Fabbrocino. 2014. “Seismic vulnerability of gas and liquid buried pipelines.” J. Loss Prev. Process Ind. 28: 72–78. https://doi.org/10.1016/j.jlp.2013.03.010.
Lim, H.-W., and J. Song. 2012. “Efficient risk assessment of lifeline networks under spatially correlated ground motions using selective recursive decomposition algorithm.” Earthquake Eng. Struct. Dyn. 41 (13): 1861–1882. https://doi.org/10.1002/eqe.2162.
Liu, W., and J. Li. 2009. “An improved recursive decomposition algorithm for reliability evaluation of lifeline networks.” Earthquake Eng. Vib. 8 (3): 409–419. https://doi.org/10.1007/s11803-009-8152-2.
Ostrom, D. 2004. “Database of seismic parameters of equipment in substations.” Accessed January 10, 2017. https://apps.peer.berkeley.edu/lifelines/lifelines_pre_2006/final_reports/413-FR.pdf.
Shields, M. D., K. Teferra, A. Hapij, and R. P. Daddazio. 2015. “Refined stratified sampling for efficient Monte Carlo based uncertainty quantification.” Reliab. Eng. Syst. Saf. 142: 310–325. https://doi.org/10.1016/j.ress.2015.05.023.
Shin, Y. Y., and J. S. Koh. 1998. “An algorithm for generating minimal cutsets of undirected graphs.” Korean J. Comput. Appl. Math. 5 (3): 681–693. https://doi.org/10.1007/BF03008891.
Suh, H., and C. K. Chang. 2000. “Algorithms for the minimal cutsets enumeration of networks by graph search and branch addition.” In Proc. 25th Annual IEEE Conf. on Local Computer Networks, 100–10. Piscataway, NJ: IEEE.
Tien, I. 2017. “Bayesian network methods for modeling and reliability assessment of infrastructure systems.” In Risk and reliability analysis: Theory and applications: Springer Series in Reliability Engineering. Berlin: Springer.
Tien, I., and A. Der Kiureghian. 2016. “Algorithms for Bayesian network modeling and reliability assessment of infrastructure systems.” Reliab. Eng. Syst. Saf. 156: 134–147. https://doi.org/10.1016/j.ress.2016.07.022.
Tien, I., and A. Der Kiureghian. 2017. “Reliability assessment of critical infrastructure using Bayesian networks.” J. Infrastruct. Syst. 23 (4): 04017025. https://doi.org/10.1061/(ASCE)IS.1943-555X.0000384.
Tong, Y., and I. Tien. 2017. “Algorithms for Bayesian network modeling, inference, and reliability assessment for multi-state flow networks.” J. Comput. Civ. Eng. 31 (5): 04017051. https://doi.org/10.1061/(ASCE)CP.1943-5487.0000699.
Tong, Y., and I. Tien. 2019. “Analytical probability propagation method for reliability analysis of general complex networks.” Reliab. Eng. Syst. Saf. 189: 21–30. https://doi.org/10.1016/j.ress.2019.04.013.
Zuev, K., S. Wu, and J. Beck. 2015. “General network reliability problem and its efficient solution by Subset Simulation.” Probab. Eng. Mech. 40: 25–35. https://doi.org/10.1016/j.probengmech.2015.02.002.
Information & Authors
Information
Published In
ASCE-ASME Journal of Risk and Uncertainty in Engineering Systems, Part A: Civil Engineering
Volume 5 • Issue 3 • September 2019
Copyright
©2019 American Society of Civil Engineers.
History
Received: Sep 21, 2018
Accepted: Jan 18, 2019
Published online: Jul 13, 2019
Published in print: Sep 1, 2019
Discussion open until: Dec 13, 2019
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.