{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,22]],"date-time":"2025-12-22T10:50:16Z","timestamp":1766400616385,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,10,30]],"date-time":"2021-10-30T00:00:00Z","timestamp":1635552000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,10,30]],"date-time":"2021-10-30T00:00:00Z","timestamp":1635552000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Appl Netw Sci"],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The issue of vulnerability and robustness in networks have been addressed by several methods. The goal is to identify which are the critical components (i.e., nodes\/edges) whose failure impairs the functioning of the network and how much this impacts the ensuing increase in vulnerability. In this paper we consider the drop in the network robustness as measured by the increase in vulnerability of the perturbed network and compare it with the original one. Traditional robustness metrics are based on centrality measures, the loss of efficiency and spectral analysis. The approach proposed in this paper sees the graph as a set of probability distributions and computes, specifically the probability distribution of its node to node distances and computes an index of vulnerability through the distance between the node-to-node distributions associated to original network and the one obtained by the removal of nodes and edges. Two such distances are proposed for this analysis: Jensen\u2013Shannon and Wasserstein, based respectively on information theory and optimal transport theory, which are shown to offer a different characterization of vulnerability. Extensive computational results, including two real-world water distribution networks, are reported comparing the new approach to the traditional metrics. This modelling and algorithmic framework can also support the analysis of other networked infrastructures among which power grids, gas distribution and transit networks.<\/jats:p>","DOI":"10.1007\/s41109-021-00427-x","type":"journal-article","created":{"date-parts":[[2021,10,30]],"date-time":"2021-10-30T18:02:38Z","timestamp":1635616958000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Probabilistic measures of edge criticality in graphs: a study in water distribution networks"],"prefix":"10.1007","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4187-4209","authenticated-orcid":false,"given":"Andrea","family":"Ponti","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antonio","family":"Candelieri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ilaria","family":"Giordani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Francesco","family":"Archetti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,10,30]]},"reference":[{"key":"427_CR1","doi-asserted-by":"publisher","first-page":"1261","DOI":"10.30638\/eemj.2015.136","volume":"14","author":"F Archetti","year":"2015","unstructured":"Archetti F, Candelieri A, Soldi D (2015) Network analysis for resilience evaluation in water distribution networks. Environ Eng Manag J 14:1261\u20131270","journal-title":"Environ Eng Manag J"},{"key":"427_CR2","unstructured":"Arjovsky M, Chintala S, Bottou L (2017) Wasserstein GAN. arXiv:1701.07875 [cs, stat]"},{"key":"427_CR3","doi-asserted-by":"publisher","first-page":"71-1","DOI":"10.1145\/2897824.2925918","volume":"35","author":"N Bonneel","year":"2016","unstructured":"Bonneel N, Peyr\u00e9 G, Cuturi M (2016) Wasserstein barycentric coordinates: histogram regression using optimal transport. ACM Trans Graph 35:71-1","journal-title":"ACM Trans Graph"},{"key":"427_CR4","doi-asserted-by":"crossref","unstructured":"Candelieri A, Giordani I, Archetti F (2017) Supporting resilience management of water distribution networks through network analysis and hydraulic simulation. In: 2017 21st international conference on control systems and computer science (CSCS). IEEE, pp 599\u2013605","DOI":"10.1109\/CSCS.2017.91"},{"key":"427_CR5","volume-title":"Elements of information theory (Wiley series in telecommunications and signal processing)","author":"TM Cover","year":"2006","unstructured":"Cover TM, Thomas JA (2006) Elements of information theory (Wiley series in telecommunications and signal processing). Wiley, New York"},{"key":"427_CR6","doi-asserted-by":"crossref","unstructured":"Deza MM, Deza E (2009) Encyclopedia of distances. In: Encyclopedia of distances. Springer, Berlin, pp 1\u2013583","DOI":"10.1007\/978-3-642-00234-2_1"},{"key":"427_CR7","doi-asserted-by":"publisher","first-page":"45","DOI":"10.3390\/w10010045","volume":"10","author":"A Di Nardo","year":"2018","unstructured":"Di Nardo A, Giudicianni C, Greco R,  Herrera M, Santonastaso GF (2018) Applications of graph spectral techniques to water distribution network management. Water 10:45","journal-title":"Water"},{"key":"427_CR8","doi-asserted-by":"publisher","first-page":"1521","DOI":"10.3390\/w12061521","volume":"12","author":"K Diao","year":"2020","unstructured":"Diao K (2020) Multiscale resilience in water distribution and drainage systems. Water 12:1521","journal-title":"Water"},{"key":"427_CR9","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/j.watres.2016.10.011","volume":"106","author":"K Diao","year":"2016","unstructured":"Diao K, Sweetapple C, Farmani R, Fu G, Ward S, Butler D (2016) Global resilience analysis of water distribution systems. Water research 106:383\u2013393","journal-title":"Water research"},{"key":"427_CR10","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1061\/(ASCE)0733-9496(2005)131:3(161)","volume":"131","author":"R Farmani","year":"2005","unstructured":"Farmani R, Walters GA, Savic DA (2005) Trade-off between total cost and reliability for Anytown water distribution network. J Water Resour Plan Manag 131:161\u2013171","journal-title":"J Water Resour Plan Manag"},{"key":"427_CR11","doi-asserted-by":"publisher","first-page":"298","DOI":"10.21136\/CMJ.1973.101168","volume":"23","author":"M Fiedler","year":"1973","unstructured":"Fiedler M (1973) Algebraic connectivity of graphs. Czechoslovak Math J 23:298\u2013305","journal-title":"Czechoslovak Math J"},{"key":"427_CR12","unstructured":"Frogner C, Zhang C, Mobahi H, Araya-Polo M, Poggio T (2015) Learning with a Wasserstein loss. arXiv:1506.05439"},{"key":"427_CR13","doi-asserted-by":"publisher","first-page":"1685","DOI":"10.1007\/s11269-016-1245-6","volume":"30","author":"M Herrera","year":"2016","unstructured":"Herrera M, Abraham E, Stoianov I (2016) A graph-theoretic framework for assessing the resilience of sectorised water distribution networks. Water Resour Manag 30:1685\u20131699","journal-title":"Water Resour Manag"},{"key":"427_CR14","doi-asserted-by":"publisher","first-page":"1241","DOI":"10.1016\/j.proeng.2015.08.985","volume":"119","author":"M Herrera","year":"2015","unstructured":"Herrera M, Abraham E, Stoianov I (2015) Graph-theoretic surrogate measures for analysing the resilience of water distribution networks. Procedia Eng 119:1241\u20131248","journal-title":"Procedia Eng"},{"key":"427_CR15","unstructured":"Kantorovich L (1942) On the transfer of masses. In: Doklady Akademii Nauk, pp 227\u2013229. (in Russian)"},{"key":"427_CR17","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/9\/6\/188","author":"V Latora","year":"2007","unstructured":"Latora V, Marchiori M (2007) A measure of centrality based on network efficiency. New J Phys. https:\/\/doi.org\/10.1088\/1367-2630\/9\/6\/188","journal-title":"New J Phys"},{"key":"427_CR18","doi-asserted-by":"publisher","first-page":"1005","DOI":"10.3390\/w10081005","volume":"10","author":"M Maiolo","year":"2018","unstructured":"Maiolo M, Pantusa D, Carini M, Capano G, Chiaravalloti F, Procopio A (2018) A new vulnerability measure for water distribution network. Water 10:1005","journal-title":"Water"},{"key":"427_CR34","unstructured":"Monge G (1781) M\u00e9moire sur la th\u00e9orie des d\u00e9blais et des remblais.\u00a0In: Histoire de l'Acad\u00e9mie Royale des Sciences de Paris"},{"key":"427_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1471-2105-12-436","volume":"12","author":"JH Morris","year":"2011","unstructured":"Morris JH, Apeltsin L, Newman AM, Baumbach J, Wittkop T, Su G, Bader GD, Ferrin TE (2011) clusterMaker: a multi-algorithm clustering plugin for Cytoscape. BMC Bioinform 12:1\u201314","journal-title":"BMC Bioinform"},{"key":"427_CR20","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001","volume-title":"Networks: an introduction, networks","author":"M Newman","year":"2010","unstructured":"Newman M (2010) Networks: an introduction, networks. Oxford University Press, Oxford"},{"key":"427_CR21","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1561\/2200000073","volume":"11","author":"G Peyr\u00e9","year":"2019","unstructured":"Peyr\u00e9 G, Cuturi M (2019) Computational optimal transport: with applications to data science. Found Trends Mach Learn 11:355\u2013607","journal-title":"Found Trends Mach Learn"},{"key":"427_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/ncomms13928","volume":"8","author":"TA Schieber","year":"2017","unstructured":"Schieber TA, Carpi L, D\u00edaz-Guilera A, Pardalos PM, Masoller C, Ravetti MG (2017) Quantification of network structural dissimilarities. Nat Commun 8:1\u201310","journal-title":"Nat Commun"},{"key":"427_CR24","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1080\/13669877.2011.634522","volume":"15","author":"RW Scholz","year":"2012","unstructured":"Scholz RW, Blumer YB, Brand FS (2012) Risk, vulnerability, robustness, and resilience from a decision-theoretic perspective. J Risk Res 15:313\u2013330","journal-title":"J Risk Res"},{"key":"427_CR26","doi-asserted-by":"publisher","first-page":"e88445","DOI":"10.1371\/journal.pone.0088445","volume":"9","author":"Q Shuang","year":"2014","unstructured":"Shuang Q, Zhang M, Yuan Y (2014) Performance and reliability analysis of water distribution systems under cascading failures and the identification of crucial pipes. PLoS ONE 9:e88445","journal-title":"PLoS ONE"},{"key":"427_CR27","doi-asserted-by":"publisher","first-page":"1189","DOI":"10.3390\/w11061189","volume":"11","author":"Q Shuang","year":"2019","unstructured":"Shuang Q, Liu HJ, Porse E (2019) Review of the quantitative resilience methods in water distribution networks. Water 11:1189","journal-title":"Water"},{"key":"427_CR28","doi-asserted-by":"publisher","first-page":"1259","DOI":"10.1016\/j.proeng.2015.08.990","volume":"119","author":"D Soldi","year":"2015","unstructured":"Soldi D, Candelieri A, Archetti  F (2015) Resilience and vulnerability in urban water distribution networks through network theory and hydraulic simulation. Procedia Eng 119:1259\u20131268","journal-title":"Procedia Eng"},{"key":"427_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s41109-018-0079-y","volume":"3","author":"A-J Ulusoy","year":"2018","unstructured":"Ulusoy A-J, Stoianov I, Chazerain A (2018) Hydraulically informed graph theoretic measure of link criticality for the resilience analysis of water distribution networks. Appl Netw Sci 3:1\u201322","journal-title":"Appl Netw Sci"},{"key":"427_CR31","volume-title":"Optimal transport: old and new","author":"C Villani","year":"2008","unstructured":"Villani C (2008) Optimal transport: old and new. Springer, Berlin"},{"key":"427_CR32","unstructured":"Weng L (2019) From gan to wgan. arXiv:1904.08994"},{"key":"427_CR33","doi-asserted-by":"publisher","first-page":"016111","DOI":"10.1063\/1.3540339","volume":"21","author":"A Yazdani","year":"2011","unstructured":"Yazdani A, Jeffrey P (2011) Complex network analysis of water distribution systems. Chaos Interdiscip J Nonlinear Sci 21:016111","journal-title":"Chaos Interdiscip J Nonlinear Sci"}],"container-title":["Applied Network Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-021-00427-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41109-021-00427-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-021-00427-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,30]],"date-time":"2021-10-30T18:04:13Z","timestamp":1635617053000},"score":1,"resource":{"primary":{"URL":"https:\/\/appliednetsci.springeropen.com\/articles\/10.1007\/s41109-021-00427-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,30]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["427"],"URL":"https:\/\/doi.org\/10.1007\/s41109-021-00427-x","relation":{},"ISSN":["2364-8228"],"issn-type":[{"type":"electronic","value":"2364-8228"}],"subject":[],"published":{"date-parts":[[2021,10,30]]},"assertion":[{"value":"1 May 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 October 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 October 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 October 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"81"}}