IDEAS home Printed from https://ideas.repec.org/a/eee/reensy/v185y2019icp429-439.html
   My bibliography  Save this article

An efficient algorithm for computing exact system and survival signatures of K-terminal network reliability

Author

Listed:
  • Reed, Sean
  • Löfstrand, Magnus
  • Andrews, John

Abstract

An efficient algorithm is presented for computing exact system and survival signatures of K-terminal reliability in undirected networks with unreliable edges. K-terminal reliability is defined as the probability that a subset K of the network nodes can communicate with each other. Signatures have several advantages over direct reliability calculation such as enabling certain stochastic comparisons of reliability between competing network topology designs, extremely fast repeat computation of network reliability for different edge reliabilities and computation of network reliability when failures of edges are exchangeable but not independent. Existing methods for computation of signatures for K-terminal network reliability require derivation of cut-sets or path-sets which is only feasible for small networks due to the computational expense. The new algorithm utilises binary decision diagrams, boundary set partition sets and simple array operations to efficiently compute signatures through a factorisation of the network edges. The performance and advantages of the algorithm are demonstrated through application to a set of benchmark networks and a sensor network from an underground mine.

Suggested Citation

  • Reed, Sean & Löfstrand, Magnus & Andrews, John, 2019. "An efficient algorithm for computing exact system and survival signatures of K-terminal network reliability," Reliability Engineering and System Safety, Elsevier, vol. 185(C), pages 429-439.
  • Handle: RePEc:eee:reensy:v:185:y:2019:i:c:p:429-439
    DOI: 10.1016/j.ress.2019.01.011
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0951832018307907
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ress.2019.01.011?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Reed, Sean, 2017. "An efficient algorithm for exact computation of system and survival signatures using binary decision diagrams," Reliability Engineering and System Safety, Elsevier, vol. 165(C), pages 257-267.
    2. Zdravko I. Botev & Pierre L'Ecuyer & Gerardo Rubino & Richard Simard & Bruno Tuffin, 2013. "Static Network Reliability Estimation via Generalized Splitting," INFORMS Journal on Computing, INFORMS, vol. 25(1), pages 56-71, February.
    3. Jane, Chin-Chia & Shen, Wu-Hsien & Laih, Yih-Wenn, 2009. "Practical sequential bounds for approximating two-terminal reliability," European Journal of Operational Research, Elsevier, vol. 195(2), pages 427-441, June.
    4. Yeh, Wei-Chang, 2006. "A simple algorithm to search for all MCs in networks," European Journal of Operational Research, Elsevier, vol. 174(3), pages 1694-1705, November.
    5. Michael P. McAssey & Francisco J. Samaniego, 2014. "On Uniformly Optimal Networks: A Reversal of Fortune?," Communications in Statistics - Theory and Methods, Taylor & Francis Journals, vol. 43(10-12), pages 2452-2467, May.
    6. Patelli, Edoardo & Feng, Geng & Coolen, Frank P.A. & Coolen-Maturi, Tahani, 2017. "Simulation methods for system reliability using the survival signature," Reliability Engineering and System Safety, Elsevier, vol. 167(C), pages 327-337.
    7. Eryilmaz, Serkan & Coolen, Frank P.A. & Coolen-Maturi, Tahani, 2018. "Marginal and joint reliability importance based on survival signature," Reliability Engineering and System Safety, Elsevier, vol. 172(C), pages 118-128.
    8. Louis J. M. Aslett & Frank P. A. Coolen & Simon P. Wilson, 2015. "Bayesian Inference for Reliability of Systems and Networks Using the Survival Signature," Risk Analysis, John Wiley & Sons, vol. 35(9), pages 1640-1651, September.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Wang, Shuang & Jia, Haiying & Lu, Jing & Yang, Dong, 2023. "Crude oil transportation route choices: A connectivity reliability-based approach," Reliability Engineering and System Safety, Elsevier, vol. 235(C).
    2. Li, Shunlong & Wang, Jie & He, Shaoyang, 2023. "Connectivity probability evaluation of a large-scale highway bridge network using network decomposition," Reliability Engineering and System Safety, Elsevier, vol. 236(C).
    3. Wu, Baichao & Sun, Long, 2024. "A novel layer-by-layer recursive decomposition algorithm for calculation of network reliability," Reliability Engineering and System Safety, Elsevier, vol. 244(C).
    4. Maryam Kelkinnama & Serkan Eryilmaz, 2023. "Some reliability measures and maintenance policies for a coherent system composed of different types of components," Metrika: International Journal for Theoretical and Applied Statistics, Springer, vol. 86(1), pages 57-82, January.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Hindolo George-Williams & Geng Feng & Frank PA Coolen & Michael Beer & Edoardo Patelli, 2019. "Extending the survival signature paradigm to complex systems with non-repairable dependent failures," Journal of Risk and Reliability, , vol. 233(4), pages 505-519, August.
    2. Huang, Xianzhen & Coolen, Frank P.A. & Coolen-Maturi, Tahani, 2019. "A heuristic survival signature based approach for reliability-redundancy allocation," Reliability Engineering and System Safety, Elsevier, vol. 185(C), pages 511-517.
    3. Huang, Xianzhen & Aslett, Louis J.M. & Coolen, Frank P.A., 2019. "Reliability analysis of general phased mission systems with a new survival signature," Reliability Engineering and System Safety, Elsevier, vol. 189(C), pages 416-422.
    4. Coolen-Maturi, Tahani & Coolen, Frank P.A. & Balakrishnan, Narayanaswamy, 2021. "The joint survival signature of coherent systems with shared components," Reliability Engineering and System Safety, Elsevier, vol. 207(C).
    5. Mi, Jinhua & Beer, Michael & Li, Yan-Feng & Broggi, Matteo & Cheng, Yuhua, 2020. "Reliability and importance analysis of uncertain system with common cause failures based on survival signature," Reliability Engineering and System Safety, Elsevier, vol. 201(C).
    6. Shi, Yan & Behrensdorf, Jasper & Zhou, Jiayan & Hu, Yue & Broggi, Matteo & Beer, Michael, 2024. "Network reliability analysis through survival signature and machine learning techniques," Reliability Engineering and System Safety, Elsevier, vol. 242(C).
    7. Hashemi, M. & Asadi, M. & Zarezadeh, S., 2020. "Optimal maintenance policies for coherent systems with multi-type components," Reliability Engineering and System Safety, Elsevier, vol. 195(C).
    8. Chang, Miaoxin & Huang, Xianzhen & Coolen, Frank PA & Coolen-Maturi, Tahani, 2023. "New reliability model for complex systems based on stochastic processes and survival signature," European Journal of Operational Research, Elsevier, vol. 309(3), pages 1349-1364.
    9. Qin, Jinlei & Coolen, Frank P.A., 2022. "Survival signature for reliability evaluation of a multi-state system with multi-state components," Reliability Engineering and System Safety, Elsevier, vol. 218(PA).
    10. Di Maio, Francesco & Pettorossi, Chiara & Zio, Enrico, 2023. "Entropy-driven Monte Carlo simulation method for approximating the survival signature of complex infrastructures," Reliability Engineering and System Safety, Elsevier, vol. 231(C).
    11. Eryilmaz, Serkan & Coolen, Frank P.A. & Coolen-Maturi, Tahani, 2018. "Marginal and joint reliability importance based on survival signature," Reliability Engineering and System Safety, Elsevier, vol. 172(C), pages 118-128.
    12. Serkan Eryilmaz & Frank P.A. Coolen & Tahani Coolen‐Maturi, 2018. "Mean residual life of coherent systems consisting of multiple types of dependent components," Naval Research Logistics (NRL), John Wiley & Sons, vol. 65(1), pages 86-97, February.
    13. Tavangar, Mahdi & Hashemi, Marzieh, 2022. "Reliability and maintenance analysis of coherent systems subject to aging and environmental shocks," Reliability Engineering and System Safety, Elsevier, vol. 218(PB).
    14. Behrensdorf, Jasper & Regenhardt, Tobias-Emanuel & Broggi, Matteo & Beer, Michael, 2021. "Numerically efficient computation of the survival signature for the reliability analysis of large networks," Reliability Engineering and System Safety, Elsevier, vol. 216(C).
    15. Salomon, Julian & Winnewisser, Niklas & Wei, Pengfei & Broggi, Matteo & Beer, Michael, 2021. "Efficient reliability analysis of complex systems in consideration of imprecision," Reliability Engineering and System Safety, Elsevier, vol. 216(C).
    16. Jane, Chin-Chia & Laih, Yih-Wenn, 2010. "A dynamic bounding algorithm for approximating multi-state two-terminal reliability," European Journal of Operational Research, Elsevier, vol. 205(3), pages 625-637, September.
    17. Yi, He & Cui, Lirong & Balakrishnan, Narayanaswamy, 2021. "Computation of survival signatures for multi-state consecutive-k systems," Reliability Engineering and System Safety, Elsevier, vol. 208(C).
    18. Yang, Lechang & Wang, Pidong & Wang, Qiang & Bi, Sifeng & Peng, Rui & Behrensdorf, Jasper & Beer, Michael, 2021. "Reliability analysis of a complex system with hybrid structures and multi-level dependent life metrics," Reliability Engineering and System Safety, Elsevier, vol. 209(C).
    19. Huang, Xianzhen & Jin, Sujun & He, Xuefeng & He, David, 2019. "Reliability analysis of coherent systems subject to internal failures and external shocks," Reliability Engineering and System Safety, Elsevier, vol. 181(C), pages 75-83.
    20. Sebastio, Stefano & Trivedi, Kishor S. & Wang, Dazhi & Yin, Xiaoyan, 2014. "Fast computation of bounds for two-terminal network reliability," European Journal of Operational Research, Elsevier, vol. 238(3), pages 810-823.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:reensy:v:185:y:2019:i:c:p:429-439. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: https://www.journals.elsevier.com/reliability-engineering-and-system-safety .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.