{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T15:45:59Z","timestamp":1773330359096,"version":"3.50.1"},"reference-count":27,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2024,3,4]],"date-time":"2024-03-04T00:00:00Z","timestamp":1709510400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["RGPIN 2018\u201005227"],"award-info":[{"award-number":["RGPIN 2018\u201005227"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["RGPIN 05191\u20102019"],"award-info":[{"award-number":["RGPIN 05191\u20102019"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Networks"],"published-print":{"date-parts":[[2024,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We introduce two new methods for approximating the all\u2010terminal reliability of undirected graphs. First, we introduce an edge removal process: remove edges at random, one at a time, until the graph becomes disconnected. We show that the expected number of edges thus removed is equal to , where  is the number of edges in the graph, and  is the average of the all\u2010terminal reliability polynomial. Based on this process, we propose a Monte\u2010Carlo algorithm to quickly estimate the graph reliability (whose exact computation is NP\u2010hard). Moreover, we show that the distribution of the edge removal process can be used to quickly approximate the reliability polynomial. We then propose increasingly accurate asymptotics for graph reliability based solely on degree distributions of the graph. These asymptotics are tested against several real\u2010world networks and are shown to be accurate for sufficiently dense graphs. While the approach starts to fail for \u201csubway\u2010like\u201d networks that contain many paths of vertices of degree two, different asymptotics are derived for such networks.<\/jats:p>","DOI":"10.1002\/net.22215","type":"journal-article","created":{"date-parts":[[2024,3,4]],"date-time":"2024-03-04T09:32:04Z","timestamp":1709544724000},"page":"51-63","update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["New approximations for network reliability"],"prefix":"10.1002","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4721-8985","authenticated-orcid":false,"given":"Jason I.","family":"Brown","sequence":"first","affiliation":[{"name":"Department of Mathematics and Statistics Dalhousie University  Halifax Nova Scotia Canada"}]},{"given":"Theodore","family":"Kolokolnikov","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Statistics Dalhousie University  Halifax Nova Scotia Canada"}]},{"given":"Robert E.","family":"Kooij","sequence":"additional","affiliation":[{"name":"Faculty of Electrical Engineering Mathematics and Computer Science, Delft University of Technology  Delft The Netherlands"},{"name":"UNIT ICT Strategy &amp; Policy, TNO (Netherlands Organization for Applied Scientific Research)  The Hague The Netherlands"}]}],"member":"311","published-online":{"date-parts":[[2024,3,4]]},"reference":[{"key":"e_1_2_9_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2022.02.002"},{"key":"e_1_2_9_3_1","doi-asserted-by":"publisher","DOI":"10.1201\/9780429161612-15"},{"key":"e_1_2_9_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.21977"},{"key":"e_1_2_9_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2014.05.048"},{"issue":"1","key":"e_1_2_9_6_1","first-page":"61","article-title":"The influence of scenario metrics on network reliability of mobile ad hoc network","volume":"9","author":"Chaturvedi S.","year":"2013","journal-title":"Int J Perform Eng"},{"key":"e_1_2_9_7_1","volume-title":"International series of monographs on computer science","author":"Colbourn C. J.","year":"1987"},{"key":"e_1_2_9_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2010.04.008"},{"key":"e_1_2_9_9_1","doi-asserted-by":"publisher","DOI":"10.5486\/PMD.1959.6.3-4.12"},{"key":"e_1_2_9_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2012.03.001"},{"key":"e_1_2_9_11_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.94.052409"},{"key":"e_1_2_9_12_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548317000177"},{"key":"e_1_2_9_13_1","doi-asserted-by":"publisher","DOI":"10.21136\/CMJ.1973.101168"},{"key":"e_1_2_9_14_1","doi-asserted-by":"crossref","unstructured":"A.GhoshandS.Boyd.Growing well\u2010connected graphs. Paper presented at: 2006 45th IEEE conference on decision and control pages 6605\u20136611.2006.","DOI":"10.1109\/CDC.2006.377282"},{"key":"e_1_2_9_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-5347-1"},{"key":"e_1_2_9_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2011.111002"},{"key":"e_1_2_9_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2014.12.023"},{"key":"e_1_2_9_18_1","volume-title":"Bernstein polynomials","author":"Lorentz G. G.","year":"1953"},{"key":"e_1_2_9_19_1","unstructured":"T.Luczak.Sparse random graphs with a given degree sequence. Proceedings of the symposium on random graphs Poznan pages 165\u2013182.1989."},{"key":"e_1_2_9_20_1","first-page":"225","volume-title":"Nauty user's guide (version 2.4)","author":"McKay B. D.","year":"2007"},{"key":"e_1_2_9_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10522-017-9684-x"},{"key":"e_1_2_9_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060204"},{"key":"e_1_2_9_23_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230200303"},{"key":"e_1_2_9_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCNS.2015.2503561"},{"key":"e_1_2_9_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2004.834113"},{"key":"e_1_2_9_26_1","doi-asserted-by":"crossref","unstructured":"R. A.RossiandN. K.Ahmed.The network data repository with interactive graph analytics and visualization. Proceedings of the twenty\u2010ninth AAAI conference on artificial intelligence AAAI'15 pages 4292\u20134293. AAAI Press.2015.","DOI":"10.1609\/aaai.v29i1.9277"},{"key":"e_1_2_9_27_1","first-page":"629","volume-title":"Mathematical proceedings of the Cambridge philosophical society","author":"Simon R.","year":"1957"},{"key":"e_1_2_9_28_1","unstructured":"W.Zhou M.Janic R. E.Kooij andF. A.Kuipers.On the availability of networks. Proceedings of broadband 2007 pages 1\u20136. IET.2007."}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.22215","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,1]],"date-time":"2024-06-01T18:07:17Z","timestamp":1717265237000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.22215"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,4]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["10.1002\/net.22215"],"URL":"https:\/\/doi.org\/10.1002\/net.22215","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,4]]},"assertion":[{"value":"2023-05-21","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-02-09","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}