Time-efficient criticality analysis and placement of isolation valves with graph-based approaches in water distribution networks Open Access

Continuous drinking water supply is crucial for the social well-being and economic growth of an area (Butler et al. 2017). Water distribution networks (WDNs) are critical urban infrastructures composed of different interacting hydraulic components that ensure a reliable and safe water supply to users. A WDN consists of consumer/demand nodes, pipes, tanks, reservoirs, pumps, and valves (Perelman & Ostfeld 2011). WDNs are divided into hydraulically isolated segments containing elements like nodes, pipes, tanks, and pumps, which can be isolated using isolation valves (Zischg et al. 2019). When a pipe fails, isolating it often requires shutting down other nearby pipes within the same segment, depending on the arrangement of isolation valves (Mottahedin et al. 2024). Such failures can involve single, or multiple pipes or valves, leading to the failure of entire segments rather than individual elements (Liu & Kang 2022). If one of the isolation valves for isolating a specific segment is faulty, both connected segments have to be isolated, which further increases the number of affected nodes and demand not supplied.

Therefore, the identification of these critical valves is essential for enhancing the resilience of WDNs, focusing on minimizing the number of affected customers and ensuring a timely repair of the impacted elements (Tornyeviadzi et al. 2022). The primary method for the identification of critical isolation valves relies on hydraulic analysis conducted using the state-of-the-art EPANET software analysis (Berardi et al. 2014; Diao et al. 2016). Thereby, valve criticality in this research refers to the impact of an element's failure on system performance quantified by the demand not met due to the combined effect of required segment isolation and valve failure. This involves simulating the WDN after isolating or removing the affected element and assessing the results of hydraulic conditions based on unfulfilled demand. Afterwards, this information can be used for strategically adding new isolation valves, to swiftly isolate specific sections during failures for repair, while ensuring a regular supply to the majority of the non-affected zones (Choi et al. 2018). Several studies have focused on segment identification, valve placement, and segment isolation (Giustolisi & Savic 2010; Alvisi et al. 2011). These studies primarily emphasize hydraulic optimization methods for these purposes. Hydraulic model-based approaches require a hydraulical model that incorporates roughness, geodetic, and calibration data. Additionally, its computational demand can be significant, particularly for large and complex WDNs (Chen et al. 2021). Additionally, operators of WDNs often lack the basic hydraulic models required for such simulations (Hajibabaei et al. 2024), making it difficult to perform hydraulic-based optimization for locating new valves to reduce the criticality (Möderl & Sitzenfrei 2019; Yu et al. 2024).

Alternative methods, such as graph-based criticality analysis of pipes, which are less data and computationally intensive, have been discussed in the literature (Pagano et al. 2019; Hajibabaei et al. 2023). These methods rely on the WDN's connectivity, represented through a mathematical graph representing the network (Ulusoy et al. 2018). This approach converts the characteristics of pipes and nodes in the WDN to a graph and can integrate hydraulic aspects to mimic hydraulic behavior, allowing for faster and less data-intensive analysis (Pagano et al. 2019). One such approach tailored for analysis of WDN is demand edge betweenness centrality (EBC^Q), a customized graph measure specifically adapted for WDNs (Sitzenfrei et al. 2020). EBC^Q is a customized graph-based measure based on spatial demand distribution, connectivity, and optimal flow to assess edge/pipe criticality in a highly computationally efficient manner with low data requirements. This approach was for example utilized for the failure of multi-pipes and resilience enhancements, achieving a decrease in computational time compared to traditional hydraulic approaches by a factor of 40 and 1,400, respectively (Hajibabaei et al. 2023; Satish et al. 2024). This is because hydraulic models solve complex nonlinear flow equations, while graph-based approaches use linear algebra for efficient network analysis, offering greater computational efficiency in water distribution studies. However, an extension of these efficient graph-based concepts to assess valve criticality is lacking in the literature which could potentially find critical valves, which could inform operators of proactive maintenance practices.

To address these limitations, this study proposes a graph-based method that could enhance resilience by proposing a two-step approach:

• Graph-based identification of critical valve rankings in WDNs.

• Strategically placing new valves to further reduce the demand failure during segment isolation, thereby decreasing valve criticality and ultimately lowering the overall number of critical valves in WDNs.

The methodology employed stands distinct from other graph-based or valve criticality analyses, as it combines the strengths of graph-based methods and eigenvector centrality to clearly identify critical valves based on the connectivity of segments, all without relying on hydraulic models.

In the first step, a graph-based ranking method is developed to identify valve criticality (Section 2.1) by creating a mathematical graph representation of the WDN, using geographic information system (GIS) data, to evaluate valve criticality. The method requires basic pipe data, such as length and diameter, along with the demand at each junction or node. Initially, the impact of segment isolations is calculated by determining graph-based failure magnitude (GBFM) values. The obtained values for segment isolations are then used as weights for determining the eigenvector centrality and to rank valves based on their influence within the system. Afterwards, critical valves are identified using the rankings (Section 2.2), and a graph-based community detection method is employed to strategically add new isolation valves in connected segments, reducing segment sizes and improving network cohesion and connectivity. This iterative process reassesses critical values, ultimately decreasing the criticality of isolation valves. Finally, the segment isolation results from the graph-based approach are compared with those from a hydraulic-based method to evaluate effectiveness (Section 2.3).

The connectivity of WDNs is modeled using a mathematical graph to capture its topological features. In the graph, nodes correspond to demand nodes, tanks, and reservoirs, while edges represent pipes, pumps, and various types of valves, including isolation valves (Sophocleous et al. 2016). The initial step involves the identification of segments in WDNs and creating a list of these segments along with their associated isolation valves.

The utilized GBFM trends to overestimate the value of demand failed. The primary reason for this overestimation is that EBC provides an estimation of the transport of demand from source to demand nodes and the topology of the network. However, redundant capacities are not accounted for and therefore, as suggested in Hajibabaei et al. (2023), concluded that considering ΔEBC as EBC abnormal minus normal provides a better adjustment to this overestimation. The process is repeated for all segments and the impact of the isolation of each segment is established.

In the equation, represents the eigenvector centrality of neighboring nodes relative to node i = 1, 2, …. n, where n is the number of nodes adjacent to node j and is the members of adjacency matrix A for the network (i.e., is equal to the weights passed on from the segment isolation GBFM values) and is the largest EV obtained in each iteration. Nodes are ranked higher by EV when they are connected to other highly critical nodes, meaning a node's centrality increases if it is linked to more influential nodes (Bonacich 1972; Rajagopal et al. 2017).

The rankings of HBFM and eigenvector centrality are then compared using Spearman's rank correlation. The coefficient assesses the strength and direction of monotonic relations between rankings, allowing it to capture nonlinear correlations by focusing on the ranks rather than the actual values of the variables (Spearman 1961). The correlation analysis was conducted to validate the proposed methodology in the research against state-of-the-art hydraulic-based methods.

After the identification of critical valves, new isolation valves are strategically placed within the two connected segments to decrease the impact of valve failure, using a community detection method (Creaco et al. 2023). First, any segment with critical valves within the network is identified from Section 2.1, and subsequently, these segments are decomposed into smaller subdivisions utilizing community detection. Next, the Louvain community detection algorithm is employed, as the modularity of this method serves as an effective criterion for identifying valve locations in a way that minimizes the number of valves required for new segments while also determining segments with higher connectivity within their communities.

The input for the community detection process is the WDN graph, while the outcome is node clusters within the critical segments used for the installation of new isolation valves at the boundaries of the identified clusters. The Louvain community detection method is based on a heuristic approach, and at the initial stage of the algorithm, each node is considered a separate community. Subsequently, nodes are assigned to neighboring nodes that yield the highest modularity gain during each iteration. The process is continued until there is a decrease in average valve criticality by adding a new set of valves. For each step, the number of valves is determined based on the pipes located at the border between communities. It should be noted that the number of valves required is determined by the results of community detection, which depend on the topology of WDNs and the resolution of the community detection process. In the valve location process, every edge in a segment has the potential to accommodate a valve placement, as the segment is defined by the surrounding isolation valves.

The proposed research was conducted entirely using Python and relevant programming libraries. The graph-based approach was implemented utilizing the NetworkX package (Hagberg et al. 2008). Additionally, hydraulic-based analysis for method validation was conducted using the EPAENT 2.2 in the WNTR package (Klise et al. 2017).

The analysis of valve criticality, based on a combination of the GBFM and eigenvector centrality was conducted and then compared with those obtained using the HBFM method. New valve placements were then determined using the community detection technique, and the corresponding results were generated for further evaluation.

As the results reveal, the rankings of the valve remain the same, but the impact of a valve failure clearly decreased and was used for further discussions. For the Middle Eastern WDN, the number of critical valves decreases from 29 to 11, and for the Alpine WDN, from 43 to 5 valves, as can be seen in the reduction of nodes with EVs between 0.85 and 1 in Figures 8(c) and 8(f) respectively comparing to Figure 6. These reductions, based on eigenvector centrality values, demonstrate a substantial decrease in the number of critical values in the WDN especially in the most critical segment. In both case studies a certain level of criticality exists due to the branched structure of the WDN from the elevated tank to the looped section. To reduce this criticality, adding parallel pipes or increasing the network's looped connections can be considered as potential options.

This study proposes a purely graph-based methodology for identifying critical isolation valves and strategically placing new valves within WDNs, without a need for hydraulic simulation. This research extends the work of Satish et al. (2024), adapting the methodology from multi-pipe failure analysis to assessing valve criticality and ranking in WDNs.

The graph-based method for valve criticality analysis is computed using GBFM and eigenvector centrality. The methodology was applied to two case studies on WDN with a large single main segment from Middle Eastern and Alpine WDN with around 1,200 segments and 1,290 isolation valves. By combining the methods, the methodology offers a comprehensive evaluation of valve criticality by considering the overall connectivity of valves used as weights to produce the graph-based segment isolation impact. The comparison of the graph-based results with hydraulic-based methods shows a high Spearman correlation (above 0.9 for both case studies), confirming that the proposed approach is a viable alternative for determining valve criticality, particularly in networks lacking detailed hydraulic models. By effectively identifying and ranking the most critical valves, the graph-based method enhances network resilience through targeted interventions, reducing the likelihood of widespread disruptions during failure scenarios. Further, community detection techniques additionally contribute to the improvement of WDN resilience by optimizing valve placement and segment isolation. The division of large, critical segments into smaller communities through the addition of new isolation valves significantly reduces segment and valve criticality, as demonstrated in both the Middle Eastern and Alpine case studies. By reducing the size and criticality of segments, this method minimizes the impact of failures and enables more efficient WDN management.

The method could be used to improve WDN performance by facilitating strategic valve placement and enhancing the network's capacity to isolate and repair valves, segments, or pipes during failure scenarios. Furthermore, it can support inspection prioritization and optimize maintenance strategies, contributing to the overall resilience of the WDN. The developed approach overcomes challenges associated with traditional hydraulic-based analyses, providing a faster alternative that enhances the resilience of WDNs. Even with a hydraulic model, the proposed method enhances computational efficiency, making it useful for hybrid approaches that screen critical elements before exact hydraulic simulations.

If a hydraulic model is available, the strength of the proposed method is the increased computational efficiency, which can be beneficial also in a hybrid method (i.e., screening for most critical elements with the proposed method and exact hydraulic simulations of only those).

This methodology can be further adapted to evaluate different types of valves. Additionally, the methodology can be enhanced to generate absolute values rather than relying solely on ranks. Additionally, the community detection approach can be refined to enable more strategic valve placements by incorporating optimization techniques that account for the economic feasibility of the placements and their overall impact on the WDN. Finally, the entire process will be adapted for large-scale WDNs with complex structures, including multiple sources, various types of valves, and pumps.

The project ‘RESIST’ is funded by the security research program KIRAS of the Austrian 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.