Modeling multiple-pipe failures in stormwater networks using graph theory

Urban stormwater networks (USNs) are vital infrastructures that significantly contribute to the urban water ecosystem by mitigating pluvial flooding. They play an important role in enhancing the overall well-being of society by efficiently draining stormwater from urban areas (Fu et al. 2011). Examining urban water infrastructure comprehensively, involving aspects such as planning, management, operation, rehabilitation, and modeling, is inherently challenging due to the intricate nature, vast scale, and interconnected components of these systems (Hajibabaei et al. 2019). The difficulties are further intensified by the unprecedented impacts of climate change and the continual growth of urban areas (Casal-Campos et al. 2018; Sitzenfrei et al. 2022). Therefore, it becomes imperative for critical urban water infrastructure to adapt in order to mitigate the effects of extraordinary loading conditions, particularly during instances of extremely high rainfall that may result in pluvial flooding (Hesarkazzazi et al. 2022). Consequently, a fundamental shift from the traditional approach of focusing solely on reliability to a more holistic consideration of resilience becomes crucial across all stages, including planning, modeling, operation, and rehabilitation (Sweetapple et al. 2022). The resilience of USNs is characterized by their capacity to reduce damage and swiftly recover from severe loading conditions by effectively mitigating the consequences of failures (Mugume & Butler 2017). Therefore, resilience enhancing strategies should be devised for USNs to address both typical and extreme loading conditions.

Concerning the risks facing USNs, two primary types of failures emerge: (1) functional failure, stemming from changes in loads and extreme stress on the system and (2) structural failure, induced by the disruption of one or multiple elements or within the network (Mugume et al. 2015). The primary driver for functional failure in USNs are extreme precipitation events, or the urbanization that increases the load on the system (Butler et al. 2017). Typically, structural failure in USNs arises from component failures, such as sewer blockages, pump malfunctions, and sensor failures (Sweetapple et al. 2022). Enhancing the overall resilience of USNs necessitates a comprehensive examination of the entire network to identify critical components which will help in mitigating the impacts of both types of failures. Meijer et al. (2018) indicated that the criticality analysis can serve as a foundation for risk-based asset management. Given the difficulty of predicting all potential threats for preventive measures, an efficient and effective approach to bolster resilience involves recognizing the most critical elements. By doing so, management and maintenance strategies can be improved, leading to an overall resilience enhancement.

Various researchers have endeavored to pinpoint critical elements within stormwater networks, employing diverse methodologies. Arthur & Crow (2007) formulated a methodology centered on assessing serviceability loss post-failure to identify critical elements. Möderl et al. (2009) introduced the software tool VulNetUD, which integrates the identification of susceptible sites within drainage networks using the GIS-based approach. Another approach to finding critical elements in a network is called the Achilles approach (Möderl & Rauch 2011; Mair et al. 2012), which relies on a systematic hydrodynamic modeling approach. In this method, the capacity of each pipe is successively reduced to near zero to simulate structural failures, and the pipes are ranked based on resulting hydraulic consequences, such as overall flooding. However, the focus of these studies predominantly revolves around structural failure induced by the failure of individual pipes. There are almost no methodologies designed to model scenarios involving multiple-pipe failures, which are more common in natural disasters like earthquakes, floods, and heavy storms. Identifying failure combinations is essential for improving the resilience of urban water infrastructure (Berardi et al. 2014). Multiple-pipe failure modeling for the identification of critical components has not been fully developed due to limitations in conventional modeling methods for USNs. These methods prove to be computationally expensive and time-consuming for such tasks.

Recent research focuses on alternate methods for USN modeling that can solve the problem of extensive computational time. One of these modeling strategies that has been discussed in recent literature is graph theory. Complex real-world problems can be represented in a simplified manner using network graphs; this approach is a branch of mathematics called Graph theory (Turan et al. 2019). Meijer et al. (2018) have suggested a methodology based on graph theory for finding critical elements of USNs. Another methodology is devised by Dastgir et al. (2022), wherein a customized graph-based metric is used to estimate the flooding impact when a particular pipe fails. However, the current focus of critical element assessment in USNs using graph theory predominantly centers around single-pipe failure analysis. The exploration of multiple-pipe failure modeling for identifying combinations of critical components has not been addressed yet. The key contributions of the study based on the research gaps identified in the above discussion are as follows:

• Proposing a graph-based methodology for modeling multiple-pipe failure combinations which is not iterative like the hydrodynamic modeling method (HMM) but rather mimics the functional behavior of USNs by employing the concept of complex network analysis.

• Incorporating a methodology for modeling hydraulic structures, like storage tanks, as part of the graph-based approach.

• Developing a hybrid methodology combining the computational time-saving properties of the GTM and the accuracy of the HMM.

• Test and validate the methodology on two real case studies with different spatial properties regarding accuracy and computational efforts.

The mathematical representation and analysis of the topological characteristics of USNs can be accomplished using a graph, denoted as G = (V, E), where V represents vertices or nodes and E represents edges. The edges in the graph are represented by ordered pairs of vertices (i, j), where i is the source node and j is the target node. In USNs, nodes can represent features such as manholes and storage tanks, while edges symbolize elements like pipes, pumps, and weirs. For this study, the distance between node pairs (pipe lengths) is employed as the edge weighting function whereas pumps are considered without weight as they do not have any lengths.

The study also suggests a novel approach for modeling hydraulic structures (e.g. pumps, storage tanks) using a graph-based methodology. This is essential for enhancing the accuracy and applicability of graph theory method (GTM) in real-world case studies as pumps and storage tanks are often integral components of the network.

Pumps in USNs are modeled as links in the graph. Each pump link in the network is assigned a value called pump capacity represented by ⁠. The representation of pump capacity in this manner is chosen because it has the same units as values of the pipes. The value of each pump is calculated based on the storage volume of the wet well of the pump and the startup and shutoff depth of the pump. This value is representative of the volume that is not being pumped to the section of the network located downstream of the pump. Hence, this volume will also not be part of the flooding volume when the downstream pipes fail. To account for this, value of the pump is subtracted from value of each downstream pipe.

Storage tanks are modeled as nodes of the graph in a stormwater network. Storage capacity is calculated using the storage curve of each tank in a network represented as ⁠. This value signifies the volume of water being stored in storage tanks and just like pumps, this value is subtracted from values of all pipes downstream of the storage tank. By doing so, the modeling approach aims to provide a more accurate depiction of the flooding impact, accounting for the fact that water stored in the tank does not contribute to downstream flooding when a pipe is blocked.

Complex network analysis and graph measures mentioned above can be used to calculate flooding volume when a particular pipe fails. values for each pipe are first calculated and these values are multiplied by the rainfall volume of the sub-catchment to determine the potential flooding volume if this pipe fails (for more information, refer to Dastgir et al. (2022)). As an extension, in this study, losses from infiltration and evaporation are also considered. These losses are included in the hydrodynamic modeling method (HMM) in the form of, e.g. depression storage on a pervious and impervious portion of the sub-catchment, which is the property of a sub-catchment. To account for these losses and to make GTM more viable and accurate, these losses are subtracted from values. The methodology for flooding volume calculation described by Dastgir et al. (2022) is valid for single-pipe failure only, which is extended to multiple-pipe failure scenarios in this work.

To exemplify, we can assume the initial failure is of pipe 21, marked in red in Figure 1. First, the shortest path graph measure is applied to identify pipes in the path from pipe 21 to the outlet, depicted with green arrows in Figure 1. This step is important because if the second pipe that fails is within this shortest path, a mere summation of flooding volumes (⁠⁠) would not accurately represent the real impact on the USN. The reason is that the flood volume from the upstream section has already exited the system at the time of pipe 21 failure. For instance, if pipe 12 is presumed to be the second pipe to fail, the flood volume associated with pipe 21 is included twice in the calculation. It contributes once as part of the for pipe 21 and again during the computation of for pipe 12 (⁠ calculation includes the whole upstream network for flooding volume calculation). Conversely, if the second failing pipe is outside the shortest path, as exemplified by pipe 4 in dark blue in Figure 1(a), the direct addition of flooding volumes (⁠⁠) for both pipes accurately reflects the flooding impact on the system. This methodology is applied to compute the flooding impact for all two-pipe failure combinations. The combination with the highest flooding volume is considered as the most critical combination. Different scenarios for two-pipe failure cases are:

• Pipe 21→ Pipe 12 = + –

• Pipe 21 → Pipe 4 = +

Similar to two-pipe failure cases, all possible three-pipe failure combinations can be studied (Figure 1(b)). Here, for the pipe failing third, the analysis checks if it is in the shortest path of the second pipe or not. For instance, if pipe 3 is the third to fail, the of pipe 5 needs to be subtracted from the total flooding impact. Conversely, if pipe 16 is the third pipe to fail and is not in the shortest path of the second pipe, a simple addition of values will yield the correct flooding impact. This process ensures an accurate representation of the flooding impact for all possible three-pipe failure combinations.

Different scenarios for three-pipe failures from Figure 1(b) are:

• Pipe 21 → pipe 12 → pipe 16 = + – + –

• Pipe 21 → pipe 5 → pipe 3 = + + –

• Pipe 21 → pipe 5 → pipe 16 = + +

The first consideration in this scenario is if the pipe failing first is part of a loop or not. If it is part of a loop then of the alternate path is subtracted from the of the failed pipe because the volume of water equivalent to of the alternate path can be redirected and does not contribute to flooding volume. Then, the pipe failing second is checked if it is in the shortest path of the first pipe and finally pipe failing second is also checked if it is part of a loop, and how much volume will be redirected is then calculated based on of its alternate path.

Imagine the same example network but this time with some additional loops as shown in Figure 2. In this case, if pipe 4 is the pipe failing second as shown in blue in Figure 2, it is part of a loop. So, if pipe 21 fails first and then pipe 4 fails, part or all of the volume from pipe 4 can be redirected to the alternate path shown with purple arrows in Figure 2. The volume redirected depends on the minimum capacity reserve of pipes in the alternate path (⁠⁠). Hence, in this case, the determined flooding impact from the combination of pipe 21 and pipe 4 can be given by:

• Pipe 21 → Pipe 4 = + –

A hybrid graph-hydrodynamic method (GHM) is also developed as part of this study, combining the advantages of the HMM and GTM. The HMM cannot be used for multiple-pipe failure combinations because of computational burdens; conversely, GTM can be used to identify critical combinations in a timely manner but the flooding volume is not as accurate. This study aims to combine only the beneficial part of both methods to develop a hybrid approach which can identify critical combinations in a reasonable time while still holding the accuracy of the HMM. The GHM described in this study combines these advantages for determining critical multiple-pipe failure combinations. Critical combinations equivalent to 20% of the total number of pipes are recognized using the GTM and then the HMM is used to calculate exact flooding volumes for these critical combinations.

Two statistical measures, namely Pearson correlation coefficient (r) (Pearson 1895) and normalized root mean square error (NRMSE), are used to compare the accuracy of results from GTM and HMM in this study. Pearson coefficient is used to determine the strength and direction of linear relationship of the data. A value closer to 1 shows a higher correlation of the data while close to zero shows a lower correlation. NRMSE allows a term-by-term comparison of actual deviation between the predicted and measured values. Smaller values of NRMSE show better model performance (Jiang 2009). Flooding volume calculated using GTM is taken as the predicted value and flooding volume calculated through the HMM is considered the measured value in this study.

The second case study is part of an entirely flat stormwater network of the city of Ahvaz in Iran as shown in Figure 3(b). It is also a fully branched network with 529 links. Hesarkazzazi et al. (2022) have created a number of different looped networks for this branched case study by systematically removing nodes while keeping the same number of links. 5 of these looped networks with varying loop degrees, i.e. 2, 5, 10, 20 and 30% (fully looped) are utilized in this study.

The total number of combinations studied for different case studies is given in Table 1. The number of combinations is given for two- and three-pipe failure scenarios.

Two real-world case studies are analyzed by comparing GTM and HMM in terms of accuracy and computational time. Because the HMM is computationally too expensive, comparison between all pipe combinations is only discussed for branched Alpine and Ahvaz networks for two-pipe failure scenarios. For three-pipe failure scenarios and looped networks, partial comparison is performed. 20% of the total pipes are used as a value for comparison of pipe combinations in that case. The reason is that the HMM cannot be used to run all possible three-pipe failure scenarios. As an estimate just for the Ahvaz case study, the HMM will require around 14 years to run all possible three-pipe failure scenarios. Hence, two-pipe failure scenarios are used for full comparison to establish that the methodology works for full comparison and then partial comparison is performed for three-pipe failure scenarios.

For three-pipe failures, all possible combinations are first run using GTM. Afterwards, the top 90 and top 100 combinations are selected and run using the HMM for Alpine and Ahvaz, respectively. For both case studies, more than 85% of these combinations have the same rankings from both GTM and HMM which shows that GTM although overestimating flood volumes, can still be used to identify the most critical combinations. The comparison of flooding volume from the GTM and HMM is given in Figure 4(c) for the Alpine network and in Figure 4(d) for the Ahvaz network.

From Figures 4(c) and 4(d), it can be observed that the correlation between the GTM and HMM flooding volumes has decreased compared to the two-pipe failure scenarios, resulting in a slightly lower performance for higher order pipe failure combinations. As the order of failure combination increases, the complexity of the system for calculating flood volume generation also increases. This complexity cannot be fully captured in GTM which does not solve complex hydraulic equations. Another observation that can be made is that the Alpine case in general has a higher correlation than the Ahvaz case, which could be attributed to the fact that the Ahvaz network has a more complex topology compared to the Alpine network. However, GTM still performs its function of finding critical combinations in the Ahvaz network too. Additionally, it can be noticed that as the flooding volume gets higher, the difference between the GTM and HMM also increases. This is because GTM does not cater for complex hydraulic behaviors like backwater effects and dampening of the wave. Solving these complex problems using simple graph-based approaches is not feasible with the proposed approach.

Five networks with varying loop degrees are analyzed for the Ahvaz network with a 30% loop degree considered as fully looped. All five networks are analyzed for both two- and three-pipe failure cases. The results are shown in Figure 5(b) for two-pipe failure scenarios and in Figure 5(c) for three-pipe failure scenarios. It can be observed for both cases that the accuracy of GTM decreases with increasing loop degree. For both two- and three-pipe failure cases purple and orange markers representing 30 and 20% loop degrees, respectively, are farthest from the diagonal line. This shows that the correlation between the GTM and HMM is decreasing with increasing loop degrees. For two-pipe failure cases, statistical measures decrease with increasing loop degree from ‘r’ = 0.79 and NRMSE = 0.140 for 2% loop degree to ‘r’ = 0.67 and NRMSE = 0.198 for 30% loop degree as shown in Table 2. Similar to the Alpine network, the accuracy of the method is even lower for three-pipe failure scenarios where ‘r’ and NRMSE values decrease from 0.76 and 0.161 to 0.65 and 0.228 for networks with 2% loop degree and 30% loop degree, respectively.

The main reason for the decrease in the correlation between the GTM and HMM with increasing loop degree is the difference in rerouting of flood volume. The HMM uses complex hydraulic equations, which can capture intricate details associated with rerouting for looped network. On the other hand, GTM uses a simplified method of which only considers adjacent pipes for rerouting while in reality, this effect goes further downstream as well. Because of this simplification, the accuracy of GTM decreases slightly with increasing loop degree.

The impact of modeling spatial structures is also shown in Table 2 for Alpine-branched and Alpine-looped network for both failure levels. It can be seen that the Pearson coefficient and NRMSE values become significantly worse when spatial structures are not modeled in the methodology, e.g. for Alpine-branched network two-pipe failure case, r and NRMSE decreases from 0.84 and 0.114 to 0.67 and 0.211, respectively. This shows the importance of including spatial structures in USN modeling strategies. GTM performance will significantly worsen when the spatial structures are not modeled. Therefore, modeling spatial structures with GTM is one of the important contributions of this study.

GTM was implemented using a Python module, NetworkX version 2.6.2 (Hagberg et al. 2008). The HMM was also implemented using a Python module called Pyswmm which employs SWMM version 5.1 (Rossman 2010). Both of these methods are implemented using a laptop having an Intel^® Core™ i7-10610U CPU @ 2.3 GHz processor and 8-GB RAM.

Table 4 shows the comparison between the computational time of the GTM and HMM for the two scenarios where all possible combinations are run using both methods. It can be seen that the HMM took 172 h while the GTM only took 1.48 h to run all possible two-pipe failure combinations for a branched Alpine network (note that the GTM code is a prototype and not optimized in terms of computational efficiency). That shows a computational time gain factor of 115 between the GTM and HMM, meaning that the GTM in this case is 115 times faster than the HMM. The GHM on the other hand took around 1.68 h to run. For Ahvaz's case, the HMM took 243 h to run all failure combinations while GTM only took 1.61 h. Hence, for the Ahvaz case study, GTM has a computational time gain factor of 150 showing that the computational efficiency of GTM increases as the number of combinations increases. The GHM in this case took around 1.83 h.

Therefore, the GTM is much faster compared to the HMM while the GHM is the best-case scenario, i.e. it is much faster than the HMM and still gives the accuracy of the HMM when the few most critical combinations are to be identified.

In this study, a new GTM is presented to identify critical multiple-pipe failure combinations in USNs. The methodology is compared with the HMM for accuracy and computational time requirements. Additionally, a hybrid GHM is also discussed which combines the advantages of the two methodologies. Due to the consideration of two real-life case studies with different spatial properties and different network characteristics, GTM explained in this study can be applied to most real-life case studies; however, transferability to some special case studies with different boundary conditions needs more investigation. The key findings of the study are mentioned below:

• Complex network analysis can be used for multiple-pipe failure modeling to identify critical pipe failure combinations in USNs. GTM discussed in this regard does not rely on complex hydraulic equations, but rather uses the concept of network topology and estimates flooding volumes based on graph measures.

• Results indicate that GTM, although overestimating flooding volumes compared to the HMM, can still be used for identifying the most critical combinations correctly. Therefore, GTM can be used for pre-screening of critical combinations very efficiently.

• GTM results are more accurate for two-pipe failure scenarios compared to three-pipe failure scenarios. The reason is that with a higher failure level complexity of calculating flooding volume increases which cannot yet be fully captured by GTM.

• Results indicate that GTM performance decreases with increasing loop degree (redundancy) in the network which is clear from Ahvaz looped case studies. The reason is that the rerouting of water is simplified in GTM when in reality it is a complex phenomenon.

• Results also show that GTM performance improves significantly when spatial structures are modeled as part of the methodology.

• Although GTM is less accurate compared to the HMM, the real advantage of the approach lies in the fact that it is extremely efficient in terms of computational time. It is faster than the HMM by a factor of 115 for the Alpine case and 150 for the Ahvaz case. This small computational time allows for analyzing all possible failure combinations for multiple-pipe failure modeling.

• A hybrid GHM is developed to combine the advantages of both methodologies. It uses GTM to identify the most critical combinations by analyzing all possible combinations and then uses the HMM for accurate calculation of the flooding impact of these critical combinations. Extensive validation of GHM will be part of the future work in this regard where it will be tested for different use cases and for more case studies.

This research was funded in part by the Austrian Science Fund (FWF) P 36737-N. For the purpose of open access, the authors have applied a CC BY public copyright licence to any Author Accepted Manuscript version arising from this submission.

All relevant data are included in the paper or its Supplementary Information.

The authors declare there is no conflict.