Graph method for critical pipe analysis of branched and looped drainage networks

Urban stormwater networks (USNs) are considered to be an important infrastructure for life in urban areas. These systems convey stormwater away from urban areas and contribute to the general well-being of the population (Fu et al. 2011). Following, a structural (e.g., blockage induced) and functional (e.g., precipitation induced) failure are two commonly adopted failure modes in USNs, which can greatly affect the performance of such systems (Butler et al. 2017). USNs are interconnected infrastructure and therefore considered complex networks, hindering the straightforward design, management, and operation of these systems. The challenges increase when considering also climate change, population increase, urbanization and aging elements which can lead to financial and mortal threats (Dong et al. 2017). To achieve a high serviceability desired for USNs, they have to be maintained and rehabilitated regularly (Le Gauffre et al. 2007). Considering these challenges, it is important to make USNs more resilient. Resilience of USNs can be defined as its ability to minimize damage and rapidly recover from extreme loading conditions by lessening failure consequences (Mugume & Butler 2017). Therefore resilience-boosting intervention strategies should be applied to USNs to deal with both normal and extreme loading scenarios.

An efficient yet effective way of enhancing resilience of any infrastructure is to identify its most important elements to focus on these critical elements in management and maintenance strategies, hence increasing the overall system's resilience. The overall performance of the stormwater network depends on the performance of its individual elements. Characteristics of a particular element and its position in the USN contribute to the importance of such element (Meijer et al. 2018). Maintaining all the elements to the same high service level is expensive in terms of cost and resources required. If the degree of criticality of different elements of a USN is known, the elements with higher degree of criticality can be given priority for maintenance and rehabilitation to increase the system's resilience while decreasing the associated costs. The degree of criticality can therefore be used as a basis for risk-based asset management (Meijer et al. 2018). Risk assessment includes two parts, consequence of failure and probability of failure. The aim of this study is to focus on the aftermaths of failure and hence, only the consequence of failure part of the risk assessment is considered.

There exist only a handful of methodologies to identify critical elements in a stormwater network in literature. Arthur & Crow (2007) worked on a methodology to find critical elements based on serviceability loss after the failure. The pipes are ranked on the basis of combination of consequence scoring (depending on consequence of failure) and likelihood scoring (based on likelihood of failure). Möderl et al. (2009) presented the development and application of the software tool VulNetUD, which is a tool for GIS based identification of vulnerable sites of drainage networks. The tool uses the Storm Water Management Model (SWMM). Another methodology for this purpose frequently used in literature is called the Achilles approach, (Möderl et al. 2009; Möderl & Rauch 2011; Sitzenfrei et al. 2011; Mair et al. 2012), where the systematic Hydrodynamic Modelling Method (HMM) is used. Within this approach, the capacity of each conduit is reduced to almost zero one by one to mimic pipe blockage and then the hydraulic consequences such as overall system flooding are determined and pipes are ranked on the basis of flooding produced. Mugume et al. (2015) used a similar approach by modelling pipe failure and adding storage tanks in (a) centralized and (b) decentralized manner to gauge the impact on overall system flooding. Zhang et al. (2017) used an approach based on HMM for vulnerability analysis of USNs. A performance indicator based on flooding volume and runoff volume is used in this study to rank the pipes. For large networks and looped systems, these methodologies require very high computational time and effort.

To solve the problem of high computational efforts for assessing water networks, researchers have started working with graph theory and complex network analysis to model urban water infrastructure. Graph theory is a branch of mathematics that employs graphs to model complex real-life problems more efficiently (Turan et al. 2019). Up to now, graph theory has been widely used to solve different design and modelling problems of urban water infrastructure, such as identification of critical pipes (Pagano et al. 2019; Hajibabaei et al. 2022) and optimal design of pipes for water distribution networks (Sitzenfrei et al. 2020). Exemplary applications of graph theory for urban drainage networks (UDNs) are layout and design (Turan et al. 2019; Hesarkazzazi et al. 2022a, 2022b), functional analysis (Reyes-Silva et al. 2020), assessing redundancy (Hesarkazzazi et al. 2022a, 2022b) and assessing the efficiency of different topological positions of combined sewer overflow structures in a UDN (Sitzenfrei et al. 2013). Meijer et al. (2018) has described a method for finding critical elements of UDN based on graph theory, which focuses on comparing the costs of the graph by removing the pipes one by one. Head loss is used as weight and shortest path length as graph measure to find the critical pipes in this research. The critical pipes are recognized based on the cost associated with the graph after removing a particular pipe. The method is repeated for all the pipes and the pipe that results in the highest graph cost when removed is considered the most critical pipe and so on. However, there is a need to extend the aforementioned research for finding critical pipes to a non-iterative graph methodology to save the computational time and effort in the case of large, complex USNs and when a lot of simulations have to be made. The scheme mentioned in this study enforces an easy-to-implement method which can be easily extended to multiple pipe failures or cascading failures.

Recognizing the research gap, this paper proposes a new method based on graph theory and complex network analysis to identify the critical pipes of a USN. In contrast to the conventional hydrodynamic modelling method, the proposed method does not depend on iterative simulations which is a time-consuming procedure. Instead, it employs the concept of network analysis to mimic functional and hydraulic properties of USNs. Critical pipes are identified with a graph-based measure called Runoff Edge Betweenness Centrality (EBC_e^R) which can be interpreted as flooding volume by multiplying it with rainfall volume for a particular pipe when that pipe is blocked. This research focuses on both tree and looped networks and also discusses the impact of loop degree on the accuracy of the method. Finally, the results from the graph-based method (GBM) are compared with hydrodynamic modelling method (HMM) in terms of accuracy, computational time, and effort required.

A graph G is a set of nodes/vertices (V) and edges (E) and can be represented as G = (V, E), where V(G) is the set of vertices or nodes and E(G) is the set of edges. An edge is represented using an ordered pair of vertices (i,j) where, ‘i’ is the source node of the edge and ‘j’ is the target node of the edge. A graph is undirected when the graph has no particular direction or it is directed if the edge (i,j) is directed from node i to node j. A graph can be branched if there exists only one unique path between each pair of nodes (no loops) or looped if there exists more than one path between a particular pair of nodes. Additionally, a graph can be weighted, i.e., nodes or edges can have weights. In USNs, manholes, storage tanks, etc. are nodes/vertices of the graph and pipes, pumps and weirs etc. are the edges of the graph. In this study, we will use undirected graphs with weighted edges. Length is used as weight in this study and because length stays the same in both directions for a particular link, using an undirected graph is more convenient for implementing the method as compared to directed graphs, without impacting the results.

The graph measures in this study are modified to the functioning and hydraulic properties of USNs. Shortest path length (σ_i,j) is the first graph measure that is used in this study. It can be defined as the path between two particular nodes (i and j) which has a minimum sum of edge weights or costs associated with the graph (Dijkstra 1959). For calculating the shortest path lengths, the length of a pipe is used as an edge weight in this study. This is because the requirement is to find the shortest path in terms of shortest distance to the outlet from a particular inlet node and to give preference to large pipes with high capacities.

The first step is to identify the shortest paths from all inlet nodes (1,2,3,4,5) to the outlet node (6) shown in red in the example network. For every node, the pipes that are part of the shortest path get a value of 1 and all other pipes get a value of 0 forming a matrix of zeros and ones. EBC of a particular pipe is then calculated by summarizing the row's values associated with that pipe as shown in Table 1.

In the next step, EBC_e^R is calculated to make it more suitable to the use case of USNs (Table 2). Runoff area of each node R is calculated using the area of sub-catchments connected to a particular node and their imperviousness, which is multiplied by all matrix elements in the corresponding shortest path. When a particular row is summed up, EBC_e^R of that pipe is calculated.

For a fully branched network, the EBC_e^R multiplied by rainfall volume corresponds to the flooding volume when that particular pipe is simulated as blocked. This flooding volume is then compared with the flood volume obtained from the HMM method.

In the case of a looped network, the aforementioned methodology has to be adapted to include the impact of loops on flooding as well. This is done by employing the concept of Capacity Edge Betweenness Centrality (EBC_e^c), given in Equation (3).

In the toy example of a looped network shown in Figure 1(b), nodes 2,3,4 and 5 are part of the loops as they have alternative paths which means even if one of the pipes B, C, D or E are blocked, there is an alternative path for flow to the outlet 6 (shown in red). Capacity and slope of the pipe in an alternate path influence the amount of flow that can be redirected. Table 3 shows the methodology for flood calculation of a looped network. If pipe C is blocked in the above example, whole EBC_e^R value of pipe C (23) does not correspond to flood volume, rather a portion or all of it can be redirected to pipe B. The amount that can be redirected depends on EBC_e^c of the pipe B (8). Flood volume produced when pipe C is blocked can be calculated by subtracting the EBC_e^c value of pipe B from the EBC_e^R value of pipe C, which will be 15 in the case of the example. Similarly, the procedure can be repeated for all the pipes having alternate paths/loops. The pipes are ranked on the basis of flooding volume in the system in case of blockage. The pipe with the highest flood volume is ranked most critical.

Two different case studies are used to identify the potential of the proposed method. First, a small benchmark network is used consisting of 59 pipes and second, a real network of an Alpine municipality in Austria is used consisting of 373 pipes.

To extend the study to looped networks, redundant flow paths (forming loops) are created in the benchmark network. Two networks having three (5% loop degree) and six loops (10% loop degree) respectively are created to study the impact of loop degree on the proposed methodology. These loops are not designed, rather slope and length of these pipes are calculated by the SWMM model based on their positioning in the network while the diameters are estimated based on the adjacent pipes. The location of these loops was manually selected based on engineering judgement of only inserting a short connection and preserving a planar graph (no crossings).

For a real case study, the existing USN of an Alpine municipality is used located in the state of Tyrol in Austria, as shown in Figure 4. It is a fully branched network that comprises 373 links connected by 374 nodes. The diameters range from 250 mm to 1400 mm. The municipality has a population of 2931 inhabitants, and the network drains an area of 699 hectares. Similar to the benchmark network, in total 10 loops have been added manually to study the impact of loops on the proposed method.

For hydrodynamic modelling, the Environmental Protection Agency (EPA's) Stormwater Management Model (SWMM) version 5.1 is used (Rossman 2010). For the application of graph-based method, Python's module Networkx version 2.6.2 developed specifically for network analysis is used (Hagberg et al. 2008). In terms of hardware, a laptop having an Intel^® Core™ i7-10610 U CPU @ 2.3 GHz processor and 8 GB RAM is used. The system has a 64-bit Windows 10 operating system.

In total five networks (three benchmark networks and two real networks) are analyzed by comparing GBM and HMM in terms of accuracy and computational time. A two-year return period rainfall was used for the three-benchmark network while a one-year return period block rain event was used for the two real networks. For evaluations, 25% most critical pipes (15 pipes) for small benchmark network and 5% most critical pipes (20 pipes) for the large real network are compared from both methods to analyze how well the graph method identifies the most critical parts of a stormwater network.

It can be observed from these results that the proposed methodology has a high accuracy for branched networks both in the case of benchmark network and real network. The marginal differences in the results however, can be attributed to the fact that GBM does not include a detailed subcatchment hydrology like HMM does. Length, width and roughness of the subcatchments are incorporated in the method using runoff area of subcatchments (area * percentage imperviousness) in EBC_e^R concept. Also, the rainfall is added to the GBM model as a single value for the whole network and does not cater for the temporal variation of the rainfall while it is added as a 15 minutes block event in HMM.

For a benchmark network with three loops and six loops, GBM identifies 12 out of 15 most critical pipes the same as HMM. This shows that the accuracy of the GBM decreases by the introduction of loops in the network. For a looped real network, GBM correctly identifies 19 out of 20 most critical pipes but the order of criticality is the same for only two of these 19 correctly identified pipes, again showing a decrease in accuracy as compared to branched real network results.

The above sections show the comparison of a few most important critical pipes using GBM and HMM visually through Figures 5 and 6. However, to understand the accuracy of GBM holistically, it is important to make a comparison of flooding volumes for all the pipes as well. This is done using NRMSE as described in the methodology section. NRMSE is used to compare the differences between flooding volume values from GBM and HMM for all five networks. Lower values of NRMSE indicate a small difference in the values from two methods. The values for NRMSE for all five networks are given in Table 4.

It can be seen from the table that for all networks the GBM results have differences as compared to HMM results. The major reason for that is HMM has a numerical solver where full Saint Venant flow equations are solved. The dynamic flow routing that is used in HMM can account for complex hydraulic behaviors like backwater effect, entrance/exit losses and flow reversal etc. On the other hand, GBM is a simple method that operates mostly based on the topology of the network while incorporating some hydraulic and functional properties indirectly. Hence, it is understandable that NRMSE values are not zero for any of the network. Another reason is that when a pipe is closed in HMM, there still remains water that resides in the system depending on the diameter and slope of the pipe. This water is not accounted for in GBM and hence GBM overpredicts flooding volumes as compared to HMM.

It can also be seen from NRMSE values that GBM flooding volume values are closest to HMM flooding volume values in the case of a branched real network. For the real network in general, GBM performs better than for the benchmark network. One of the main reasons for that is the benchmark network is a flat network with large, high capacity pipes and hence for a particular pipe that blocks, more water can remain in the system as compared to a real network which has smaller pipes and higher slopes.

To better understand the impact of loop degree on the overall accuracy, a scatter plot shows flood volume from GBM and from HMM for both benchmark network and real network. Data fitting and correlation techniques are used to describe the impact of loop degree.

This pattern is then also confirmed by repeating the same procedure for a real network. Again, the R-squared value reduces from 0.96 in the case of a branched network, shown in Figure 7(d), to 0.90 in the case of a looped network, shown in Figure 7(e), showing the loss in accuracy of proposed GBM. Here the decrease in accuracy is even more significant. For 3% loop degree added to the system, the correlation between the data reduces more significantly than the benchmark network. The reason is that the real network is a large and already complex network. Adding loops to this network increases its complexity even further, causing more significant loss in accuracy for GBM.

To further confirm these results, Pearson correlation coefficient (r) values calculated for all five networks are shown in Table 5. It can be seen that the ‘r’ value follows the exact same pattern as R² values discusses above. The value of ‘r’ for branched benchmark network is 0.99 which reduces to 0.97 in the case of a network with three loops and further decreases to 0.96 for a six loops benchmark network. For a real network, similar to R² values, the ‘r’ value also decreases from 0.98 for a branched real network to 0.95 for a looped real network. Finally, NRMSE values increase with increasing loop degree which also confirm that the accuracy of GBM decreases with increasing loop degree.

The main reason behind the loss of accuracy for GBM when loops are added is the way how rerouting of water is being done in the graph method. The impact of rerouting of water in the proposed GBM is only considered for the adjacent pipes using EBC_e^c concept, while in reality this impact goes further downstream as well. Because of this simplification, the results for GBM become worse when the loop degree is increased. However, it can also be seen that even in looped networks the results of the proposed graph methodology are still sufficiently good (R-squared values greater than 0.9).

Table 6 shows the comparison of computational time taken by GBM and HMM. In the case of a benchmark network, HMM takes 5 minutes and 20 seconds to run. As it is an iterative method, the model has to run once for each pipe blockage scenario. In comparison, GBM only takes 6 seconds to run having a computational gain factor of 53 (320/6) as compared to HMM. The benefit of computational time increases with the size of the network, because running HMM takes significantly more time for larger and more complex networks. For example, HMM takes 45 minutes to run for real network, while GBM takes only 10 seconds with very little attention to code efficiency. The computational gain factor in the case of real case study is hence 270 (45*60/10). Subsequently, the computational gain factor between the two methods increases significantly with increasing network size. Thus, the graph method is much more efficient in the case of large USNs and when a lot of simulations have to be run.

Hybrid simulations involving both graph methodology and hydrodynamic simulations were also considered to figure out the computational gain and accuracy in that case. The 20 most critical pipes were found using GBM and then HMM was used to evaluate the criticality of these 20 pipes. The hybrid simulations were performed for branched real case study. The accuracy of hybrid simulations in this case is 100%. It identifies all 20 pipes and in the same order of criticality, but the computational time is significantly less as compared to HMM because in this case only 20 iterations of hydrodynamic simulations are required. The hybrid method takes around 3 minutes to run (10 seconds for GBM and 8*20 for HMM simulations) as compared to 45 minutes of HMM having a computational gain factor of 15 over HMM.

GBM can be setup with just nodes, links and sub catchments data. On the other hand, setting up a full scale urban hydrodynamic model requires more data including, soil information, land use, etc. Hence, GBM presented in this study is less data-intensive as compared to conventional HMM. Additionally, it is also easier and less time-consuming to set up the graph method as compared to setting up a full-scale hydrodynamic model. Once the code is ready for running the graph methodology, it can be used for different case studies by making minor, quick changes, while the hydrodynamic model has to be set up from scratch every time.

GBM has a number of advantages over other commonly used models, e.g. conceptual hydrological model including GBM directly converts the network to a graph and structural and layout details are very well preserved. GBM can be adapted to a higher level of combinatorial problems very easily and can be used to test other graph metrics. It is also a non-iterative method, so it takes less computational effort, the methodology is easy to implement and can be extended to multiple pipe failure. The methodology can be used for specific practical use cases, for example when a lot of simulations or scenarios are required, e.g. deep uncertainty analysis, future developments, multiple pipe failure combinations etc., or when the complete data is not available to setup the full hydrodynamic model.

The GBM described in this study has some limitations as well. For instance, our proposed framework is not able to model complex hydraulic behaviors like the backwater effect resulting from the blocked pipes. In addition, rerouting of water in case of presence of loops is simplified by the GBM while in reality it is much more complex. This implies that the rerouting can affect the pipes further downstream as well, which is not yet modeled using GBM. This also explains the decrease in accuracy of the method as more and more loops are added.

Future work in this regard will focus on extending the proposed GBM to more diverse real-life case studies. Capacity considerations will also be added to the methodology. Impact of hydraulic structures on GBM and how they can be incorporated without compromising accuracy will also be part of the future work. One of the next steps in this research is to further explore the potential of a hybrid graph and hydrodynamic modelling approach. Additionally, the research will also be extended to multiple pipe failure scenarios and potentially to cascading failures using GBM.

In this study, a new graph-based methodology (GBM) is proposed based on so-called runoff edge betweenness centrality (EBC_e^R) as a measure to identify most critical pipes of urban stormwater networks (USNs). The method uses network analysis techniques adapted to USN to mimic the hydraulic and functional properties. The method does not include the capacity problems of the initial system; hence it is important that the base flooding in the initial system is zero. Key findings of the study are mentioned below:

• Results indicate that the graph method is highly accurate in case of branched networks, R² value of 0.98 and ‘r’ value of 0.99 for benchmark network. The value decreases to R² = 0.96 and r = 0.98 in the case of branched real network which is larger and more complex showing that the increasing complexity and size of USN slightly reduces the accuracy of the method.

• Normalized root mean square error values for all five networks show that the real network performs better than the benchmark network, specifically the branched real network has the least differences between flooding volumes from two methods.

• Impact of loop degree on the methodology is also studied in this research. The results show that the accuracy of methodology decreases by introducing loops. Furthermore, GBM becomes less accurate with increasing loop degree as is clear from the case of benchmark network.

• Real network is used to study the impact of higher return period rain on GBM. The results indicate that the accuracy of the methodology decreases with increasing return periods showing that the method does not work very well when the system is already flooding because of lack of capacity.

• Although the accuracy of graph methodology is not as good as HMM, the biggest advantage of using GBM lies in the difference in the computational time required to run both methodologies. GBM has a computational gain factor of 53 for benchmark network which increases to 270 for the real network. This shows that not only the proposed GBM is efficient in terms of computational time but also the efficiency increases as the size of the network increases.

• Also, GBM is less data intensive and is easier to setup as compared to a full-scale hydrodynamic model. Especially for larger networks and more scenarios (e.g., cascading failures, failure combinations), GBM can provide results in more reasonable time.

• Additionally, a hybrid method based on both graph methodology and hydrodynamic simulations can be used to find out critical pipes of a USN with higher accuracy as compared to GBM and in significantly less time as compared to HMM.

• The proposed GBM in this paper can be used by small utilities where a quick initial and preliminary analysis is required or where the data available is not enough to setup a hydrodynamic model. Moreover, in the case of large cities with large-scale USNs where running multiple simulations of conventional hydrodynamic model becomes too time-consuming, the proposed methodology can be promising.

This study is funded by Austrian Science Fund (FWF) P 31104-N29

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

The authors declare there is no conflict.