Probability of network disconnection of water distribution system for maintenance prioritization

The municipal water distribution network (WDN) is the lifeline of communities. Since potable water is the most essential element for life, a WDN is designed to provide uninterrupted service to community dwellers. For this purpose, the water distribution system (WDS) is designed with an amount of redundancy using looped networks to provide alternative paths for situations if one or more links go out of service. It is, however, difficult to assess all possible paths from the source to the demand points for a municipal WDN containing thousands of demand nodes and pipes. The performance of the WDS in providing an acceptable level of service to consumers is assessed in terms of system reliability (Tung 1985). Over the last few decades, considerable research has focused on system reliability assessments of the WDN. However, no universally accepted definition and measure of system reliability has been used. Wagner et al. (1988) developed analytical methods for system reliability assessment using network connectivity and approachability. Wagner et al. (1988) and Quimpo & Shamsi (1991) incorporated multiple connections from several source nodes to demand nodes for estimating the system reliability. The connectivity and approachability are defined as the connection of all demand nodes to the source nodes, and the connection of a demand node to its source, respectively.

Su et al. (1987) and other researchers employed hydraulic failure as the reliability measure for WDS design optimization, which is based on the measure of hydraulic availability of the system needed to provide an acceptable level of service. This approach is rigorous and provides a precise description of a WDS. However, analysis of hydraulic availability involves extensive system simulations and is therefore computer time-intensive. To overcome the computational problem, several heuristic measures of system reliability were developed (Shamir & Howard 1981; Goulter & Coals 1986; Awumah et al. 1991), which are criticized for not evaluating the hydraulic availability (Cullinane et al. 1992). Cullinane et al. (1992) attempted to balance the two types of measures; hydraulic failure is evaluated for selected conditions. This approach still relies on heuristics and judgement. Shinstine et al. (2002) demonstrated that availability measurement provides a means of examining the robustness of a WDS during design, rather than relying on implicit judgement. They employed a hydraulic simulation model (i.e., KYPIPE) to obtain the values of a pressure head at each demand node by closing a pipe or a combination of pipes, which was repeated until all the combinations of the pipes were examined. Pipes were considered as repairable components and an average time to repair of 1 day was assumed. In this study, a WDS containing up to 109 pipes and 89 nodes was analysed. However, repeated hydraulic simulation of a larger WDN containing thousands of nodes would be tedious. Aydin et al. (2014) reported 7 days of simulation of a WDN using the EPANET model. Moreover, this approach only simulates the network conditions when valves are closed immediately after pipe breaks. Water disruption due to leaks in water mains is not simulated.

Despite the limitations, the hydraulic-based approach is desired for the design optimization of WDS, since it provides water availability at the demand nodes. On the other hand, for repairing deteriorating water mains in an existing WDN, the pipe breaks causing isolation of part of the system should be given priority. If isolated from the network, the demand nodes will not have any available supply. The focus of the present study is the prioritization of water mains for repair/maintenance and to identify the pipes and combinations of pipes causing isolation (disconnection) of parts of the WDN. The failure probability of the system is defined as the probability of disconnection. Although breaks of other pipes may also cause water to be unavailable at certain demand nodes due to low pressure, this is not considered here, to avoid computationally expensive hydraulic simulations.

To identify a pipe and combinations of pipes causing isolation, the minimum cut-set method is used. In the conventional minimum cut-set method, pipes causing system failure are rigorously examined, requiring complex and extensive computation. Yannopoulos & Spiliotis (2013) employed graph theory using a connectivity matrix to identify minimum cut-sets. The computational time required in this method is also significantly high, as discussed in more detail in the paper. To overcome this computational limitation, this paper employs complex network analysis (CNA) to find the minimum cut-sets of the network. CNA has been used for the quantification of structural properties of networks and to improve understanding of network connectivity and robustness. Complex network models have been applied in various areas including WDNs (Yazdani & Jeffrey 2010, 2011a, 2011b; Nazempour et al. 2016). Yazdani & Jeffrey (2010) discussed the metrics for CNA to evaluate the robustness and vulnerability characteristics of a WDN. Among several metrics for CNA, algebraic connectivity (AC) has been proposed and analysed by Fiedler (1973). AC is a well-known measure for evaluating the well-connectedness of a graph (Fiedler 1973; Capocci et al. 2005; Ghosh & Boyd 2006; Newman 2006; Yazdani & Jeffrey 2011a, 2011b). The network with higher AC is more robust and more tolerant to the breakage of links. AC provides information on graph partitioning that is closely related to the disconnection of nodes due to pipe breaks (Phan et al. 2017). Fiedler (1973) pointed out that an event of disconnection in a system would lead to an increase of AC. On the other hand, decrease of AC corresponds to a reduction of redundancy in the network (Phan et al. 2017). AC has been used to develop a framework to evaluate the redundancy or robustness of WDNs (Fiedler 1973; Yazdani & Jeffrey 2010; Phan et al. 2017). However, no such comprehensive modelling has ever been performed to take advantage of the characteristics of the AC for network reliability assessment.

The novelty of the current paper is the development of a method for finding minimum cut-sets of complex WDNs using AC. The proposed approach is computationally more efficient than the existing methods of finding minimum cut-sets. A reliability framework is then developed based on AC and the failure probability of pipe components. The proposed method is applied to a real WDN.

In Table 1, the pipe is named for the first and second nodes that it links. For example, pipe 5–6 means the pipe connects nodes 5 and 6. The numbers alongside in Figure 2 indicate the assumed geometric length of the corresponding pipe. For example, pipe 5–6 has 2.5 units length.

One of the major limitations of using the minimum cut-set approach for evaluating the disconnection probability of a large network is the high computational cost needed to determine all minimum cut-sets. Applying the approximation presented in Equation (13), the computational cost can be significantly reduced. The conventional approach to solve the minimum cut-set problem is to count all the paths connecting two different nodes of the network. Yannopoulos & Spiliotis (2013) used the connectivity matrix from graph theory to record all the paths. If any element of the connectivity matrix is zero, then there is a disconnection between the concerned nodes. Subsequently, the minimum cut-sets are found by removing (idealized for breaking) a set of pipes and recalculating the resulting connectivity matrix. If the connectivity matrix of the break-containing network comprises zero elements, then disconnection occurs. However, computational cost of such an approach may be significantly increased when the size of the network is large. In the following sections, the characteristic of the AC is investigated to determine the minimum cut-sets for a single pipe break and multiple pipe breaks.

• ⁠, if there is a link (pipe) between node i and node j.

• if there is no link (pipe) between node i and node j.

A network with higher AC implies that the network is better connected (Newman 2010; Yazdani & Jeffrey 2010, 2011a). The addition of links to a network has been observed to increase the AC, as reported in Ghosh & Boyd (2006) and Phan et al. (2017). Ghosh & Boyd (2006) have reported a method to maximize the AC with a set of pipes to increase the redundancy of the network when the number of nodes remains the same. On the contrary, the process of pipe breakage may be considered as a reverse process of decreasing the AC with the break or removal of pipes from the network. As long as the disconnection has not occurred, the AC tends to decrease, implying that the redundancy of the network is reduced after a break event. This indicates that if a break does not isolate a node or cluster of nodes, the AC will decrease from the value prior to the break.

The disconnection may be viewed as the direct failure of the network, considering the system failure as the state of not properly serving water to every demand node (i.e., the communities). The reduction of redundancy might lead to the disabling of service to demand nodes, but might not directly result in a network failure event. Thus, the AC will change with the removal of a pipe in the network, where:

• AC will increase if an isolation of nodes occurs, and

• AC will decrease if the redundancy is reduced.

Now, if the removal of a pipe leads to disconnection of the network (e.g., AC increases), such a pipe is considered as a minimum cut-set. Thus, by observing the change in AC by removing pipes one by one within the network, all minimum cut-sets can be determined.

For illustration, the AC for a hypothetical network shown in Figure 2 is estimated to demonstrate the numerical values of the parameter in describing robustness of the network. The network consists of 10 nodes and 13 links (i.e., pipes) with the AC of 0.19781 (i.e., AC_intact = 0.19781). It is representative of a WDN connecting two distinct communities. Community 1 contains nodes 1 to 5 and Community 2 contains nodes 6 to 10. The communities are connected by pipe 5–6. In other words, pipe 5–6 has a high betweenness.

Table 3 ranks 13 events corresponding to the removals of 13 pipes from the network. The difference between AC before and after removal of a pipe is presented in a descending order. There are three events with AC increases, resulting in the network disconnection. These are events 1.1, 1.2 and 1.3, with the removals of pipes 5–6, 8–9 and 9–10, respectively. These pipes are the three minimum cut-sets that contain only one break corresponding to events E_1.1, E_1.2 and E_1.3, shown in Table 2.

As seen in Figure 2, the removal of pipes 5–6, 8–9 and 9–10 will result in the disconnection of a node or cluster of nodes. Removal of pipe 5–6 caused the highest increase (i.e., ranked first) since it has high betweenness. Pipe 9–10 has the least increase because the removal of 9–10 leads to the isolation of a single node (node 10). Phan et al. (2017) have concluded from a previous study that the size and number of disconnected clusters greatly affect the increase of the AC.

The other ten events (i.e., event 1.4 to 1.13) in Table 3 show a decrease of the AC with removal of a single pipe, indicating no disconnection. However, the redundancy of the network is decreased, and thus the change in the AC shows a positive correlation to redundancy. Similar observations were reported in previous studies (Yazdani & Jeffrey 2011a, 2011b). These ten events can further be divided into two groups: the first group consists of events 1.4 to 1.10 with the removal of pipes in Community 1; the second group is the events 1.11 to 1.13 with the removal of pipes in Community 2, which has a higher absolute change in AC (ΔAC) compared to the first group. This difference is due to the fact that Community 2 (with AC= 0.5188) has less redundancy compared to Community 1 (with AC = 2.000).

From the analysis it can be observed that the ΔAC can be used for the following:

• 1.

  Identifying the disconnection and reduction of redundancy by observing the sign of ΔAC, where a positive sign (+) denotes network disconnection and a negative sign (−) indicates reduction of redundancy.

• 2.

  Identifying the components causing most significant disconnection based on the highest positive ΔAC.

• 3.

  Identifying the components causing the most significant decrease in redundancy, based on the highest negative ΔAC.

Since the computational cost of multiplying two matrices with size n × n is O(n³) for a naive algorithm, the computational cost of the last component of matrix B will be O(n⁴). Even for the improved algorithm proposed by Coppersmith & Winograd (1990), the computational cost of estimating will be approximately (n-2) × O(n^2.375477) = O(n^3.375477). However, using the Eigenvalue problem, it can be reduced to O(n²) for each step of the interaction, for calculating only Eigenvalues (Flannery et al. 1992), compared to the cost of O(n³) otherwise. Thus, calculating the last component in Equation (18) itself is more computationally expensive than the Eigenvalue problem. Consequently, this method of counting paths is more computationally expensive than the method based on the Eigenvalue problem. Using the available functions of Matlab^R software to solve the Eigenvalue problem consisting of 5,000 nodes and 5,000 pipes, which is close to the size of the WDN in the city of Mount Pearl in Newfoundland and Labrador, the time required for the Eigenvalue problem is just 130 seconds, and calculating component only takes 430 seconds.

However, for multiple breaks, it is challenging to compare ACs. First, the number of computations increases significantly since many more sets of pipes are to be considered when the size of minimum cut-sets (i.e., number of pipes in the minimum cut-set) is large. For example, if finding the minimum cut-sets containing one pipe break requires m Eigenvalue problems to be solved, approximately m(m-1)/2 Eigenvalue problems need to be solved to determine all the minimum cut-sets containing two simultaneous pipe breaks. Second, a combination of breaks can lead to a ‘noisy’ situation, in which both the disconnection and reduction of redundancy may occur. Once this ‘noise’ happens, the ΔAC may decrease (e.g., E_2.3 in Table 2) or increase (e.g., E_2.1 in Table 2), depending on the network structure. If ΔAC decreases, it may fail to recognize the disconnection. This is further demonstrated below through application of the hypothetical network in Figure 2.

Table 4 presents the ACs for all possible minimum cut-sets of the network shown in Figure 2. In Table 4, minimum cut-set E_2.3 leads to disconnection of node 7; however, the change in AC is negative. Thus, the ΔAC-based method would fail to identify E_2.3. This phenomenon is termed herein as ‘noise’. The reason for the negative ΔAC is that the increase of AC due to disconnection of node 7 is less than the decrease of AC due to loss of redundancy.

Note that all of the pipes within the set of a minimum cut-set have to break simultaneously to cause disconnection of the network or to increase the AC. Removal of only one pipe from the set does not lead to disconnection or an increase in AC. Thus, the AC of a network with removal of a pipe from the set of a minimum cut-set is always lower than the AC of the network with removal of all pipes in the minimum cut-set. This characteristic can be used to eliminate the noise, as discussed below.

To implement this, when ΔAC decreases with a set of b breaks, the AC of the network is calculated with removal of each of the pipes within the set, i.e., AC_u* for removing u^th pipe (u = [1:b]). If the largest AC_u* is less than the AC with removal of the full set of pipes, then disconnection occurs. For example, removal of the set of pipes 6–7 and 6–8 causes a negative ΔAC value in Table 4, with an AC of 0.1823. The AC of the network with the break of pipes 6–8 and 6–7 (AC₁* and AC₂*) are 0.1341 and 0.1672, respectively. These two values are lower than the AC of the event E_2.3 (0.1823). Therefore, the set of pipes 6–7 and 7–8 is a minimum cut-set that leads to disconnection. In this manner, the noise removal is applied to the network (Figure 2) and the minimum cut-sets of the network based on the change in AC are successfully determined and tabulated in Table 4.

The exact solution of the network disconnection probability can be obtained theoretically by rigorously examining the minimum cut-sets using FTA, discussed above. However, this process requires tedious and complex computations for a large-scale network. Therefore, a practical approach is required, using assumptions to overcome the difficulties. This section develops a framework to estimate network disconnection probability based on the change of AC. It was revealed earlier in this paper that a single event-based failure probability provides a reasonable approximation of the system failure probability (i.e., ⁠). Both single event-based and multiple event-based failure probabilities are considered here for the AC-based reliability assessment. For the failure probability of the pipe components, a constant failure rate-based model, a failure function (i.e., exponential function) and Monte Carlo simulation (MCS) are considered.

Figure 5 illustrates the detailed procedure of of calculating system failure probability considering rigorous multiple events (i.e., minimum cut-sets). As discussed earlier, ‘noise’ may appear in the failure probability assessment for minimum cut-set containing multiple pipes. Thus, there can be some disconnection events with negative ΔAC. A sub-algorithm (Figure 5) discussed in the section ‘AC for multiple pipe breaks’ can be applied to avoid the noise problem. For calculation of failure probability of the components, application of a Monte Carlo (MC) simulation is used.

The methods discussed above are applied to the network presented in Figure 2 through development of codes using Matlab^R software. The calculated failure probabilities are compared in Figure 6. For the failure function, an equivalent exponential model is considered for illustration. The failure probability based on rigorous investigation of the network using FTA (without the use of AC) is also calculated and included in the figure. Among AC-based methods, the approximate failure probabilities calculated using a Poisson process-based and exponential component failure model are the same in Figure 6, since equivalent reliability models are used for the components. In the developed framework, different reliability models can be used (e.g., Weibull or lognormal distribution) instead of an exponential model, if the distribution is known.

The MC simulation conducted using 10,000 trials each time provides multiple event-based failure probabilities, which is very close to the failure probabilities calculated using single event-based approximation. Note that the MC simulation without the ‘noise’ removal sub-algorithm fails to predict the failure probability (Figure 6).

In Figure 6, the failure probability calculated using the FTA and AC methods is not significantly different. The network disconnection probability reaches close to 100% after 26 months, according to the rigorous FTA solution. The AC-based method with reliability algorithms predicts the failure probability as 97% (after 26 months).

The developed method is applied to the network in the city of Mount Pearl, which is a community with a population of approximately 25,000. The water main system contains 130 km of pipe network (see schematic shown in Figure 7). Thus, on average, 192 people are served by each kilometre of water main, which is comparable to common WDNs in the USA and Canada, which serve 164 people per kilometre (Folkman 2012). Diameters of the pipes in the city range from 150 to 600 mm. Water is bought from St John's – a neighbour city – to two water tanks located at the north (S1) and south-west (S2) parts of the city. The WDS to support the entire city is based on gravity flow. The locations of the sources are ignored in this study, for simplification. However, they could be useful for further study, which defines system failure as the disconnection of the source to nodes or reachability of the network. A sample of a raw database for the network is presented in Table 5. The table is included to show the typical WDN data that can be used for the AC-based method. After reorganizing the database, it is found that the WDN of the city of Mount Pearl contains 4,848 nodes and 5,046 pipes (Table 5).

This pipe system generally comprises ductile iron (91%), cast iron pipe (5%) and other materials (4%). Based on the annual water main break records of the city, the annual break rate is 6.931 breaks/year/100 km. This break rate is comparable to the average break rate of 6.77 breaks/year/100 km reported in Folkman (2012). It is understood that the break rate based on limited records is not sufficient for failure assessment, but is acceptable for the purpose of illustration.

Phan et al. (2017) calculated different parameters used in complex network analysis to assess the robustness and redundancy of the network for the WDN of the city. Yazdani & Jeffrey (2011a) provided a summary of the parameters used to assess the redundancy and robustness of networks. The parameters calculated for the network in the city of Mount Pearl are provided in Table 6, and are compared with values for different other cities, as reported in Yazdani & Jeffrey (2011a). In Table 6, the parameters for the city of Mount Pearl are mostly within the ranges of those for the other cities, indicating that the redundancy, connectivity and robustness of the city network are similar to those for other cities reported in Yazdani & Jeffrey (2011a). The redundancy, connectivity and robustness parameters of the Mount Pearl network range from the average to lower bound values of the parameters in the networks reported in Yazdani & Jeffrey (2011a). The low well-connectivity can be observed since the network contains high betweenness pipes, the removal of which could lead to the separation of the network.

For identification of critical pipes using AC, the pipes can be ranked according to the change in AC (ΔAC) with and without removal of a pipe from the network. Sample results of ranking of the pipes in the city of Mount Pearl's WDN are presented in Table 7. The histogram of the ΔAC is presented in Figure 8. According to Table 7, there are 2,061 out of 5,046 pipes belonging to Group 1 that directly lead to disconnection, and the remaining pipes belonging to Group 2 cause a reduction of redundancy. From Figure 8, it can be seen that the ΔAC generally ranges from −2.5 × 10⁻⁶ to 2.5 × 10⁻⁶ with some outliers that have significantly high positive values of up to 40 × 10⁻⁵. This sudden jump in ΔAC marks the most critical pipes, the failures of which would lead to an overall structural change in the network (i.e., disconnection on a large scale). Group 2 does not contain such outliers. Even though Group 2 has no outliers, it is helpful to understand the reduction of redundancy on a macro scale. To investigate the groups of pipes further, a set of the top 50 ranked pipes from Group 1 is analysed in more detail. The most important pipes of Group 2 (first 100 ranked pipes) have also been analysed, as illustrated in Figure 9.

The critical pipes in the network are also identified using the shortest path (SP) method for comparison. In the SP method, the shortest path to all pairs of nodes within the network is investigated. The method is thus computationally more demanding than the AC-based method. A pipe component appearing in the highest number of the shortest path is considered to be most critical, since water is expected to flow through this pipe component to a maximum number of destinations. The pipes are therefore ranked according to the number of their appearances on the shortest paths. The pipes with higher rank are considered to be more critical. Figure 10 shows the top 100 highest ranked pipes (thick solid lines) in the city of Mount Pearl's network. As seen in the figure, the critical pipes connect the northern and southern communities. The highest ranked pipe is the one laid between the Southern community, 1, and Northern community, 2 (Figure 10). Note that the sub-communities are not disconnected with removal of the pipe, since there are several other paths (redundancy) to connect the two sub-communities. An alternative path is shown as bold black lines in Figure 10. Thus, the SP method provides information for the important pipes (critical pipes), which may or may not lead to the separation of part(s) of the network. The method cannot be applied to identify the pipes that may lead to network disconnections.

It can be seen that the top ranked pipes based on the ΔAC (Figure 9) matched well with the shortest path results presented in Figure 10. Thus, the ΔAC could effectively classify the critical pipes in Group 1 and Group 2. The ranked ΔAC table can also be used to identify the alternate path of connecting two points, which cannot be obtained from the shortest path method.

Disconnection probability of the city of the Mount Pearl WDN is analysed using the methods discussed above. The results are presented in Table 8 and Figure 11. Time periods of 1, 2, 6 and 12 months are used in the analysis. From Table 8, it can be seen that the P_Br.av of the network is significantly low compared with the example in Figure 2. Thus, the calculated failure probabilities using the single event-based approach and the multiple event-based approach are almost the same in Figure 11.

In an existing WDS, pipe breaks causing isolation of part of the system should be avoided, to provide uninterrupted service to the dwellers. Studying the disconnection probability of WDS is therefore important for optimizing repair/maintenance prioritization planning. A pipe or combination of pipes causing network isolation can be identified using the minimum cut-sets method. In the conventional minimum cut-set method, pipes causing system failure (i.e., isolation) are rigorously examined to determine a combination of the minimum number of components' failure leading to the system failure. The process of finding minimum cut-sets is very complex and requires extensive computation. This paper presents a method of finding minimum cut-sets using AC for complex network analysis. The AC-based approaches reduced the amount of computation required compared to the existing methods, including the graph theory used in Yannopoulos & Spiliotis (2013). The AC is a network parameter which is determined by solving Eigenvalue problems that avoids counting the paths, as described in Yannopoulos & Spiliotis (2013). The decrease of AC due to a pipe break indicates a reduction of redundancy and the increase of AC indicates disconnection (isolation) of parts of the network. For the events with multiple pipe breaks, some breaks might cause an increase in AC while others might cause a decrease in AC, resulting in a ‘noisy’ situation. A methodology is developed to eliminate the ‘noise’ for multiple pipe breaks through scrutinizing the pipes in the minimum cut-sets. A failure probability estimation framework is developed using the AC-based minimum cut-sets.

The proposed method employs removal of pipes one by one from the network and subsequent estimation of the change in AC (ΔAC) for estimating the network failure probability and ranking pipes within the network according to their importance level. Based on these steps, the critical pipes in the network can be identified. The suitability of the proposed method is demonstrated through application, first to a simple hypothetical network and then to a medium-sized real WDS. The study reveals that the single event-based approximate failure probability can reasonably be used for system probability assessment, saving extensive computational time. The critical and high betweenness pipes identified using the AC-based method are validated through comparison with the results of the SP method. The SP method is a distance-related measurement in CNA, which is useful for identifying high betweenness pipes or nodes (Newman 2010). However, the SP method cannot be used for identification of network isolation.

The proposed reliability model considers the probability of disconnection only. Hydraulic availability of the demand nodes is not considered. Thus, lower bound values of the system failure probability are obtained. The developed model examines constant annual break rate-based component failure functions.

The financial support for this research has been provided by the Natural Sciences and Engineering Research Council of Canada (NSERC) through its Collaborative Research and Development Grants and the city of Mount Pearl in the province of Newfoundland and Labrador. The city of Mount Pearl provided necessary information regarding their WDN along with the past water main break records. The comments from anonymous reviewers are appreciated.