## Abstract

Unexpected pipe breaks in municipal water distribution systems may cause isolation of parts of the network or reduction of redundancy, leading to reduced system reliability. While a network with less redundancy implies less tolerance to further breaks, the isolation of nodes explicitly indicates unavailability of the system to service the nodes. This paper presents a method of measuring these topological changes using algebraic connectivity (*AC*). *AC* is a parameter that can be used to assess robustness and redundancy of a network. The changes in *AC* associated with pipe breaks are compared with the *AC* of intact networks to assess whether the removal of the pipe causes reduction of redundancy or isolation in the network. An *AC* of 1.5625 × 10^{−5} is calculated for an intake of a medium-sized water distribution network (WDN). The fluctuation in *AC* is used to assess the criticality of each pipe segment to the overall structure of the network. This study also evaluates the failure probability of the WDN, assuming that the network failure probability is equivalent to the probability of isolation of parts of the system due to pipe breaks. The breaks leading to the failure are identified using the method of the minimum cut-sets.

## INTRODUCTION

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.

## RELIABILITY WITH MINIMUM CUT-SETS

*E*. The probability of system failure can be determined using the minimum cut-set approach (Tung 1985; Yannopoulos & Spiliotis 2013). The minimum cut-set is a combination of a minimum number of component failures that lead to system failure (i.e., disconnection, in the current study). If

*E*is an event of system failure due to a set of

_{k}*k*pipes,

*k*ranges from 1 to m-1 where

*m*is the number of pipes in the network, the relationship between event

*E*and events

*E*can be written as: Because the events

_{k}*E*are mutually exclusive, then: where is the probability of system failure and is the probability of event

_{k}*E*to occur.

_{k}*pk*is defined as the number of minimum cut-sets consisting of

*k*pipes in the network, and event

*E*is the union of

_{k}*pk*events corresponding to

*pk*minimum cut-sets: is the event of the

*pd*minimum cut-set to occur, where

^{th}*pd*ranges from 1 to

*pk*. The relationship of system failure and the event of minimum cut-sets occurring is provided in the fault tree analysis (FTA) diagram shown in Figure 1.

*i*and node

*j*(from now on, written as pipe

*ij*) can be found as follows: where is the average annual break rate in the WDN, is total length of pipes in the network, is length of pipe

*ij*and

*λ*is break rate of pipe

_{ij}*ij*.

*ij*at time

*t*, , is the probability of a pipe to function at a desired level within the period of time [0:

*t*], where: Thus, For the hypothetical network in Figure 2, the average break per year (

*Br*) is randomly chosen as three breaks per year. From Equations (9) and (10), the failure probability of each pipe within 1 month (

*t*= 1/12) is calculated and given in Table 1. Consequently, the network disconnection probability is found as 0.063 with the details of calculating process given in Table 2.

*E*(empty) and

_{5}*E*(empty) in Table 2 indicate that there are no minimum cut-sets with five and 13 pipes, respectively.

_{13}Pipe | Length | λ_{ij} | P_{ij}(t)^{a} |
---|---|---|---|

1–2 | 1.0 | 0.169014 | 0.014085 |

1–3 | 0.5 | 0.084507 | 0.007042 |

1–5 | 1.5 | 0.253521 | 0.021127 |

2–4 | 0.75 | 0.126761 | 0.010563 |

2–5 | 2.5 | 0.422535 | 0.035211 |

3–4 | 2.0 | 0.338028 | 0.028169 |

4–5 | 1.75 | 0.295775 | 0.024648 |

5–6 | 2.5 | 0.422535 | 0.035211 |

6–7 | 2.0 | 0.338028 | 0.028169 |

6–8 | 0.5 | 0.084507 | 0.007042 |

7–8 | 0.75 | 0.126761 | 0.010563 |

8–9 | 0.5 | 0.084507 | 0.007042 |

9–10 | 1.5 | 0.253521 | 0.021127 |

Pipe | Length | λ_{ij} | P_{ij}(t)^{a} |
---|---|---|---|

1–2 | 1.0 | 0.169014 | 0.014085 |

1–3 | 0.5 | 0.084507 | 0.007042 |

1–5 | 1.5 | 0.253521 | 0.021127 |

2–4 | 0.75 | 0.126761 | 0.010563 |

2–5 | 2.5 | 0.422535 | 0.035211 |

3–4 | 2.0 | 0.338028 | 0.028169 |

4–5 | 1.75 | 0.295775 | 0.024648 |

5–6 | 2.5 | 0.422535 | 0.035211 |

6–7 | 2.0 | 0.338028 | 0.028169 |

6–8 | 0.5 | 0.084507 | 0.007042 |

7–8 | 0.75 | 0.126761 | 0.010563 |

8–9 | 0.5 | 0.084507 | 0.007042 |

9–10 | 1.5 | 0.253521 | 0.021127 |

^{a}*t* = 1 month.

Min. cut-sets contain k pipes E _{k} | pk | Min. cut-set (E) _{k.pd} | Pipes in the min. cut-set E (_{k.pd}E) _{k.pd.[pd.1]}; … ; E_{k.pd.[pd.k]} | P (E _{k.pd}) | P (E _{k}) |
---|---|---|---|---|---|

E _{1} | 3 | E._{1}_{1} | 5–6 | 0.035211 | 0.0622 |

E._{1}_{2} | 8–9 | 0.007042 | |||

E._{1}_{3} | 9–10 | 0.021127 | |||

E _{2} | 4 | E._{2}_{1} | 1–3; 3–4 | 0.000198 | 7.6849 × 10^{−4} |

E._{2}_{2} | 6–7; 6–8 | 0.000198 | |||

E._{2}_{3} | 6–7; 7–8 | 0.000297 | |||

E._{2}_{4} | 6–8; 7–8 | 7.439 × 10^{−5} | |||

E _{3} | 6 | E._{3}_{1} | 1–2; 1–3; 1–5 | 2.0955 × 10^{−6} | 4.3219 × 10^{−5} |

E._{3}_{2} | 1–2; 1–5; 3–4 | 8.3820 × 10^{−6} | |||

E._{3}_{3} | 1–2; 2–4; 2–5 | 5.2387 × 10^{−6} | |||

E._{3}_{4} | 1–3; 2–4; 4–5 | 1.8336 × 10^{−6} | |||

E._{3}_{5} | 1–5; 2–5; 4–5 | 1.8336 × 10^{−6} | |||

E._{3}_{6} | 2–4; 3–4; 4–5 | 7.3342 × 10^{−6} | |||

E _{4} | 5 | E._{4}_{1} | 1–2; 1–3; 2–5; 4–5 | 8.6082 × 10^{−8} | 7.8458 × 10^{−7} |

E._{4}_{2} | 1–2; 1–5; 2–4; 4–5 | 7.7474 × 10^{−8} | |||

E._{4}_{3} | 1–2; 2–5; 3–4; 4–5 | 3.4433 × 10^{−7} | |||

E._{4}_{4} | 1–3; 1–5; 2–4; 2–5 | 5.5339 × 10^{−8} | |||

E._{4}_{5} | 1–5; 2–4; 2–5; 3–4 | 2.2136 × 10^{−7} | |||

E (empty) _{5} | 0 | – | – | 0 | |

… | |||||

E (empty) _{13} | 0 | – | – | 0 | |

Sum: | 0.0630 |

Min. cut-sets contain k pipes E _{k} | pk | Min. cut-set (E) _{k.pd} | Pipes in the min. cut-set E (_{k.pd}E) _{k.pd.[pd.1]}; … ; E_{k.pd.[pd.k]} | P (E _{k.pd}) | P (E _{k}) |
---|---|---|---|---|---|

E _{1} | 3 | E._{1}_{1} | 5–6 | 0.035211 | 0.0622 |

E._{1}_{2} | 8–9 | 0.007042 | |||

E._{1}_{3} | 9–10 | 0.021127 | |||

E _{2} | 4 | E._{2}_{1} | 1–3; 3–4 | 0.000198 | 7.6849 × 10^{−4} |

E._{2}_{2} | 6–7; 6–8 | 0.000198 | |||

E._{2}_{3} | 6–7; 7–8 | 0.000297 | |||

E._{2}_{4} | 6–8; 7–8 | 7.439 × 10^{−5} | |||

E _{3} | 6 | E._{3}_{1} | 1–2; 1–3; 1–5 | 2.0955 × 10^{−6} | 4.3219 × 10^{−5} |

E._{3}_{2} | 1–2; 1–5; 3–4 | 8.3820 × 10^{−6} | |||

E._{3}_{3} | 1–2; 2–4; 2–5 | 5.2387 × 10^{−6} | |||

E._{3}_{4} | 1–3; 2–4; 4–5 | 1.8336 × 10^{−6} | |||

E._{3}_{5} | 1–5; 2–5; 4–5 | 1.8336 × 10^{−6} | |||

E._{3}_{6} | 2–4; 3–4; 4–5 | 7.3342 × 10^{−6} | |||

E _{4} | 5 | E._{4}_{1} | 1–2; 1–3; 2–5; 4–5 | 8.6082 × 10^{−8} | 7.8458 × 10^{−7} |

E._{4}_{2} | 1–2; 1–5; 2–4; 4–5 | 7.7474 × 10^{−8} | |||

E._{4}_{3} | 1–2; 2–5; 3–4; 4–5 | 3.4433 × 10^{−7} | |||

E._{4}_{4} | 1–3; 1–5; 2–4; 2–5 | 5.5339 × 10^{−8} | |||

E._{4}_{5} | 1–5; 2–4; 2–5; 3–4 | 2.2136 × 10^{−7} | |||

E (empty) _{5} | 0 | – | – | 0 | |

… | |||||

E (empty) _{13} | 0 | – | – | 0 | |

Sum: | 0.0630 |

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.

*h*

*>*

*k*). This is due to the fact that requires an intersectional condition for

*h*(i.e., larger than

*k*) simultaneous pipe breaks. Similarly, the intersectional condition indicates the fact that , since the failure probability of each component is less than 1. The difference of and is more significant when components in Equation (7) are relatively small. The average failure probability,

*P*, is useful to quantify this difference. The average failure probability can be obtained by taking the ratio of expected pipe breaks per total number of pipes in the network. This ratio is positively correlated with the breakage probability of the pipe components. Assuming that the pipe break is a Poisson process, the average failure probability within a period can be written as: where is the average annual break rate in the WDN and

_{Br.av}*m*is the number of pipes in the network.

*P(E*) significantly overwhelms the summation of the others, then network disconnection probability can be approximated by . That is: To investigate the relationship of and the difference between and , the network in Figure 2 has been investigated by changing the average break (

_{1})*Br*) within a fixed period of time, . Figure 3 compares the results. Figure 3(a) shows that is very close to . This is supported by Figure 3(b), in which the ratio between and is consistently larger than 0.89. This demonstrates that accounts for more than 89% of in all cases. It also implies that the approximation in Equation (13) can be more accurate with small . In other words, the smaller the , the closer the distance between and becomes. It is observed from Figure 3 that can be used to predict within an acceptable small value of . In the case of a WDN, containing thousands of pipes combining with relatively small

*Br*, the system is expected to be small. This leads to the approximation presented in Equation (13) being reasonable.

## ALGEBRAIC CONNECTIVITY

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.

*AC* for single pipe breaks

*AC*is a parameter used in graph theory to determine the strength of connection between the nodes in a network. Mathematically, it is defined as the second smallest Eigenvalue of the Laplacian matrix of the connected graph (Fiedler 1973). Municipal WDNs can be considered as graphs of connected networks, where a number of pipes connect the nodes at their intersections. Then, the graph of WDN can be described as

*G*

*=*

*G(V,P)*, where

*V*is a set of

*n*nodes (intersections) and

*P*is a set of

*m*pipes. An adjacent matrix

*A*of

*G*is used to describe the link between the nodes, where:

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

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

^{T}. The second smallest Eigenvalue of the Laplacian matrix is the

*AC*, which is greater than 0 if

*G*is a connected graph. The Eigenvalues of a network with

*n*nodes of connected graph are: .

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.

*AC*will be higher. For example, assume a network has two clusters: Cluster 1 includes nodes from 1 to

*i*-1 and Cluster 2 includes nodes from

*i*+ 1 to

*n*. The clusters of nodes are only linked by

*i*node. If links to this node are all broken, then the network Laplacian matrix will have the following form:

^{th}*AC*of the network is a combination of the isolated clusters. Fiedler (1973) mathematically proved that: where is the

*AC*of the connected network, is the

*AC*of the network after the disconnection with removal of nodes, and is the

*AC*of the network after the disconnection with removal of pipes.

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*and

_{1.2}*E*, shown in Table 2.

_{1.3}Sub-event | Removed pipe ID | AC | Change in AC ΔAC=AC-AC _{intact} | Type of network struct. change | Grouped as | Note |
---|---|---|---|---|---|---|

1.1 | 5–6 | 0.518806 | 0.32100 | Disconnection | Group 1 | E._{1}_{1} |

1.2 | 8–9 | 0.351227 | 0.15342 | Disconnection | Group 1 | E._{1}_{2} |

1.3 | 9–10 | 0.266187 | 0.06838 | Disconnection | Group 1 | E._{1}_{3} |

1.4 | 1–2 | 0.197626 | −0.00018 | Less redundancy | Group 2 | |

1.5 | 2–4 | 0.197626 | −0.00018 | Less redundancy | Group 2 | |

1.6 | 1–3 | 0.193938 | −0.00387 | Less redundancy | Group 2 | |

1.7 | 3–4 | 0.193938 | −0.00387 | Less redundancy | Group 2 | |

1.8 | 2–5 | 0.186393 | −0.01141 | Less redundancy | Group 2 | |

1.9 | 1–5 | 0.182328 | −0.01548 | Less redundancy | Group 2 | |

1.10 | 4–5 | 0.182328 | −0.01548 | Less redundancy | Group 2 | |

1.11 | 7–8 | 0.181990 | −0.01582 | Less redundancy | Group 2 | |

1.12 | 6–7 | 0.167151 | −0.03066 | Less redundancy | Group 2 | |

1.13 | 6–8 | 0.134125 | −0.06368 | Less redundancy | Group 2 |

Sub-event | Removed pipe ID | AC | Change in AC ΔAC=AC-AC _{intact} | Type of network struct. change | Grouped as | Note |
---|---|---|---|---|---|---|

1.1 | 5–6 | 0.518806 | 0.32100 | Disconnection | Group 1 | E._{1}_{1} |

1.2 | 8–9 | 0.351227 | 0.15342 | Disconnection | Group 1 | E._{1}_{2} |

1.3 | 9–10 | 0.266187 | 0.06838 | Disconnection | Group 1 | E._{1}_{3} |

1.4 | 1–2 | 0.197626 | −0.00018 | Less redundancy | Group 2 | |

1.5 | 2–4 | 0.197626 | −0.00018 | Less redundancy | Group 2 | |

1.6 | 1–3 | 0.193938 | −0.00387 | Less redundancy | Group 2 | |

1.7 | 3–4 | 0.193938 | −0.00387 | Less redundancy | Group 2 | |

1.8 | 2–5 | 0.186393 | −0.01141 | Less redundancy | Group 2 | |

1.9 | 1–5 | 0.182328 | −0.01548 | Less redundancy | Group 2 | |

1.10 | 4–5 | 0.182328 | −0.01548 | Less redundancy | Group 2 | |

1.11 | 7–8 | 0.181990 | −0.01582 | Less redundancy | Group 2 | |

1.12 | 6–7 | 0.167151 | −0.03066 | Less redundancy | Group 2 | |

1.13 | 6–8 | 0.134125 | −0.06368 | Less redundancy | Group 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*.

*AC*-based method to determine the minimum cut-set involving a single pipe break, as discussed above, is based on solving the Eigenvalue problem. This is basically different from the method of counting paths as described in Yannopoulos & Spiliotis (2013). To identify whether a single pipe or a set of pipes breaking is a minimum cut-set or not, the method reported in Yannopoulos & Spiliotis (2013) requires finding the associated connectivity matrix

*B*, as presented below: where

*AA*is the adjacent matrix

*A*(see Equation (14)) with the removal of the concerned pipe or set of pipes.

Since the computational cost of multiplying two matrices with size *n* × *n* is *O(n ^{3})* 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 (

^{4})*n*-2) ×

*O(n*=

^{2.375477})*O(n*. However, using the Eigenvalue problem, it can be reduced to

^{3.375477})*O(n*for each step of the interaction, for calculating only Eigenvalues (Flannery

^{2})*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

^{3})^{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.

*AC* for multiple pipe breaks

However, for multiple breaks, it is challenging to compare *AC*s. 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*in Table 2), depending on the network structure. If Δ

_{2.1}*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 *AC*s 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*. This phenomenon is termed herein as ‘noise’. The reason for the negative Δ

_{2.3}*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.

Min. cut-set (E_{k.pd}) | Pipes in the min. cut-set E_{k.pd} (E_{k.pd.[pd.1]}; … ; E_{k.pd.[pd.k]}) | AC | ΔAC |
---|---|---|---|

E_{1}._{1} | 5–6 | 0.5188 | 0.3210 |

E_{1}._{2} | 8–9 | 0.3512 | 0.1534 |

E_{1}._{3} | 9–10 | 0.2662 | 0.0684 |

E_{2}._{1} | 1–3; 3–4 | 0.2230 | 0.0252 |

E_{2}._{2} | 6–7; 6–8 | 0.5858 | 0.3880 |

E_{2}._{3} | 6–7; 7–8 | 0.1823 | -0.0155 |

E_{2}._{4} | 6–8; 7–8 | 0.4384 | 0.2406 |

E_{3}._{1} | 1–2; 1–3; 1–5 | 0.2051 | 0.0073 |

E_{3}._{2} | 1–2; 1–5; 3–4 | 0.2509 | 0.0531 |

E_{3}._{3} | 1–2; 2–4; 2–5 | 0.2104 | 0.0126 |

E_{3}._{4} | 1–3; 2–4; 4–5 | 0.2509 | 0.0531 |

E_{3}._{5} | 1–5; 2–5; 4–5 | 0.4131 | 0.2153 |

E_{3}._{6} | 2–4; 3–4; 4–5 | 0.2051 | 0.0073 |

E_{4}._{1} | 1–2; 1–3; 2–5; 4–5 | 0.3004 | 0.1026 |

E_{4}._{2} | 1–2; 1–5; 2–4; 4–5 | 0.3004 | 0.1026 |

E_{4}._{3} | 1–2; 2–5; 3–4; 4–5 | 0.2137 | 0.0159 |

E_{4}._{4} | 1–3; 1–5; 2–4; 2–5 | 0.2137 | 0.0159 |

E_{4}._{5} | 1–5; 2–4; 2–5; 3–4 | 0.3004 | 0.1026 |

Min. cut-set (E_{k.pd}) | Pipes in the min. cut-set E_{k.pd} (E_{k.pd.[pd.1]}; … ; E_{k.pd.[pd.k]}) | AC | ΔAC |
---|---|---|---|

E_{1}._{1} | 5–6 | 0.5188 | 0.3210 |

E_{1}._{2} | 8–9 | 0.3512 | 0.1534 |

E_{1}._{3} | 9–10 | 0.2662 | 0.0684 |

E_{2}._{1} | 1–3; 3–4 | 0.2230 | 0.0252 |

E_{2}._{2} | 6–7; 6–8 | 0.5858 | 0.3880 |

E_{2}._{3} | 6–7; 7–8 | 0.1823 | -0.0155 |

E_{2}._{4} | 6–8; 7–8 | 0.4384 | 0.2406 |

E_{3}._{1} | 1–2; 1–3; 1–5 | 0.2051 | 0.0073 |

E_{3}._{2} | 1–2; 1–5; 3–4 | 0.2509 | 0.0531 |

E_{3}._{3} | 1–2; 2–4; 2–5 | 0.2104 | 0.0126 |

E_{3}._{4} | 1–3; 2–4; 4–5 | 0.2509 | 0.0531 |

E_{3}._{5} | 1–5; 2–5; 4–5 | 0.4131 | 0.2153 |

E_{3}._{6} | 2–4; 3–4; 4–5 | 0.2051 | 0.0073 |

E_{4}._{1} | 1–2; 1–3; 2–5; 4–5 | 0.3004 | 0.1026 |

E_{4}._{2} | 1–2; 1–5; 2–4; 4–5 | 0.3004 | 0.1026 |

E_{4}._{3} | 1–2; 2–5; 3–4; 4–5 | 0.2137 | 0.0159 |

E_{4}._{4} | 1–3; 1–5; 2–4; 2–5 | 0.2137 | 0.0159 |

E_{4}._{5} | 1–5; 2–4; 2–5; 3–4 | 0.3004 | 0.1026 |

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*pipe (

^{th}*u*= [1:

*b*]). If the largest

*AC*is less than the

_{u}**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

_{1}**AC*) are 0.1341 and 0.1672, respectively. These two values are lower than the

_{2}**AC*of the event

*E*(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

_{2.3}*AC*are successfully determined and tabulated in Table 4.

## RELIABILITY ASSESSMENT USING *AC*

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.

### Single event-based approximate failure probability

*pd*minimum cut-set containing only one pipe.

^{th}*P(E)*≈

*P (E*, as described in Equation (13), the failure probability of the system can be defined as:

_{1})*P(E)*≈

*P(E*as: A detailed failure probability estimation procedure using either Poisson process-based failure functions or any other failure functions is illustrated in Figure 4.

_{1})### Multiple event-based failure probability

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).

## A CASE STUDY OF THE CITY OF MOUNT PEARL

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).

Node ID | Shape | Pipe ID | Material | Diameter (mm) | POINT_X | POINT_Y |
---|---|---|---|---|---|---|

1 | Point | 1 | Ductile iron | 150 | 320991.62230 | 5264475.70150 |

2 | Point | 1 | Ductile iron | 150 | 321007.09150 | 5264498.97460 |

3 | Point | 2 | Ductile iron | 200 | 321048.28280 | 5265709.24110 |

… | … | … | … | … | … | … |

8564 | Point | 9474 | DI Private (approx.) | 150 | 320423.51620 | 5263016.32110 |

Node ID | Shape | Pipe ID | Material | Diameter (mm) | POINT_X | POINT_Y |
---|---|---|---|---|---|---|

1 | Point | 1 | Ductile iron | 150 | 320991.62230 | 5264475.70150 |

2 | Point | 1 | Ductile iron | 150 | 321007.09150 | 5264498.97460 |

3 | Point | 2 | Ductile iron | 200 | 321048.28280 | 5265709.24110 |

… | … | … | … | … | … | … |

8564 | Point | 9474 | DI Private (approx.) | 150 | 320423.51620 | 5263016.32110 |

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.

Parameter | Equation | Calculated value | Reference values^{a} |
---|---|---|---|

Total length | 129.837 (km) | ||

Number of pipe | – | 5.046 | 769–3,065 |

Number of node | – | 4.848 | 755–2,799 |

Link-per-node | 1.041 | 1.01–1.10 | |

Average node degree | 2.082 | 2.04–2.23 | |

Link density | 4.29 × 10^{−4} | 7.83 × 10^{−4}–2.7 × 10^{−3} | |

Independent loop | 197 | – | |

Meshness coefficient | 0.0203 | 9.97 × 10^{−3}–5.86 × 10^{−2} | |

Threshold for random removal of node | 0.1770 | 0.22–0.42 | |

Route factor | 1.7560 | 1.45–1.67 | |

Characteristic path length | 88.378 | 25.94–51.44 | |

Algebraic connectivity | – | 1.5625 × 10^{−5} | 6.09 × 10^{−5}–2.43 × 10^{−4} |

Spectra gap | – | 2.55 × 10^{−2} | 9.08 × 10^{−3}–7.27 × 10^{−2} |

Parameter | Equation | Calculated value | Reference values^{a} |
---|---|---|---|

Total length | 129.837 (km) | ||

Number of pipe | – | 5.046 | 769–3,065 |

Number of node | – | 4.848 | 755–2,799 |

Link-per-node | 1.041 | 1.01–1.10 | |

Average node degree | 2.082 | 2.04–2.23 | |

Link density | 4.29 × 10^{−4} | 7.83 × 10^{−4}–2.7 × 10^{−3} | |

Independent loop | 197 | – | |

Meshness coefficient | 0.0203 | 9.97 × 10^{−3}–5.86 × 10^{−2} | |

Threshold for random removal of node | 0.1770 | 0.22–0.42 | |

Route factor | 1.7560 | 1.45–1.67 | |

Characteristic path length | 88.378 | 25.94–51.44 | |

Algebraic connectivity | – | 1.5625 × 10^{−5} | 6.09 × 10^{−5}–2.43 × 10^{−4} |

Spectra gap | – | 2.55 × 10^{−2} | 9.08 × 10^{−3}–7.27 × 10^{−2} |

^{a}From Yazdani & Jeffrey (2011a).

### Identification of the critical pipes

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^{−6} to 2.5 × 10^{−6} with some outliers that have significantly high positive values of up to 40 × 10^{−5}. 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.

Removed pipe ID | AC | Δ AC=AC-AC _{intact} | Type of network structural change | Grouped as |
---|---|---|---|---|

1734–1735 | 5.52 × 10^{−5} | 3.96 × 10^{−5} | Disconnection | Group 1 |

1734–3518 | 5.52 × 10^{−5} | 3.96 × 10^{−5} | Disconnection | Group 1 |

1733–3518 | 5.52 × 10^{−5} | 3.95 × 10^{−5} | Disconnection | Group 1 |

… | … | … | … | … |

2373–2631 | 1.21 × 10^{−5} | −3.56 × 10^{−6} | Less redundancy | Group 2 |

1655–2631 | 1.21 × 10^{−5} | −3.57 × 10^{−6} | Less redundancy | Group 2 |

1655–1656 | 1.21 × 10^{−5} | −3.57 × 10^{−6} | Less redundancy | Group 2 |

Removed pipe ID | AC | Δ AC=AC-AC _{intact} | Type of network structural change | Grouped as |
---|---|---|---|---|

1734–1735 | 5.52 × 10^{−5} | 3.96 × 10^{−5} | Disconnection | Group 1 |

1734–3518 | 5.52 × 10^{−5} | 3.96 × 10^{−5} | Disconnection | Group 1 |

1733–3518 | 5.52 × 10^{−5} | 3.95 × 10^{−5} | Disconnection | Group 1 |

… | … | … | … | … |

2373–2631 | 1.21 × 10^{−5} | −3.56 × 10^{−6} | Less redundancy | Group 2 |

1655–2631 | 1.21 × 10^{−5} | −3.57 × 10^{−6} | Less redundancy | Group 2 |

1655–1656 | 1.21 × 10^{−5} | −3.57 × 10^{−6} | Less redundancy | Group 2 |

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.

### Estimating the system disconnection probability

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.

Δt (month) | Average number of breaks | P _{Br.av} | P(E Δ_{1},t) single event based | P(E, Δt) multiple event based |
---|---|---|---|---|

1 | 0.716 | 1.486 × 10^{−4} | 0.243 | 0.229 |

2 | 1.518 | 2.973 × 10^{−4} | 0.427 | 0.436 |

6 | 4.479 | 8.918 × 10^{−4} | 0.812 | 0.814 |

12 | 8.834 | 17.836 × 10^{−4} | 0.964 | 0.973 |

Δt (month) | Average number of breaks | P _{Br.av} | P(E Δ_{1},t) single event based | P(E, Δt) multiple event based |
---|---|---|---|---|

1 | 0.716 | 1.486 × 10^{−4} | 0.243 | 0.229 |

2 | 1.518 | 2.973 × 10^{−4} | 0.427 | 0.436 |

6 | 4.479 | 8.918 × 10^{−4} | 0.812 | 0.814 |

12 | 8.834 | 17.836 × 10^{−4} | 0.964 | 0.973 |

## CONCLUSIONS

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.

## ACKNOWLEDGEMENTS

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.

arXiv preprint arXiv:1601.02155