## Abstract

Water distribution networks (WDNs) must keep a proper level of service under a wide range of operational conditions, and, in particular, the analysis of their resilience to pipe failures is essential to improve their design and management. WDNs can be regarded as large sparse planar graphs showing fractal and complex network properties. In this paper, the relationship linking the geometrical and topological features of a WDN to its resilience to the failure of a pipe is investigated. Some innovative indices have been borrowed from fractal geometry and complex network theory to study WDNs. Considering all possible network configurations obtained by suppressing one link, the proposed indices are used to quantify the impact of pipe failure on the system's resilience. This approach aims to identify critical links, in terms of resilience, with the help of topological metrics only, and without recourse to hydraulic simulations, which require complex calibration processes and come with a computational burden. It is concluded that the proposed procedure, which has been successfully tested on two real WDNs located in southern Italy, can provide valuable information to water utilities about which pipes have a significant role in network performance, thus helping in their design, planning and management.

## LIST OF SYMBOLS

*APL*average path length

*APL*_{(1/D)}inverse diameter-weighted average path length

*B*_{r}Bridge Ratio index

*C*number of total pipe failure combinations

*C**number of total pipe failure combinations that do not disconnect the network

*D*_{f}fractal dimension

*h**nodes design pressure [m]

*h*_{i}node hydraulic head [m]

*H*_{R}head of the

*j*-th reservoir [m]*i*node index

*I*_{r}resilience index

*k*average node-degree

*k*_{i}total number of connections of the

*i*-th node*l*pipe index

*L*_{TOT}total pipes length [km]

*m*total number of pipes

*m*_{d}number of pipes disconnecting the network

*n*total number of nodes

*n*_{n}total number of demand nodes

*n*_{R}total number of reservoirs

*N(r)*number of square boxes of dimension

*r**q*_{i}water demand at

*i*-th node [m^{3}/s]*Q*_{R}water flow entering through the

*R*-th reservoir [m^{3}/s]*q*link density

*r*dimension of square box

*R*reservoirs index

*WSN*water supply network

*λ*_{2}algebraic connectivity

## INTRODUCTION

Nowadays, improving the resilience of communities is one of the most important and universal societal issues. Different definitions of resilience are given in the literature, highlighting specific aspects based on the field of application (Holling 1973; Hamel & Välikangas 2003; Pickett *et al.* 2004; Folke 2006; Wieland & Wallenburg 2013).

Resilience is a typical feature of network systems where the redundancy in links, paths and loops allows systems to maintain and adapt their operational performance when some of their components fail or other unplanned and adverse conditions arise (Laprie 2005; Strigini 2012).

In relation to communal network infrastructure (e.g. telecommunications, transport, public services and power grids) which continuously require renovation (owing to either rising demand, changes in user profiles or age), it is possible to measure resilience in terms of energy, i.e. the system capacity to exploit the available energy with minimum dissipation in ordinary operational conditions, or in terms of the system redundancy, that allows the level of service to users to be maintained notwithstanding unplanned operational conditions including loss of nodes/links caused by failures or intentional damage (Cohen *et al.* 2001; Estrada 2006).

In relation to water distribution networks (WDNs), resilience is linked to the network geometry and topology based on the premise that a densely looped layout offers a system redundancies which are capable of overcoming operational perturbations (Mays 2000). These operational perturbations can range from variable water demand (Gargano & Pianese 2000), to breakages and leakage caused by deterioration of pipes and pumping units (Walski & Pelliccia 1982), to natural or man-made disasters (e.g. earthquakes, ﬂoods, vandalism) (Zohra *et al.* 2012). Furthermore, unplanned urban development without suitable design can lead to the modification of the topology of a WDN by simply adding nodes and links in order to satisfy increased water demand. This can have unintended consequences for the system resilience.

The resilience of WDNs depends essentially on three aspects:

- (a)
network geometry;

- (b)
topological redundancy; and

- (c)
energy redundancy.

The network geometry deals with the layout and extent of the network and the physical dimensions of its links and nodes (Csanyi & Szendrői 2004). Topological redundancy is related to the presence of independent alternative paths (usually looped), which connect the source with demand nodes, along which water can flow to satisfy supply requirements during interruption or failure of links (Goulter & Coals 1986). Energy redundancy is related to both topological redundancy (i.e. more paths imply more pipes to convey flow, thus reducing energy losses) and to geometrical redundancy (i.e. the use of conduit diameters, larger than those strictly needed to satisfy the required level of service for the users in terms of nodal pressure and water demand, provides additional capacity to respond to unplanned service conditions).

As a result of these multi-dependent factors, there is no single established approach or method to assign and to quantify the resilience of a WDN. The factors which are crucial to a network's resilience include the choice of pipe materials, pipe diameters and the levels of topological and energy redundancy which can be assessed through an in-depth analysis of pipe lengths, topological layout and loop number.

In this regard, it is clear that the resilience depends on the connectivity of the network and on the location of each single element (e.g. pipes, pumps, valves) and also on the complex network geometry produced by traditional design criteria, i.e. placing looped pipes under nearly every street. These complex geometries and topologies require innovative approaches for the analysis and management of a WDN.

Several concepts from graph theory (Konig 1936), fractal geometry (Mandelbrot 1982), social network theory (Freeman 2005) and, more recently, complex network theory (Watts & Strogatz 1998; Barabasi & Albert 1999) have been applied to better analyze WDNs. This has led to the development of mathematical approaches and operational procedures that use innovative metrics and algorithms to better understand and describe, and then optimise and control, complex WDNs. In fact, many water supply systems consisting of up to tens of thousands of nodes and hundreds of looped paths can be considered as complex networks (Boccaletti *et al.* 2006). Recently, the fractal theory (Kowalski *et al.* 2014) and topological metrics (Yazdani & Jeffrey 2010; Gutiérrez-Perez *et al.* 2013; Herrera *et al.* 2016; Di Nardo *et al.* 2016a) were also used to analyse global resilience of a WDN.

Because the WDN resilience depends on different aspects, in this paper, attention is mainly focused on using innovative metrics to characterise the relationship between geometrical, topological and energy redundancy, in order to better assess and measure the resilience of WDNs. Specifically, the relationship between energy resilience and average path length (APL), used as a surrogate for a network topological measure, is investigated. Further, the feasibility of identifying critical links with the help of topological metrics only, and without recourse to hydraulic simulations, which require complex calibration procedures and come with a computational burden, is investigated. The proposed procedure allows identification, *a priori*, of the pipes on which the attention and the maintenance efforts should be focused to preserve network resilience.

The effectiveness of the procedure is tested on two real, medium-sized distribution networks serving two towns located near the city of Naples (Italy), namely Parete and Villaricca (Di Nardo & Di Natale 2011).

## METHODS AND METRICS

The following section briefly describes the geometrical, topological and energy metrics used in this paper. Their properties and how they can express and measure global network redundancy is also described hereinafter. The adopted combinatorial methodology to analyse the vulnerability of a network to pipe failures is then described. This procedure is aimed at identifying a possible relationship between WDN topology and its resilience.

### Geometrical metrics

*et al.*1992) developed in a MatLab

^{®}tool on the basis of the work of Minkowski–Bouligand, has been used to define the relation: where

*N(r)*is the number of square boxes of

*r*dimension necessary to cover the planar layout of the network, and

*D*is the fractal dimension, according to the following formulation: The self-similarity, and so the fractal nature of the spatial distribution of nodes and links, can be seen as an indicator of the low reachability of the system (Csanyi & Szendrői 2004), typical of spatial networks with strong geographical constraints, as opposite to small world networks (Boccaletti

_{f}*et al.*2006).

In Figure 1, an example of two simple networks is shown, to illustrate the relationship between fractal dimension *D _{f}* – computed with the box counting method from

*r*= 16 pixels to

*r*= 1 pixel – and network topological resilience.

In particular, the example networks have the same number of nodes but different numbers of links, network A being less connected than network B. As reported in Figure 1, the value of *D _{f}* of network B, equal to 1.547, is higher than the

*D*of network A (1.381), indicating that the less connected network also has less 2D Euclidean space covering. So, the fractal dimension can be used as a surrogate of topological resilience, measuring, at the same time, topological redundancy and space covering.

_{f}### Topological metrics

In recent years, in order to describe network behaviour and to characterise some of their general properties, innovative topological metrics have been proposed in the literature on complex networks theory (Boccaletti *et al.* 2006). Interesting applications to WDNs have confirmed their suitability for the investigation of vulnerability (Yazdani & Jeffrey 2010; Yazdani & Jeffrey 2011) and water network partitioning (Herrera *et al.* 2012; Di Nardo *et al.* 2015, 2016b, 2017).

The following metrics are used in this paper:

- (1)
the link density,

*q*, which expresses the ratio between the total number of network edges and the number of edges of a globally coupled network with the same number*n*of nodes, thus providing a measurement of network redundancy; - (2)
the average node-degree,

*k*, which is the average of the degrees*k*of all nodes (with_{i}*k*being the total number of connections of the generic_{i}*i*-th node to other nodes), which expresses how nodes are interconnected, thus measuring the topological redundancy of a network; - (3)
the

*APL*, which is the average number of steps along the shortest paths between all possible pairs of nodes in the network, which determines the average degree of separation between any pair of nodes (high values of*APL*indicate a much fragmented network (Guest & Namey 2014)); and - (4)
the algebraic connectivity,

*λ*, i.e. the second smallest eigenvalue of the Laplacian of the graph adjacency matrix (Fiedler, 1973), which quantifies the strength of network connections (a high value of algebraic connectivity indicates the tolerance of the network to link faults and, consequently, its resilience against efforts to cut it into parts (Yazdani & Jeffrey 2010))._{2}

These indices are used generally to analyse both the redundancy and the resilience of a complex network (Yazdani & Jeffrey 2010).

It is important to highlight that, like many other real networks (i.e. ties between individuals in social networks, uneven fluxes in metabolic reaction pathways, different capabilities of transmitting electrical signals in neural networks, unequal traffic on the Internet (Boccaletti *et al.* 2006)), WDNs exhibit large heterogeneity in the intensity of the connections between nodes. In this regard, WDNs are better studied as weighted networks, in which each link has a numerical value measuring the ‘strength of the connection’. Consequently, a weighted average path length, *APL _{1/D}*, is introduced, adopting the inverse of pipe diameter as weight, in order to take into account one of the most important hydraulic characteristics of the links between nodes. In this way, the shortest path between each pair of nodes is defined as the minimum sum of the inverse of the diameters

*D*of the pipes linking them, in order to identify the path with minimum resistance to water flow.

### Failure metrics

As reported in Creaco *et al.* (2016), failure metrics in WDN can be divided into two main categories: pressure head/energy related indices (Gessler & Walski 1985; Todini 2000; Prasad *et al.* 2003), and flow path related indices (Tanyimboh & Templeman 2000; Tanyimboh *et al.* 2011). Both categories of indices aim to measure the WDN global behaviour under local failures of one or more components or unplanned changes.

In this paper two concepts are used to express WDN resilience to pipe failure, namely:

- (1)
how much the network preserves the connectivity (flow path related index); and

- (2)
how much the network preserves a pressure head surplus (pressure head/energy related index).

*m*(the value of the corresponding

_{d}*APL*tends to infinite) and the total number of pipes,

_{1/D}*m*.

*I*, which is a measure of the available surplus of energy: where

_{r}*n*is the number of demand nodes,

_{n}*n*the number of reservoirs,

_{R}*q*and

_{i}*h*the demand and the head of the

_{i}*i*-th node,

*Q*and

_{R}*H*the discharge and the pressure head of the generic

_{R}*R*-th source point, and

*h**the design pressure head of the network.

### Combinatorial analysis of pipe failures

In order to evaluate the impact of pipe failures on network resilience, a combinatorial analysis of all possible network layouts, *C*, obtained by interrupting one pipe (Greco *et al.* 2012) was carried out. The hydraulic simulation of every configuration was carried out using Demand Driven Analysis (Todini 2000) under peak conditions. The procedure consisted of the following steps:

- 1.
Close a pipe

*l*. - 2.
Evaluate

*APL*._{1/D} - 3.
Carry out network hydraulic simulation and evaluate the resilience index

*I*._{r} - 4.
Repeat the procedure, opening the pipe

*l*and closing the pipe*l**+**1*. - 5.
Stop the procedure when all possible network layouts

*C*have been investigated.

At the end of the procedure, the topological and energy resilience for all combinations were compared, in order to identify similar trends and so to establish a possible relationship which could help to identify, *a priori*, the worst single pipe failures, without carrying out hydraulic simulations.

It is worth highlighting that, in this study, the combinatorial analysis and hydraulic simulations to compute Todini's index were carried out only to find a possible relationship between weighted *APL _{1/D}* and

*I*. Clearly, thanks to the identified relationship, operators can identify,

_{r}*a priori*, and without any hydraulic simulation, but only with the calculation of weighted

*APL*, the pipes on which attention and maintenance efforts should be focused to best preserve network resilience.

_{1/D}## CASE STUDY

The proposed procedure was tested on two real, medium-sized WDNs, serving the towns of Villaricca and Parete, both located near Naples (Italy), with about 30,000 and 11,000 inhabitants, respectively (Di Nardo & Di Natale 2011). Figure 2 shows the layout of the two WDNs, while Table 1 summarises their main characteristics.

WDN . | Nodes . | Links . | Sources . | Total length . | Link density . | Average node-degree . | Average path length . | Algebraic connectivity . | Todini's resilience . |
---|---|---|---|---|---|---|---|---|---|

n [−] | m [−] | n [−] _{R} | L [km] _{TOT} | q [%] | k [−] | APL [−] | λ_{2} [−] | I [−] _{r} | |

Villaricca | 196 | 241 | 3 | 34.71 | 1.26 | 2.42 | 11.29 | 0.006 | 0.442 |

Parete | 182 | 282 | 2 | 32.44 | 1.67 | 3.05 | 8.80 | 0.021 | 0.351 |

WDN . | Nodes . | Links . | Sources . | Total length . | Link density . | Average node-degree . | Average path length . | Algebraic connectivity . | Todini's resilience . |
---|---|---|---|---|---|---|---|---|---|

n [−] | m [−] | n [−] _{R} | L [km] _{TOT} | q [%] | k [−] | APL [−] | λ_{2} [−] | I [−] _{r} | |

Villaricca | 196 | 241 | 3 | 34.71 | 1.26 | 2.42 | 11.29 | 0.006 | 0.442 |

Parete | 182 | 282 | 2 | 32.44 | 1.67 | 3.05 | 8.80 | 0.021 | 0.351 |

The comparison of the two networks sketched in Figure 2 shows that, although the WDNs have roughly the same total pipe length (about 30 km), they have layouts which are significantly different both topologically and geometrically.

The geometrical characteristics of the two networks (spatial shape and extension, pipe orientations, etc.) are very different and, clearly, they cannot be described exhaustively with only a visual analysis or Euclidean geometry and therefore require more sophisticated metrics. In this regard, the fractal dimension of the two networks was evaluated using the box-counting method on image files plotted at the same scale, with a number of pixels equal to 6357 × 4490 (Villaricca) and 2649 × 1871 (Parete). In Figure 3, the log–log plot shows the number of boxes *N(r)* of size *r* as a function of *r* for the two case studies. The linearity of the two curves (in log-log space) indicates that the networks exhibit some fractal behaviour, with a fractal dimension (i.e. the slope of the straight line in the log-log plot) equal to *D _{f}* = 1.348 for Villaricca and

*D*= 1.484 for Parete. In both cases, the smallest size of box-counting corresponds to the dimension of a single pixel (about 79.4 × 79.4 cm in real scale). The slope of the straight line has been evaluated in the range 10 <

_{f}*r*< 10

^{3}. The lower bound and the upper bound of such a range are close, respectively, to the minimum and maximum length of pipes. In other terms, with

*r*= 10 a box can include at most one pipe, while with

*r*= 10

^{3}a box can contain a set of network pipes including the pipe with the maximum length.

As indicated in Figure 3, the fractal dimension *D _{f}* for Parete is larger than that of Villaricca in the range 10 <

*r*< 10

^{3}. This result confirms some intuitive observations from visual analysis of system layouts, namely that the nodes of the network of Parete are more interconnected in all directions than those of Villaricca. However, the fractal dimension allows these geometrical differences to be quantified. A relationship exists between geometrical and topological features, as reported in Csanyi & Szendrői (2004). Indeed, the

*APL*in a fractal system is proportional to the number of nodes

*n*through the inverse of

*D*∼

_{f}, APL*n*. Thus, the estimated fractal dimensions are consistent with the values of

^{1/Df}*APL*, which for the network of Parete is lower than for Villaricca.

However, the fractal dimension does not catch all network characteristics. The other computed topological metrics confirmed the higher topological resilience of the Parete WDN compared to Villaricca. In fact, the Parete WDN exhibits higher values of *q, k* and *λ _{2}* and a lower value of

*APL*, and thus greater connectivity, and so it is expected a higher strength against efforts to cut it into parts.

Further interesting results can be found from the combinatorial analysis obtained by considering all the possible combinations *C* of a single pipe failure, with *C* = 241 for Villaricca and *C* = 282 for Parete.

The Bridge Ratio indices for the two WDNs were evaluated giving *B _{r}* = 0.245 for Villaricca and

*B*= 0.007 for Parete which confirmed that the Parete network is more resilient than that of Villaricca which suffers more disconnections.

_{r}The different metrics used in this study were analyzed to better understand their potential relationship with resilience to pipe failures. In particular, the link density and the average node-degree, although they are measures of network topological redundancy, undergo the same change after the failure of any single pipe; the spectral connectivity, that quantifies the strength of network connections, shows little sensitivity to single pipe failures. Conversely, the *APL* results were highly sensitive, suggesting further investigation of the possible relationship between the weighted *APL* and Todini's energy resilience would be of value.

So, a comparison was undertaken between the weighted average path length *APL _{1/D}* and the Todini resilience index

*I*, only for the layout combinations that do not lead to disconnection of the graph (respectively

_{r}*C**= 182 for Villaricca and

*C**= 280 for Parete). These results are plotted in Figures 4 and 5. Failures which disconnect the networks have been considered as the worst cases, but also as trivial solutions.

The ascending ordered values of *APL _{1/D}* for Villaricca and Parete are plotted in Figure 4. The

*x*-axis shows the percentage of the total number of pipes. The plot of Villaricca appears shorter, because about 24% of the pipe failures lead to disconnection of the network, which causes the

*APL*to have an infinite value. Conversely, only 0.7% of pipe failures cause disconnection of the network of Parete. With the same order of the layouts used in Figure 4, the values of

_{1/D}*I*are plotted in Figure 5.

_{r}From the two figures, it looks clear that the Parete WDN is more resilient than that of Villaricca. In fact, in the first case, about 70% of the failed-pipe layouts do not affect the original values of *APL _{1/D}* of the network, while for Villaricca significant variations of

*APL*occur for nearly 40% of the layouts. Furthermore, although in both cases about 30% of the combinations hardly worsen the energy resilience

_{1/D}*I*, it is clear that the energy redundancy of the network of Villaricca results in greater sensitivity to pipe failures. This confirms the indications given by the various metrics reported in Table 1.

_{r}In the right part of the graphs, the performances are significantly worsened from both a topological and energy point of view, showing an interesting relationship between *APL _{1/D}* and

*I*. Therefore, a preliminary identification of the pipe failures, which are crucial for the hydraulic performance of the network, can be achieved using only topological information. Such a result is not trivial, as some of these pipe failures do not imply disconnection of the network (easy to compute). It is therefore possible to identify, without time-consuming hydraulic simulations, those pipes on which maintenance efforts should be concentrated to reduce costs and to maintain resilience.

_{r}Finally, in Figure 2, the 10 most important pipes in terms of the *APL _{1/D}* for each network are highlighted in bold lines. This visualization allows better understanding of the effectiveness of the proposed procedure because, while some important pipes are closer to reservoirs, as expected, others are located far from the sources. Furthermore, Figure 2 shows that, without hydraulic simulations, but only using a topological metric such as

*APL*, it is possible to recognize, besides some important pipes, also the most critical paths (formed by consecutive pipes) for the water distribution system, thus providing valuable management information to water utilities.

_{1/D}## CONCLUSIONS

This paper presents a novel procedure to assess the resilience of a water distribution network to failure of a single pipe based on the use of fractal and topological metrics. The effectiveness of the proposed methodology was tested on two real, medium-sized, WDNs. The fractal analysis indicated that the geometrical shape of the planar layout of both networks met the formal conditions of fractal sets. This result was expected, as WDNs are geographically constrained, which implies that, as connections occur mainly between immediately neighbouring nodes, water flow may be significantly affected by the interruption of single links. The relationships between geometrical and topological metrics and between topological metrics and energy resilience were also investigated. To this aim, the *APL*, weighted with the inverse of pipe diameter, was introduced. The results of a combinatorial analysis of all possible single pipe failures showed that this novel metric easily allowed identification, without hydraulic simulations, of the most important pipes and crucial paths (composed of more pipes), the failure of which causes a significant decline of both the topological and hydraulic resilience of the network. The obtained relationship between topology and energy resilience provides water utilities with an effective and easy tool to improve WDN management.

This result represents a novelty compared to other studies on the global resilience of WDNs carried out by complex network metrics. In fact, the weighted topological metric adopted in this paper provides useful information, allowing the direct identification of pipes most likely affecting the energy resilience and, consequently, the hydraulic performance and the level of service offered to users. Further studies will investigate this relationship using other geometrically weighted topological metrics, in order to identify the hydraulic characteristics of pipes most suitable to be used as a proxy for network resilience. In addition, the possibility of incorporating the dependence of resilience on the probability of failure of a pipe (i.e. related to pipe material, age, etc.) will be investigated. Finally, the procedure will be tested on larger WDNs to further validate the results.

## REFERENCES

*.*

*Technical Report TREL-85-11. US Army Corps of Engineers' Waterways Experimentation Station, Vicksburg, MS*

*Urban Water II*(S. Mambretti (Politecnico di Milano, Italy) & C. A. Brebbia (Wessex Institute of Technology, UK), eds). Vol. 139, pp. 75–90, WIT Press, UK

*.*

*.*

Theorie der endlichen und unendlichen Graphen (Theory of finite and infinite graphs). Akad, Verlagsgesellschaft, Leipzig, Germany