A graph-based method for identifying critical pipe failure combinations in water distribution networks

Water distribution networks (WDNs) are complex infrastructures consisting of sources, pipes, and pumps that transport water from sources to consumers (Quitana et al. 2020). Pipes are the main component of WDN, comprising majority of networks and connecting all other elements within it. This renders them more susceptible to failure compared with other components (Jun et al. 2008; Hajibabaei et al. 2022). Pipe failures can lead to interruptions in water supply, impacting economic and social aspects within urban environments (Marlim et al. 2019). Thus, assessing WDNs across various failure scenarios is crucial to identify critical elements and minimize interruptions during such events. In this context, resilience assessment is of paramount importance as it evaluates the system's ability to withstand and recover from failures or disruptions, thereby minimizing service interruptions, protecting public health, and upholding the overall functionality of WDNs (Diao et al. 2016). One of the primary challenges confronting engineers and managers of WDN face is accurately identifying critical pipes and their combinations, which is essential for sustaining a resilient system and enhancing the resilience of the WDN.

The failure probability of pipes is often unpredictable because of age or sudden changes in pressure, and critical impacts can arise from a combination of pipe failures rather than a single failure (Tidwell et al. 2005). One of the primary challenges encountered by engineers and managers of WDNs is the proactive identification of critical pipes and their combinations in order to plan counteractions. Failure of pipes could reduce network functionality leading to a reduction in pressure and subsequently influencing the demand supplied, which can negatively affect WDN resilience. Due to the complex hydraulic behaviour in WDNs, the critical combinations of pipe failures, significantly affecting demand supplied, remain unclear. Therefore, having knowledge of critical combinations of pipe failures could help decision makers to proactively plan counteractions or consider it in the yearly rehabilitation work (Bata et al. 2022). Therefore, identifying critical failure combinations is essential for improving resilience and emergency mitigation of WDNs (Berardi et al. 2014).

The criticality of pipe failure combinations can be evaluated by calculating the water supply decrement caused by their failures in WDNs. Efficiently pinpointing critical pipes in large WDNs presents a combinatorial challenge. Therefore, hydraulic-based approaches are commonly used to evaluate the pipe criticality in the event of failures (Berardi et al. 2014). Various studies in the literature have successfully used hydraulic-based methods (Diao et al. 2016). However, the computational efforts are substantial, particularly for large-scale networks, although many combinations yield marginal impact on the network performance. Additionally, depending on the failure scenarios, WDN networks need extensive input data, and many water utilities lack hydraulic models or possess incomplete data (Chen et al. 2021). In recent years, significant strides have been made in exploring alternative methods for pipe criticality analysis for WDNs. One such alternative is graph-based methods, which have been employed in literature for pipe criticality analysis (Chen et al. 2021; Hajibabaei et al. 2023a). The method relies on the WDN network's connectivity, which is represented through a mathematical graph-based approach. The approach models the pipe and node characteristics of the WDN and integrates hydraulic aspects to imitate the hydraulic behaviour (Hajibabaei et al. 2023a).

Graph-based ranking methods have been used in several research areas in WDNs, including resilience evaluation and enhancement (Herrera et al. 2016; Pagano et al. 2019), water quality analysis (Sitzenfrei 2021), WDN optimization (Diao et al. 2022), and seismic performance evaluations (Li et al. 2023). However, the graph-based methods employed for pipe criticality analysis have often neglected hydraulic features such as water flow (Chen et al. 2021) and primarily focus on topological properties like the length and diameter of pipes (Pagano et al. 2019). Although these methods reduce the computation time and the required data (Ulusoy et al. 2018), they ignore most hydraulic constraints. Additionally, their application is currently confined to analysing single pipe failures (Hajibabaei et al. 2023b). Therefore, the potential of graph theory methods for analysing combinations of multiple pipe failures remains largely untapped.

To address this gap, the research aims to develop a new graph-based approach to identify critical pipe failure combinations and ranks for multiple pipe failures. The developed approach is compared with the state-of-the-art hydraulic-based method from accuracy and computational time perspectives. Additionally, the research also discusses the potential of a combined method, ‘hybrid hydraulically informed graph-based ranking method (HHGM)’ integrating the hydraulic-based method into the graph-based approach to get exact accurate rankings and robust output for pipe criticality analysis.

In the hybrid method, the graph-based method is utilized for identifying the combinations with failures and these combinations are selectively cherry-picked to do hydraulic-based ranking method. Subsequently, the hydraulic simulation is performed to rank the selected graph-based combinations, called ‘hybrid hydraulically informed graph-based ranking (HHGM)’. In this work, the graph of the WDN was created using the hydraulic model, but of course, the graph of the WDN could be also created using geometric data only to investigate the graph-based rankings. However, in such situations, obtaining rankings and results using the HHGM would not be feasible.

WDN connectivity, which is based on its spatial layout, is represented using a mathematical graph object to capture its topological features. A WDN graph comprises a set of vertices, which represent nodes (n) and source (s), and edges (e), which represent pipes, pumps, and valves. In this research, we focus solely on pipe combinations, assuming that each pipe can be isolated separately, while future work will aim to incorporate valve and segment criticality.

The initial phase of the study involved identifying failure combinations, where all possible combinations with the available pipes in the WDN were determined using the ‘itertools’ function in Python (Python Software Foundation 2022). Bridges in a network can be identified through graph analysis, which removes individual edges and checks for the presence of disconnected nodes in the network (Hagberg et al. 2008). If any disconnected nodes are found after removing a particular edge, that edge is identified as a bridge. Subsequently, combinations containing bridges were systematically excluded because bridges represent individual pipes or edges whose failure could disconnect parts of the network from water sources (Bollobás 1998).

This study employs two graph metrics are employed for graph analysis. The initial metric is the shortest path (SP), which determines the shortest path from a single node to a source (e.g., tank). In a WDN graph, the SP between source and demand nodes is important and should represent efficient water flow paths with the least hydraulic resistance. Therefore, to emulate the hydraulic resistance a weighted function determined by the ratio of pipe length to diameter is utilized to find the shortest (supply) path (Herrera et al. 2016). Employing the Single Source Dijkstra's algorithm, the study efficiently computes the shortest path length (SPL) from a specified source node to target nodes in the WDN graph using positive edge weights (Dijkstra 1959).

After identifying various combinations of edge failures, GFM is computed for each combination. Subsequently, combinations yielding a GFM of zero are recognized as having no impact on the network's performance during failure conditions. The remaining combinations are then ranked based on GFM, which is called ‘graph-based ranking’. Higher GFM values indicate combinations with a greater impact on network performance and criticality.

To enhance accuracy, and robustness in comparison to the graph-based ranking method and computational efficiency relative to the hydraulic-based ranking method, a hybrid hydraulically informed graph-based ranking method (HHGM) methodology which combines both techniques is used. The affected combinations (combinations with a GFM value greater than zero) or user-defined range of critical combinations from graph-based ranking methods are cherry-picked and passed onto the HHGM method for further analysis. The combinations are then analysed with the hydraulic-based ranking method and then ranked according to the HFM values.

The second case study is the Jilin network (Bi & Dandy 2014), a small-scale WDN also for benchmarking purposes. This network comprises 34 pipes, 27 junctions, and a single reservoir serving as the water source (Figure 4(b)). The Jilin network presents a suitable combination of looped sections and branched subsections, making it well-suited for testing scenarios involving both connected and disconnected failures. This feature allows the evaluation of the proposed method in terms of its ability to handle and predict the criticality of pipes under various failure scenarios.

The third case study is a real-world medium-scale WDN from an Alpine municipality in Austria investigated as part of the project ‘RESIST’. The network has been skeletonized using WaterGEMS software skelebrator function (Bentley 2023), resulting in a simplified model that facilitates quicker and more efficient analysis. The skeletonized model of the main zone comprises 299 pipes, 207 junctions connected to a tank and a primary water source with an average base demand of 21.52 l/s (Figure 4(c)). The layout representation of this network has been visually altered due to data protection while the hydraulics are fully preserved. The network has a high level of looped configurations, enabling the assessment of the proposed method in predicting the critical ranking of all combinations within a real-world looped network. Both Jilin and the skeletonized real-world WDNs provide valuable opportunities for validating and comparing the ranking performance of the graph-based method.

The results of graph-based rankings are compared against those obtained with state-of-the-art hydraulic-based ranking using Spearman correlation (Spearman 1904) for all case studies. The Spearman coefficient captures non-linear correlations between rankings by considering the ranks of variables rather than their actual values, and it focuses on the monotonic relationship between rankings, measuring direction and strength of association regardless of the linearity of the data (De Winter et al. 2016). Furthermore, the computational time needed for each method is determined and compared.

The graph-based ranking method for HHGM is implemented using NetworkX package in Python 3.9.13. The hydraulic analysis is entirely coded using the WNTR (Water Network Tool for Resilience) package (Klise et al. 2017) which cooperates EPANET 2.2. The computational hardware employed for this study consists of a laptop equipped with an AMD Ryzen 3 PRO 5450 with Radeon Graphics 2.60 GHz processor and 32 GB RAM. The operating system utilized is 64-bit Windows 11 Enterprise.

The failure magnitude values for both graph-based ranking method (GFM) and hydraulic-based ranking method (HFM) were utilized to determine graph-based ranking and hydraulic-based ranking, respectively, for all pipe combinations. A correlation analysis was conducted to validate and assess the agreement and consistency between the graph-based ranking and with state-of-the-art hydraulic-based ranking. This evaluation was used to compare the performance and reliability of the graph-based ranking methodology.

Furthermore, the benchmark network Jilin (Figure 5(b)) revealed the graph-based ranking method's limitations in precisely predicting variations in supply failures, e.g., several pipe combinations with the same failure magnitude. It could also be attributed to the fact that incorporating hydraulic components such as pipe roughness, pressures, and valves into the model could lead to a more robust analysis of flow behaviour and pipe criticality analysis. In contrast, the graph-based method relies solely on EBC^Q calculations along the weighted shortest path towards the source, assuming the entire demand load was on particular pipes (SPL). However, demand loads are typically distributed among various alternative flow paths. Hence, the graph-based method may overlook the nuanced allocation of demand loads, leading to differences when compared with hydraulic-based rankings. In hydraulic-based ranking, the hydraulic functionality of elements like pumps and control valves are considered, whereas in a graph, these features are only represented as edges and this could impact the rankings, like in the investigated real-world network.

Table 1 provides a summary of the total number of combinations in each network, the overall number of critical combinations, Spearman correlation between graph-based and hydraulic-based rankings and critical pipe combinations that were overlooked by graph-based ranking. The comparison between graph-based ranking and hydraulic-based ranking revealed a significant correlation between the two methods. For the two-loop network, correlations are assessed for the entire failure combinations ranging from 2 to 7 pipe failures. The correlations range from 0.750 for two-pipe combinations with the lowest correlation to a perfect correlation of 1 for five-pipe and six-pipe combinations.

For the Jilin network and real-world network, correlations are investigated for combinations ranging from two to five pipe failures and only two pipe failure combinations, respectively. This was due to the significantly higher computation time of the hydraulic-based ranking with a larger number of edges than the simple two-loop network. The correlation values for the Jilin network provide a significantly positive correlation between the two methods with the Spearman correlation greater than 0.812 for all the pipe failure combinations tested (Table 1). For the real-world network, there is a high correlation of nearly 1.0 between the two approaches for two-pipe failure combinations. These results show the effectiveness of the graph-based ranking method in detecting the criticality ranking of multiple pipe failures in WDN.

However, the graph-based ranking method failed to capture a varied array of critical pipe combinations with specific failure values in the WDN. This can be attributed to the fact that the graph-based ranking method allocates the entire demand load to specific edges along the shortest path, thereby overlooking certain hydraulic aspects of the system (such as redundant alternative flow paths). However, overlooked combinations primarily consisted of low-ranked combinations with lower HFM values. For instance, the last two ranked failure combinations were missed for two-loop networks in two-pipe combinations, while in real-world networks, the last five ranked failure combinations were not identified. Similarly, in the Jilin network, the failure combinations missed are notably the lower-ranked and less impactful combinations. The graph-based ranking method efficiently filters out 99% of non-impactful combinations from the analysis in real-world WDN, enhancing its efficiency for swift results during emergency situations in large WDNs.

The graph-based approach exhibits a positive correlation with the state-of-the-art hydraulic-based ranking method for pipe criticality assessment; nevertheless, as previously noted, differences in rankings persist. To address this, a hybrid hydraulically informed graph-based ranking method (HHGM) is proposed which runs hydraulic-based analysis only for the cherry-picked combinations of the graph-based ranking method, yielding precise ranking results. Notably, the graph-based ranking method tends to overlook the lower-ranked combinations, thus remaining valuable for identifying the most critical pipe failure combinations. The graph-based method for the real-world WDN filters out more than 99% of combinations (excluding bridges and their combinations) without any impact on the WDN supply reliability. This accurately detects 90% of critical combinations, reducing the number of combinations cherry-picked for the hydraulic-based ranking method. As a result, the HHGM ranking method for real-world WDN is considerably faster (26 times faster) compared with the hydraulic-based ranking method. The HHGM facilitates a more accurate assessment of the impact scale through the calculation of HFM values, providing a robust and realistic measurement unit for understanding the exact consequences of failure combinations on the WDNs. Consequently, such swift evaluations could be instrumental in disaster response scenarios, effectively enhancing the overall resilience of the system.

The graph-based ranking method consistently aligned with the hydraulic-based approach in determining failure magnitude (GFM and HFM) values but with fewer constraints, thereby enhancing computational efficiency. In the real-world WDN, the graph-based method took approximately 2 min, while the hydraulic-based method required around 129 min (64 times slower) to analyse two-pipe combinations. In benchmark networks, the graph-based ranking was 66–110 times faster for a two-loop WDN and 34–40 times faster for the Jilin benchmark network compared with the hydraulic-based method (refer to the computational gain factor in Table 2). These results demonstrate that the graph-based approach is significantly faster compared with the state-of-the-art hydraulic-based method.

The hybrid-based ranking method is slightly slower compared with the hydraulic-based ranking method for the benchmark networks because HHGM considered all combinations as critical and ran the hydraulic simulations for the entire set of combinations, similar to the method employed by the hydraulic method. The HHGM method proves to be more advantageous for large WDNs with numerous pipe combinations, where computational efficiency and the number of non-impactful failure combinations become crucial factors. For example, the hybrid-based method is 26 times faster than the hydraulic-based ranking method for the real-world WDN (Table 2). The hybrid-based ranking method proves to be faster in this specific case study because it encompasses a multitude of pipe combinations with the need for cherry-picking those devoid of GFM for hydraulic-based ranking analysis. Both the graph-based and HHGM methods could be used to faster identify critical pipe combinations than the hydraulic-based ranking method based on the network size.

The study introduces a graph-based ranking method to assess the criticality of pipe combinations within WDNs, utilizing network components like pipes and nodes in a graph, topological features, and spatial demand distribution. This approach effectively identifies combinations of pipes whose failure could significantly impact the functionality of WDN. Compared with the state-of-the-art hydraulic-based method, the graph-based ranking approach demonstrates superior computational efficiency and acceptable accuracy. This increased speed is credited to the method's ability to filter out combinations without a significant impact on the supply, resulting in a reduced number of non-important combinations being assessed. This is particularly beneficial for large networks with many possible pipe failure combinations.

Moreover, the graph-based analysis can also be conducted without a hydraulic model by constructing the network graph from, e.g., CAD or GIS files. This highlights its ability to expedite criticality analysis with minimal data prerequisites, rendering it particularly well-suited for addressing failures within small- to medium-sized WDNs lacking comprehensive data and resource allocations for building a hydraulic model. However, it is essential to recognize the limitations of the graph-based methodology, notably its occasional failure to detect all critical combinations and its tendency to overlook scenarios with lesser impact, owing to the omission of crucial parameters such as topological attributes and frictional losses, in contrast to hydraulic-based methodologies. Additionally, the graph-based approach falls short in providing a robust assessment (i.e., the exact value of HFM) of pipe failures, especially when compared with the state-of-the-art hydraulic-based approach.

To address these limitations, the study proposed a hybrid approach, referred to as the HHGM, which integrates graph-based and hydraulic elements to enhance the criticality assessment of multiple pipe failure scenarios in WDNs. The graph-based component of HHGM effectively screens out combinations with no impact on the network by calculating the graph failure magnitude of each scenario using graph metrics. This hybrid method enhances computational speed and efficiency while also providing accurate and robust results in the analysis of pipe failures. The findings show that the computational time required by the proposed HHGM is significantly faster than the state-of-the-art hydraulic-based simulation, particularly for large WDNs with a substantial number of combinations. The effectiveness of the graph-based method in eliminating combinations with no impact leads to a reduced number of non-important combinations in the results.

Future research would endeavour towards the integration of multiple paths, a complex task due to the time-consuming network decomposition, to achieve more precise estimations of water flow. Additionally, there will be an exploration of the incorporation of other essential WDN elements, such as pumps, into the graph. Addressing these limitations is essential to enhance the graph-based ranking method's accuracy and suitability in assessing the criticality of multiple pipe failure combinations. The method can provide water utilities with an effective way to identify combinations of critical components using graph-based approaches. Additionally, a hybrid approach is proposed, combining the advantages of graph- and hydraulic-based approaches for robust failure assessment and for specific failure scenarios. This approach strengthens operators' capability to increase the resilience and reliability of the entire network, by specifically tailoring maintenance and rehabilitation programmes, e.g., to also prioritize pipes in critical combinations. Nonetheless, with continued refinement, the graph-based ranking method and HHGM have shown significant potential for advancing WDN management in the detection of critical pipes.

The project ‘RESIST’ is funded by the Austrian security research programme KIRAS of the Federal Ministry of Finance (BMF). Among others, the project RESIST aims to increase the resilience of water distribution networks by further developing graph-based approaches for water distribution networks to practical applications.

Data cannot be made publicly available; readers should contact the corresponding author for details.

The authors declare there is no conflict.