- Email: [email protected]

Contents lists available at ScienceDirect

Environmental Modelling & Software journal homepage: www.elsevier.com/locate/envsoft

Resilience enhancing expansion strategies for water distribution systems: A network theory approach A. Yazdani a, R. Appiah Otoo b, P. Jeffrey a, * a b

Centre for Water Science, Cranﬁeld University, MK43 0AL, UK GIS Department, Ghana Water Co. Ltd., Accra, PO Box GP130, Ghana

a r t i c l e i n f o

a b s t r a c t

Article history: Received 22 May 2011 Received in revised form 26 July 2011 Accepted 26 July 2011 Available online 23 August 2011

Planners and engineers attempting to improve the resilience of water distribution systems face numerous challenges regarding the allocation and placement of redundancy so as to reduce the likelihood and impact of asset failures and take into consideration the growing demand for clean water, now and into the future. Water distribution systems may be represented as networks of multiple nodes (e.g. reservoirs, storage tanks and hydraulic junctions) interconnected by physical links (e.g. pipes) where the connectivity patterns of this network affects its reliability, efﬁciency and robustness to failures. In this paper we employ the link-node representation of water infrastructures and exploit a wide range of advanced and emerging network theory metrics and measurements to study the building blocks of the systems and quantify properties such as redundancy and fault tolerance, in order to establish relationships between structural features and performance of water distribution systems. We study the water distribution network of a growing city from a developing country and explore network expansion strategies that are aimed to secure and promote structural invulnerability, subject to design and budget constraints. 2011 Elsevier Ltd. All rights reserved.

Keywords: Water distribution Urban planning Graph theory Network analysis GIS Vulnerability Robustness System redundancy

1. Introduction Increasing water stress in many developing countries both endangers lives and restricts economic growth. Although levels of access to a piped water distribution are increasing at a global level, many of the developing world’s cities are served by old and poorly maintained networks with consequential problems in terms of both water quality and supply reliability (UNDP, 2006). The problem is compounded by the increasing frequency and scale of extreme natural events (CRED, 2009) and man-made catastrophes that cause major ﬂow disruptions. Like many other infrastructural systems, water distribution systems consist of multiple interconnected components, whose individual or simultaneous failure may have adverse consequences in terms of disruption to water services. Therefore, improving system reliability and reducing system susceptibility to damage and perturbation are prime concerns for system engineers and utility managers responsible for the design, operation and protection of the Water Distribution Networks (WDN). As the cities of developing countries expand

* Corresponding author. E-mail address: [email protected]ﬁeld.ac.uk (P. Jeffrey). 1364-8152/$ e see front matter 2011 Elsevier Ltd. All rights reserved. doi:10.1016/j.envsoft.2011.07.016

(often very rapidly) through urban migration, the expansion of existing WDNs provides an opportunity to enhance service resilience through the incorporation of strategic network redundancy. Assessing WDN susceptibility to damage requires deﬁning system performance indicators such as failures, reliability, resilience and vulnerability, as well as characterizing reductions in network structural qualities such as redundancy and optimal connectivity. Failures in water distribution systems mainly fall into two closely related groups (Ostfeld and Shamir, 1993): (i) mechanical failure of system components, and (ii) hydraulic failures in meeting consumer demand. The reliability of a water distribution system is usually deﬁned as the probability of non-failure over a given period of time. The analytical evaluation of the reliability of large WDNs is deemed extremely cumbersome and difﬁcult due to the high dependency of the involved procedures on data from individual system components and their failure modes, and the intricacies of impacts on system performance by the set of all possible subsystem failures (Mays, 2000, p18.2). Hashimoto et al. (1982) were among the ﬁrst to propose the use of indices of resilience (the speed of recovery from failure) and vulnerability (the extent of failure) for the assessment of water resource system performance. Later, Todini (2000), provided an index of resilience related to “the intrinsic capability of the system

A. Yazdani et al. / Environmental Modelling & Software 26 (2011) 1574e1582

to overcome failures”, which to some extent addressed the problem of accounting for reliability. In this work we use a rather conceptual (but perhaps broader) deﬁnition of system resilience provided by Bruneau et al. (2003) characterized by the four infrastructural qualities of robustness, redundancy, resourcefulness and rapidity, which largely incorporate the notions of risk (likelihood and impacts of failures), reliability, recovery, and system tolerance at both pre- and post-failure stages. System vulnerability is consequently regarded as the antonym of resilience and hence we use the words resilience and invulnerability interchangeably. These characteristics viewed individually or together, can be expected to reduce the likelihood and impact of service failures and the total service disruption during emergency conditions (e.g. pipe breakage, ﬁre demand and pump outage). A comprehensive assessment of WDN resilience would entail an analysis and modeling of system performance or failure data during both normal and abnormal operational circumstances, the incorporation of any alternative supply options, as well as disruption response options. Because the data needed to support such an analysis are typically non-existent in a developing world context, this work adopts a restricted yet useful approach by studying the relationship between WDN structure (in particular, redundancy and optimal connectivity) and overall vulnerability. Such a structural analysis, using graph theory as the underlying analytical tool, provides an intuitively robust model of the water distribution system which leads to further explorations of the interplay between system layout and performance, efﬁciency and vulnerability. Moreover, it will demonstrated that performing such a limited assessment of water system resilience by looking at the structure of the network brings additional advantages such as low computational overheads and data requirements. Analysis of the vulnerability of complex networks using graph theory techniques is concerned with the study and quantiﬁcation of network building blocks (e.g. loops, connectivity) and the identiﬁcation of structural weaknesses, critical locations and the impacts of failures of the core components and highly connected nodes or hubs (Albert et al., 2000). This is typically carried out using analytical techniques which assess the impacts of random failures or successive targeted attacks on the efﬁciency and performance of the network (Crucitti et al., 2005). Notable studies concerned with the structural analysis and assessment of the vulnerability of complex networks in other sectors have addressed the resilience of urban transport networks (Zio and Sansavini, 2007; Masucci et al., 2009), the vulnerability of power grids (Bompard et al., 2009, Crucitti et al., 2005 and Holmgren, 2006) and the World Wide Web (Albert et al., 2000). Furthermore, other methodologies have been proposed that analyze cascading failures in such networks, along with the traditional path-based methods in the analysis of infrastructure network reliability (Dueñas-Osorio and Vemuru, 2009). A WDN can be described as a spatially organized system of multiple interconnected components arranged in a non-trivial and rather complex conﬁguration. Such a system may be represented by a mathematical graph as a collection of nodes (e.g. junctions such as pipe intersections, reservoirs and consumers) and links (e.g. pipes and sometimes valves) which deﬁne the relationship between such nodes. In the literature, the problem of reliable design and (capacity) expansion of water distribution systems has been mostly addressed in the context of heuristic methods based on trade-off between reliability and cost by using stochastic simulation-based or mult-iobjective optimization techniques (Simpson et al., 1994; Savic and Walters, 1997; Todini, 2000, 2009; Prasad and Park, 2004; Agrawal et al., 2007; Tanyimboh and Kalungi, 2008). However, modeling WDNs by using network theory measurements has remained a relatively less explored area,

1575

with most of the previous works concerned with reliability or aggregation/skeletonization problems (Jacobs and Goulter, 1988; Walters and Lohbeck, 1993; Yang et al., 1996; Ostfeld, 2005; Giustolisi et al., 2008; Perelman and Ostfeld, 2011 and references therein). In general, graph models do not account for the importance and location of the isolation valves in a WDN reliability analysis (Walski, 1993), and alternative representations based on the segments (i.e. the portions of water distribution systems that can be isolated by valves) are required to make the use of linknode representations more realistic. Apart from such limitations and some other necessary simpliﬁcations that will be made to make modeling viable, the vulnerability and robustness of WDN may still be systematically exposed to analysis by graph theory and complex network measurements (Yazdani and Jeffrey, 2011a,b). Generally speaking, reliability analysis is a probabilistic approach quantifying the likelihood of failure, while structural robustness (invulnerability) analysis is a deterministic approach to quantifying susceptibility of a network structure to damage by using graph properties (Boesch et al., 2009). Studying the structure of water distribution systems may offer a simple framework for assessing network robustness against single or multiple component failures and providing support for decisions on assessment of water distribution system resilience. To this end, this work should be regarded as a contribution falling under the second viewpoint (i.e. the study of structural robustness and interplay between system structure and function) which complements but does not replace general reliability analysis. Among notable contributions based on the use of graph models are work by Jacobs and Goulter (1988, 1989) who showed that the most invulnerable-to-failure design water distribution system is a regular graph with equal number of links incident to each node, while the inverse relationship is not necessarily true due to the existence of bridges (links whose removal disconnects the network) and articulation points (nodes whose removal along with the removal of their incident links disconnects the network). Kessler et al. (1990) used graph theory to develop a methodology for least cost design of invulnerable WDNs by incorporating reliability in the design of the network. Furthermore, Ostfeld and Shamir (1996) and Ostfeld (2005) utilized graphs to study the selection of one-level system redundancy “backups” in a WDN undergoing failures. A recent contribution uses topological clustering of water distribution systems for the purpose of connectivity analysis under various conditions including failure scenarios (Perelman and Ostfeld, 2011). In the work described below, by employing the graph representation of WDNs and quantifying the structure of such a graph, we demonstrate that useful information can be obtained about levels of network redundancy and optimal connectivity. In such a representation, the redundancy (i.e. the existence of the alternative supply paths) is to some extent captured by the loops in the network designs, while structural vulnerability or lack of robustness is observed as graph cut-sets whose failure (i.e. the removal of their constituent components from the graph) may result in the disconnection of a large number of nodes (e.g. consumers or distribution branches) from water supply sources. Using graph models and network measurements enables a systematic quantiﬁcation of the structure of WDNs even for large complex systems. This, in turn, allows for a comparison of connectivity patterns for alternative design, which can be used to improve system robustness and resilience by avoiding critical locations and network bottlenecks. This is, in particular, extremely important to water system engineers and urban planners contemplating sustainable strategies for WDNs within a wider context of optimally-designed next-generation infrastructures.

1576

A. Yazdani et al. / Environmental Modelling & Software 26 (2011) 1574e1582

This paper is organized as follows. First, we brieﬂy introduce some graph theory metrics and measurements and explain how they might be interpreted and used to capture qualities such as redundancy, optimal connectivity and structural robustness. Second, we study the structure of the water distribution network of Kumasi (Ghana’s second largest city), quantify its connectivity and redundancy and explore the relationship of these metrics to the network’s structural invulnerability and robustness. We then examine a number of scenarios for the expansion of this network to serve a growing part of the city (based on current development plans), and investigate different investment options to improve structural invulnerability subject to limited ﬁnancial resources. We make heuristics-based recommendations on how to achieve budget-constrained network expansions supported by the undertaken measurements. Finally, we discuss the scope, usefulness and limitations of the proposed methodology in dealing with the resilience of real water distribution systems and brieﬂy look at future directions for this work. 2. Network characteristics and measurements A WDN is primarily a network of interconnected pipes and other appurtenances through which water is conveyed, stored intermittently and pumped where necessary in order to meet the demand and pressure requirement of the system. Such a network is typically governed by complex structures and dynamical processes due to its usually large number of interconnected interacting components which are ordered in non-trivial conﬁgurations. One way to represent the structure of any such system is by employing a mathematical graph which is a collection of nodes to represent elements at speciﬁc locations (such as pipe intersections, reservoirs, consumers and pumps) and links to represent the pipes which deﬁne the relationship between such nodes. The study of complex networks by using techniques from graph theory helps with the classiﬁcation of different network models and quantifying their building blocks which may partly explain the vulnerability, robustness and tolerance of the system to errors and attacks (Albert et al., 2000). Throughout, a network is represented as a mathematical graph G ¼ GðV; EÞ in which V is the set of all graph nodes with n elements (graph size) and E is the set of graph edges with m elements (graph order). WDNs are typically connected graphs in the sense that every two distinct nodes are connected by some path (i.e. a set of links). However, the most important aspect of such connectivity is that every node or link in the network should ideally remain connected to a water supply source such as a tank or a reservoir, at least in an ideal modeling environment (e.g. in an all-channel network with no-failure condition). Water distribution systems could be potentially represented as weighted bi-directional networks where the direction of the network ﬂow and the weights allocated to each graph links or nodes are determined by the physical and operational attributes such as the nodal demand for water or the actual ﬂow inside each pipe. However, in some of the networks studied here no such data on system attributes was available to this study and hence all networks were treated as undirected and unweighed graphs for the sake of maintaining the consistency among the measurements. WDNs are typically organized spatially, parallel to or underneath roads and other urban structures. Despite the fact that different points in a WDN might have different heights (such as the two end points of a water main that carries water uphill), from a technical point of view a WDN might be regarded as a nearlyplanar graph. A planar graph is one that can be drawn on a plane without having edges intersecting other than at a node mutually incident with them. This condition is not necessarily violated due to

the presence of components with elevation, as the graph may be redrawn so as to project its elevated components onto a twodimensional plane. In reality, however, WDNs are not strictly planar due to the existence of crossovers (i.e. pipes crossing over or under other pipes) but only nearly-planar. In other words, only a negligible percentage of the network edges intersect at locations other than at a node mutually incident with them (Newman, 2010). Structural measurements quantify the connectivity patterns among the network components. Kessler et al. (1990) used two basic yet important such metrics of link- and node-connectivity that quantify the minimum number of attacks or failures required to render a group of network nodes disconnected from the water supply source. However, these metrics become trivial in WDNs which exhibit low redundancy and sparseness at transmission or subsystem level. Sparse networks are deﬁned as networks with the number of links linearly proportional to the number of nodes i.e. m ¼ Oðjnjk Þ for 1 < k < 2 (Diestel, 2005). In real sparse networks the isolation of only a very few links from the source makes the graph disconnected. This could happen where there is not much redundancy available in the system and hence the structure of the network is free from loops, at least locally. In other words, the failure of the bridge type pipes in the design of WDNs may result in a disconnection between the reservoirs or tanks and the consumers. The structural network measurements introduced in this work, broadly classiﬁed into statistical and spectral forms, overcome such difﬁculties by providing a deeper analysis of the network connectivity. Table 1 provides a brief deﬁnition of the statistical and spectral measurements utilized in this analysis together with an indication of which property (robustness or redundancy) is being assessed through each metric. In each case, the magnitude of the value of each measurement indicates the level of signiﬁcance of the associated property. Statistical measurements are those which quantify organizational properties of the network, based on the structural patterns and network building blocks. Descriptions of the statistical measurements utilized in this analysis are provided below: 1. Link density q is the most basic indicator of the overall linkedness or sparseness of the structure of a network. This metric is not scale invariant and hence its magnitude may change by changing the network size. 2. Average node degree < k > accompanied by the degree distribution (i.e. histogram of the node degrees) is a basic measure of the connectivity. It reﬂects the overall topological similarity of the network to perfect grids or lattice-like structures, important toward equalized distribution of ﬂow and pressure under varying demands. 3. Network diameter or the longest shortest path dT captures the maximum eccentricity of nodes in the network that when combined with the distribution of the Euclidean lengths of the links, provides a basic measure of topological and geographical spread of the network. 4. Average (geodesic) path-length lT estimates the average number of links that need to be traversed in order to reach from one point to another. This will provide a limited view of network reachability and efﬁciency in water transport, while viewed against the actual Euclidean path-length lE (and the indicators of operational efﬁciency measured by the level of conservation of energy). 5. Clustering coefﬁcient Cc (Wasserman and Faust, 1994), also known as transitivity, is used to measure the redundancy by quantifying the density of triangular loops and the degree to which junctions in a graph tend to be linked. Clustering coefﬁcient is usually found to be a tiny number in grid-like

A. Yazdani et al. / Environmental Modelling & Software 26 (2011) 1574e1582

1577

Table 1 Metrics used to assess the structure, redundancy and robustness of complex networks. Metric

Deﬁnition

Mathematical expression

Quantifying

Link density

The fraction between the total and the maximum number of links. Average value of the node degree distribution.

2m q ¼ nðn 1Þ 2m < k >¼ n dT ¼ maxfdðvi ; vj Þ : cvi ˛Vg

Structure

Average node-degree Diameter Average path-length Clustering coefﬁcient Meshed-ness coefﬁcient Central-point dominance Density of articulation points Density of bridges Spectral gap Algebraic connectivity

6.

7.

8.

9.

The maximum geodesic distance between any two nodes in a network. The average number of steps along the shortest paths between all possible pairs of network nodes. The fraction between the total number of triangles NΔ and the total number of connected triples N3. The fraction between the total and the maximum number of independent loops in planar graphs. Average difference between the centrality of the most central-point Bmax and all other network nodes Bi. The ratio of the total number of articulation points Nap over all nodes. The ratio of the total number of bridges Nbr over all edges. The difference between ﬁrst and second eigen values of graph’s adjacency matrix. The second smallest eigen value of normalized Laplacian matrix of the network.

structures and networks with structural loops different from a simple triangle. Meshed-ness coefﬁcient Rm (Buhl et al., 2006) to quantify the status of general loops (of any length) in the network. It provides an estimation of topological redundancy in nearplanar WDNs by ﬁnding the number of actually present independent loops ðm n þ 1Þ as a percentage of the maximum possible loops in planar graphs ð2n 5Þ. Central-point dominance CB (Freeman, 1997) measures the concentration of the network topology around a central location. It can be regarded as a large-scale quantiﬁer of the network vulnerability against failures that might occur around that central location. Its calculation is based on the betweenness centrality of the network nodes, deﬁned as the number of shortest geodesic paths between two given vertices that pass through that node divided by the total number of shortest geodesic paths between those two vertices. The value of CB is limited by the two extremes of CB ¼ 1 for star topology and CB ¼ 0 for regular networks with the same number of connections at each node. The density of articulation points Dap estimates the percentage of the nodes/junctions whose failure may potentially disrupt water delivery by isolating a part of the network from the water supply source. An articulation point is a node whose removal along with the removal of the incident links disconnects the network. The density of bridges Dbr estimates the percentage of the links/pipes whose failure may potentially disrupt water delivery by isolating a part of the network from the water supply source. A bridge is a link whose removal disconnects the network.

Spectral metrics are those derived from the spectrum (set of eigen values and eigenvectors) of the network adjacency or Laplacian matrices and quantify invariant properties which depend only on the abstract structure and remain unchanged under different representations. The adjacency matrix of graph G with n nodes is the unique n n matrix A¼(aij) where aij ¼ 1 if there is a link between nodes i and j and aij ¼ 0 otherwise. The Laplacian matrix of G is deﬁned as L ¼ D A where D ¼ diag(ki) and ki is the degree of node i. Two important spectral metrics utilized in this work, also described in Table 1 are:

X 1 * lT ¼ dðvi ; vj Þ nðn 1Þ i;j 3ND Cc ¼ N3 mnþ1 Rm ¼ 2n 5 1 X CB ¼ ðBmax Bi Þ n1 i Nap Dap ¼ n N Dbr ¼ br m

Structure Network efﬁciency Network efﬁciency Redundancy Redundancy Robustness Robustness

Dl

Robustness Robustness

l2

Robustness

1. Spectral gap Dl (Estrada, 2006) provides information on the robustness of the network. Spectral gap is used for the purpose of detecting networks with “good expansion” properties (those that possess optimal connectivity layouts) and such value must be sufﬁciently large. Small spectral gap would probably indicate the presence of articulation points or bridges that might cause serious disruptions to ﬂow in the network when removed. 2. Algebraic connectivity l2 ﬁrst deﬁned in (Fiedler, 1973) and extensively discussed in Mohar (1991), quantiﬁes the network’s structural robustness and fault tolerance. While the smallest eigen value of a network’s Laplacian is zero and its multiplicity equals the number of connected components in a network, a larger value of algebraic connectivity indicates enhanced fault tolerance and robustness against efforts to cut the network into isolated parts. In the following section, statistical and spectral measurements for a case study WDN and its expansions are derived and their relationship to network robustness and vulnerability is interpreted. It will be demonstrated that spectral metrics, taken along with the

Fig. 1. GIS view of Kumasi town water distribution system.

1578

A. Yazdani et al. / Environmental Modelling & Software 26 (2011) 1574e1582

described statistical measurements, reveal useful information on patterns of connectivity of the network and its structural tolerance against component failures. 3. Case studies and methodology The water distribution system chosen for this research is from Kumasi, the second largest city in Ghana, located in the Ashanti region. The town has a population of over one and a half million people with several rapidly growing water consuming industries. The water distribution system is managed and operated by “Aqua Vitens Rand Limited” on behalf Ghana Water Company Limited (GWCL) under a World Bank management contract. The network is large and sparse with redundant loops at the urban center and branched conﬁgurations at the outskirts (see Fig. 1). The network has expanded gradually over the past half century. The two water production facilities are at the outskirts of the city, and ﬁve main

reservoirs are located in the suburban areas where the dominant network architecture is to some extent branched. This presents a danger of major ﬂow disruption following pipe failures or system component breakdowns anywhere close to these supply points. The undertaken analysis involved conventional data manipulations (mostly carried out using ArcGIS), network measurements and validation of results. Similar to the practices in the hydraulic analysis of water distribution systems, the network’s end user distribution pipes falling below the diameter of 50 mm are removed from this analysis as they don’t play a signiﬁcant role in providing redundancy. Network measurements were undertaken using the open-source graph manipulation software “igraph” (Csárdi and Nepusz, 2006) which can be used as an extension package to the statistical computing software “R” (R Development Core Team, 2009) and is available free online. Calculations of the various statistical and spectral measurements are conducted as follows: (i) Install and call igraph library package in “R”

Fig. 2. A GIS view of (a) the Kumasi network, (b) the section earmarked for expansion, and the expansion scenarios: (c) branched expansion KSIB, (d) looped expansion KSIL, (e) extra-looped expansion KSIXL, and (f) meshed expansion KSIM.

A. Yazdani et al. / Environmental Modelling & Software 26 (2011) 1574e1582

1579

Table 2 Descriptive structural measurements for the expansion options and existing Kumasi structure. Network

n

m

q

dr

lr

lE (meters)

Cc

Rm

Kumasi With KSIB With KSIL With KSIXL With KSIM

2799 2869 2869 2869 2869

3065 3135 3140 3143 3183

0.08% 0.08% 0.08% 0.08% 0.08%

2.19 2.19 2.19 2.19 2.22

120 136 106 104 104

33.89 35.17 33.96 33.00 32.64

316.19 341.71 344.37 345.80 369.13

0.0154 0.0151 0.0150 0.0150 0.0145

4.77 4.66 4.74 4.80 5.49

environment (other library packages such as “matrix”, “stats” or “graph” might be required depending on the undertaken analysis). (ii) Read the network ﬁle, structured in a format supported by igraph functions for reading external ﬁles. (iii) For each measurement use the associated functions, directly or in combination with others, by using “R” commands. Most of the calculations are performed in linear or polynomial computation time depending on the function being applied and network size (Csárdi and Nepusz, 2010). 4. Expansion strategies WDNs in cities like Kumasi are subject to continual refurbishment and expansion. Under such conditions, early assessment of existing network structural vulnerability is critical to support strategic planning and operational decisions focused on improved system invulnerability to hazards and perturbations, both now and into the future. With cost as a signiﬁcant limiting factor in the expansion of WDNs in developing countries, we devised hypothetical expansion scenarios for the Kumasi network and quantiﬁed the overall degree of redundancy, robustness and efﬁciency for each option, providing an assessment of each expansion option’s economic value. The economic aspect of design and expansion of water distribution systems may well be viewed as a pipe-sizing optimization problem, where the objective function which is to be minimized is given by the total cost of network construction as a function of the pipe diameter and length (for example see Walski et al., 2003, p362). In the analysis to follow, the cost-related impacts of different expansion strategies from a purely topological point of view are investigated. It should be noted that, here, only the total pipe length associated with the addition of new pipes (as a surrogate for the cost of expansion) is taken into consideration. For the sake of simplicity however, other physical attributes such as pipe diameter and material are assumed to be the same across all the expanded segments. In general, the reliability and invulnerability of WDNs is enhanced by improving redundancy. To determine the appropriate level of redundancy and to beneﬁt from its targeted allocation (e.g. at the most effective locations), exploring alternative design options could prove invaluable. However, undertaking a thorough assessment of the best expansion strategies may become cumbersome and costly, due to the technical and computational complexities involved in performing extensive calculations which need to take into account numerous redundancy placement eventualities in the network. To this end, performing low cost but reasonably accurate investigations for a limited number of expansion strategies may prove useful and are regarded as a necessary (but perhaps insufﬁcient) step toward analysis of information related to overall system resilience. Network expansion strategies are mainly focused on meeting the extra demand for water subject to limited network design and implementation costs. Increasing network redundancy would usually also increase the cost of any expansion strategy. However, most of the reliable network design optimization algorithms would generate solutions which reduce the cost of the network by removing redundancy and ultimately generating a sparse structure,

* * * * *

102 102 102 102 102

which is highly vulnerable to component failures (Kessler et al., 1990). Therefore, the allocation of redundancy in the network structure (though limited) needs to be accompanied by strategies to maximize the beneﬁts of such investment. In other words, any such expansion plan may ideally seek to either minimize the cost of expansion, or maximize the robustness in design, or both. This is to ensure that the selected expansion strategy satisﬁes good connectivity criteria while keeping costs within budget. In order to simulate a realistic network expansion strategy to meet the demand from the projected population growth in north eastern Kumasi we created 70 new demand nodes (representing an approximately 2.5% increase in total demand on the network) and a minimum of 100 Km of new pipe-work (representing an approximate 10% increase in the total length of the network mains). We created four hypothetical network expansion options, starting from a tree-like expansion with no loops, gradually moving toward more looped structures which are deemed better-conceived networks with greater redundancy. Subsequently, we performed the calculations for various resilience metrics and compared the results with those from the unexpanded network to assess how robust the expansion options are and how they contribute to enhancing or degrading the overall system robustness and its ability to deliver service. An overview of the geographical spread of the whole of the Kumasi network is shown in Fig. 2(a) as well as the location of the expansion area Fig. 2(b) and the four expansion options Fig. 2cef. The four devised network expansion scenarios we created and tested are: a) Branched (KSIB): a branched-only expansion (100.8 km total added length) where one directional ﬂow is generated by the distribution from the source to end nodes in the system, with each intermediate node connected to one upstream and one downstream node only (Fig. 2c). b) Looped (KSIL): an expansion consisting of the nodes that can receive water from more than one source as a consequence of a long loop structure (110.9 km total added length). It is created by connecting the end nodes of the branched network to set up loops (Fig. 2d). c) Extra-Looped (KSIXL): a network generated by inserting two additional pipes to KSIL (116.5 km total added length) that are strategically placed to create extra loops at the locations adjacent to water supply sources (Fig. 2e). d) Meshed (KSIM): an almost totally looped expansion pattern (205.2 km total added length) with most of the intermediate nodes connected to four pipes to form a grid-like structure (Fig. 2f). Table 3 Robustness measurements for Kumasi and other expansion options. Network

CB

Dap

Dbr

Dl

Kumasi With KSIB With KSIL With KSIXL With KSIM

0.45 0.38 0.39 0.39 0.39

0.42 0.43 0.41 0.41 0.41

0.91 0.92 0.91 0.91 0.90

9.08 1.89 1.89 1.89 1.71

l2 * * * * *

103 103 103 103 101

9.40 9.24 9.46 9.48 9.48

* * * * *

105 105 1.5 105 105

1580

A. Yazdani et al. / Environmental Modelling & Software 26 (2011) 1574e1582

Table 4 Basic structural measurements for local sections. Network

n

m

q

dr

lr

lE (meters)

Cc

Rm

Kumasilocal KSIBlocal KSILlocal KSIXLlocal KSIMlocal

765 834 834 834 834

812 881 886 889 929

0.28% 0.25% 0.26% 0.26% 0.27%

2.12 2.11 2.12 2.13 2.23

90 107 76 63 60

27.76 31.67 27.51 24.53 23.41

266.51 359.75 369.09 374.10 453.18

1.20Ee02 1.13Ee02 1.12Ee02 1.11Ee02 9.75Ee03

3.02Ee01 2.77Ee02 3.07Ee02 3.25Ee02 5.65Ee02

spectral gap and other redundancy or robustness measures suggest that KSIM possesses the most redundant, the most structurally robust and perhaps the most efﬁcient structure but also the most expensive design, while KSIB possesses the least redundant and the least robust structure but not the least expensive design (Fig. 3). The quantiﬁed measurements of network structure for only the expanded section of the network are provided in Table 4 (connectivity measurements) and Table 5 (vulnerability and robustness measurements), with an illustration of the impact of extra investment in design through additional pipe length on local redundancy and robustness presented in Fig. 4. The obtained numerical values show similar trends to those previously observed in Tables 2 and 3. In other words, it might be stated in a similar fashion that the KSIM option possesses the most redundant, most robust and perhaps the most efﬁcient local structure, while the KSIB option possesses the least redundant and least robust structure. The structural measurements undertaken for the expansion options demonstrate that in general an increase in redundancy at the local expansion level may not only improve the structural robustness and efﬁciency at the local scale, but may also improve network invulnerability at a larger scale. This is clearly reﬂected in the increasing trend observed in the values indicating robustness and efﬁciency by gradually moving from KSIBlocal to KSIMlocal. Implementation of such redundancy, however, comes at a cost and is not always feasible due to the required resources and the personnel to develop a new source of supply, in addition to geographical and many other limitations. In particular, the study and comparison of the quantiﬁed redundancy and robustness of the expansions KSIXL and KSIM and KSIXLlocal and KSIMlocal (Tables 2e5, Figs. 3 and 4) suggest that an excessive implementation of redundancy may not necessarily result in a signiﬁcant

1.0E-04

Network

Ca

Dap

Dbr

Dl

l2

Kumasilocal KSIBlocal KSILlocal KSIXLlocal KSIMlocal

0.48 0.49 0.44 0.49 0.50

0.47 0.50 0.43 0.42 0.41

0.94 0.95 0.94 0.94 0.90

1.64Ee01 1.64Ee01 1.64Ee01 1.64Ee01 1.72Ee01

1.58Ee04 1.13Ee04 3.12Ee04 4.05Ee04 4.35Ee04

21.1%

KSIXL

12.0%

KSIL

11.4%

KSIB

10.4%

Kumasi

0.0%

0.05

KSIM

Algebraic connectivity

0.10

0.00

Table 5 Robustness measurements for local sections.

0.0E+00

0.15

Meshedness coefficient

We use two sets of structural measurements to analyze the Kumasi WDN expansions: (i) those quantifying the structure of the whole network including expanded sections, and (ii): those quantifying the expanded sections only. Considering the expanded part of the network in isolation provides an assessment of structural vulnerability assuming there is a choice to develop a new source of supply independent from the whole network to improve water service reliability. Results relating to the whole network, in its original and four expanded forms, show insigniﬁcant differences in many of the descriptive structural quantities listed in Table 2 (respectively robustness indicators listed in Table 3) of the expanded network when compared with the unexpanded conﬁguration. Consequently, the impact of the expansions on the structure of the networks was captured by the ‘expanded sections only’ measurements based on quantiﬁcation of structure in Table 4 (respectively robustness in Table 5). It is worth mentioning that, in general, other descriptive metrics may be selected in order to further reﬂect the small changes in value of key performance indicators following expenditures. This may well deﬁne a broader cost-beneﬁt type of analyses using more sophisticated techniques as compared to the relatively simple method presented here. It is observed that expansions make the original network more expensive to build (through larger lE which is the average pipe length in meters) but also more structurally reachable in terms of the topological distances (i.e. smaller dT and lT), hence arguably more efﬁcient. The network expansion options possess loops of more than three links, so the primary focus is on the Meshed-ness coefﬁcient as an indicator of redundancy (Yazdani and Jeffrey, 2011a). The value of the clustering coefﬁcient decreases in network expansions with mostly non-triangular loops added, where the meshed-ness coefﬁcient increases such as in the design of KSIM. Other measurements related to the structural robustness of expanded networks are included in Table 3. All expansions have smaller values of central-point dominance than the original Kumasi structure, hence representing lower structural density around a central location. However, no signiﬁcant change is observed in the overall density of bridges and articulation points, partly because the expansions are designed to replicate the original Kumasi structure. The value of spectral gap is signiﬁcantly larger in KSIM than the other expansion options. In order for a large sparse network to have “Good Expansion” properties (i.e. structured in a way that vertices connect in a robust way), having a larger spectral gap is a necessary condition (Estrada, 2006). However, we use spectral gap as a measure of robustness only with caution, because it largely favors meshed conﬁgurations. The study of the algebraic connectivity,

2.0E-04

Percentage of added pipe length (Km) Fig. 3. Comparison of the global expansion options: meshed-ness coefﬁcient (red bars) and algebraic connectivity (blue hanging bars) as a function of normalized percentage of added pipe length indexed to total Kumasi pipe length. (For interpretation of the references to color in this ﬁgure legend, the reader is referred to the web version of this article.)

A. Yazdani et al. / Environmental Modelling & Software 26 (2011) 1574e1582

Meshedness coefficient

0.10

4.0E-04 KSIM 0.05 Kumasi

KSIB

KSIL

KSIXL

94.5%

53.6%

51.1%

46.4%

8.0E-04 0.0%

0.00

Algebraic connectivity

0.0E+00

0.15

Percentage of added length (Km) Fig. 4. Comparison of the local sections: meshed-ness coefﬁcient (red bars) and algebraic connectivity (blue hanging bars) as a function of normalized percentage of added pipe length indexed to total Kumasi pipe length. (For interpretation of the references to color in this ﬁgure legend, the reader is referred to the web version of this article.)

improvement in network robustness. While the lack of investment (approximated here by the total percentage increase of the pipe length) such as that observed in the KSIB expansion option may endanger overall robustness of the network, especially at local levels, by leaving it vulnerable to the failure of components, an over-allocation of redundancy may result in a signiﬁcant amount of extra cost (KSIM is slightly less than twice as costly as KSIXL) while gaining only marginal extra robustness. The lesson here is that in order to maintain an acceptable level of reliability and invulnerability in the design and expansion of WDNs, analytical modeling should not only consider a wide range of alternative design strategies, but should also be validated by heuristics. 5. Discussion and conclusions In the foregoing, we have explored a suite of WDN expansion strategies (branched, looped, extra-looped and perfect-mesh) aimed at securing and promoting structural invulnerability subject to design and budget constraints using a developing country case study. The structural measurements are based on the premise that water distribution infrastructures are spatially organized networks of components (i.e. nodes and links) which represent actual physical locations of water distribution appurtenances. This property, in line with the main objective of water distribution systems, which is to supply water from source to consumers with standard quality and sufﬁcient quantity, has important consequences in terms of the patterns of connectivity of the underlying network. For example the local topological structure of WDNs can vary between densely-constructed (e.g. meshed-like) structures in urban centers to very sparse (e.g. tree-like) structures at suburban transmission level. On the other hand, the inevitable existence of pipe-bridges in a network which direct water from a reservoir to a large proportion of consumers may signiﬁcantly affect the vulnerability of the system. Therefore, there exists interplay between structure and resilience which makes the task of quantifying the network structure in order to comment on overall reliability and resilience worthwhile. By using the proposed methodology (which relies on powerful and rigorous metrics including the spectral and statistical measurements) some of the vaguely understood qualities such as optimal connectivity, structural robustness and path redundancy in

1581

WDNs may be quantiﬁed in a fashion which is relatively fast and inexpensive to implement. The proposed methodology may therefore be regarded as a relatively quick-to-implement precursor to more detailed trade-off analyses involving (for example) reliability and cost (Prasad and Park, 2004; Agrawal et al., 2007; Tanyimboh and Kalungi, 2008) or multi-objective considerations (di Pierro et al., 2009) which are usually highly data-dependent and/or require extensive computational resources. For example, a preliminary identiﬁcation of resilient network structure as illustrated above might form the basis for subsequent analysis using the robust optimization approach recently reported in this journal by Chung et al. (2009). However, it should be borne in mind that purely topological measurements may only partially describe the network structure and fail to entirely characterize its properties. Moreover, an extensive assessment of water distribution system resilience depends not only on structural measurements, but also largely on domain-speciﬁc heuristics and information (such as the location of isolation valves or the location of tanks and storage facilities). This shows that oversimpliﬁcation of water distribution systems into abstract graph models is extremely useful but far from sufﬁcient for a comprehensive assessment of system resilience and its robustness against perturbations and hazards. Another contribution of this work is that a tentative ranking of structural vulnerability of networks with different expansion options was proposed, based on the comparison of the quantiﬁed optimal connectivity and robustness of water distribution systems. This was later used to support the budget-constrained strategies for invulnerable expansion of water distribution system of a growing city from a developing country (i.e. Ghana). In places where the cost of development and network expansion is an issue, alternative design strategies become crucial toward sustainable and resilient development of water distribution systems. Given a set of hypothetical demand points, the objective is to expand the existing network and connect it to these locations in an inexpensive fashion subject to geographical restrictions while maintaining a minimum level of reliability and resilience. In reality, this deﬁnes a complex combinatorial optimization problem where ﬁnding its solution may require extensive computations depending on network size and capacity, and domain-related information on terrain speciﬁcations and population density of the served area, to say the least. On the other hand, a simpliﬁed network-based approach (as demonstrate above) could provide useful insight on where and to what extent the redundancy to avoid or tolerate failures should be allocated in the network structure. Undertaking such a basic cost-beneﬁt analysis may largely contribute to the development of well-conceived least cost network designs and strategies for invulnerable expansions where the cost of construction is an important consideration such as in the developing countries. Subsequently, it can be argued that great beneﬁts in terms of overall system resilience and invulnerability may be gained by following such rational which is based on the ﬁne-tuning allocating of redundancy and its strategic placement in the system. Acknowledgments The authors are grateful to the Leverhulme Trust for ﬁnancial support and to Ghana Water Co. Ltd. for making available the Kumasi data. R. A. Otoo was partially supported by the Commonwealth Scholarship Commission, British Council. References Agrawal, M.L., Gupta, R., Bhave, P.R., 2007. Reliability-based strengthening and expansion of water distribution networks. Journal of Water Resources Planning and Management 133 (6), 531e541.

1582

A. Yazdani et al. / Environmental Modelling & Software 26 (2011) 1574e1582

Albert, R., Jeong, H., Barabasi, A.-L., 2000. Error and attack tolerance of complex networks. Nature 406, 378e382. Boesch, F.T., Satyanarayana, A., Suffel, C.L., 2009. A survey of some network reliability analysis and synthesis results. Networks 54 (2), 99e107. Bompard, E., Napoli, R., Xue, F., 2009. Analysis of structural vulnerabilities in power transmission grids. International Journal of Critical Infrastructures Protection 2, 5e12. Bruneau, M., Chang, S.E., Eguchi, R.T., Lee, G.C., O’Rourke, T.D., Reinhorn, A.M., Shinozuka, M., Tierney, K., Wallace, W.A., von Winterfeldt, D., 2003. A framework to quantitatively assess and enhance the seismic resilience of communities. Earthquake Spectra 19 (4), 733e752. Buhl, J., Gautrais, J., Reeves, N., Sole, R.V., Valverde, S., Kuntz, P., Theraulaz, G., 2006. Topological patterns in street networks of self-organized urban settlements. European Physical Journal B 49, 513e522. Chung, G., Lansey, K., Bayraksan, G., 2009. Reliable water supply system design under uncertainty. Environmental Modelling & Software 24 (4), 449e462. Csárdi, G., Nepusz, T., 2006. The igraph software package for complex network research. InterJournal; Complex Systems, 1695. Csárdi, G., Nepusz, T., 2010. Igraph Reference Manual. available online at. http:// igraph.sourceforge.net/documentation.html (accessed 20.06.10). CRED, 2009. Natural Disaster Trends, World 1900e2009. available online at. http:// www.emdat.be/natural-disasters-trends (accessed 05.07.10). Crucitti, P., Latora, V., Marchiori, M., 2005. Locating critical lines in high-voltage electrical power grids. Fluctuation and Noise Letters 5 (2), 201e208. di Pierro, F., Khu, S.-T., Savic, D., Berardi, L., 2009. Efﬁcient multi-objective optimal design of water distribution networks on a budget of simulations using hybrid algorithms. Environmental Modelling & Software 24 (2), 202e213. Diestel, R., 2005. Graph Theory. Springer, Berlin. Dueñas-Osorio, L., Vemuru, S.M., 2009. Cascading failures in complex infrastructure systems. Structural Safety 31, 157e167. Estrada, E., 2006. Network robustness to targeted attacks: the interplay of expansibility and degree distribution. European Physical Journal B 52, 563e574. Fiedler, M., 1973. Algebraic connectivity of graphs. Czechoslovak Mathematical Journal 23, 298e305. Freeman, L.C., 1997. A set of measures of centrality based on betweenness. Sociometry 40 (1), 35e41. Giustolisi, O., Kapelan, Z., Savic, D., 2008. Algorithm for automatic detection of topological changes in water distribution networks. Journal of Hydraulic Engineering ASCE 134 (4), 435e446. Hashimoto, T., Loucks, D.P., Stedinger, J.R., 1982. Robustness of water resources systems. Water Resources Research 18, 21e26. Holmgren, A.J., 2006. Using graph models to analyse the vulnerability of electric power networks. Risk Analysis 26 (4), 955e969. Jacobs, P., Goulter, I.C., 1988. Evaluation of methods for decomposition of water distribution networks for reliability analysis. Civil Engineering Systems 5 (2), 58e64. Jacobs, P., Goulter, I.C., 1989. Optimization of redundancy in water distribution networks using graph theoretic principles. Engineering Optimization 15 (1), 71e82. Kessler, A., Ormsbee, L., Shamir, U., 1990. A methodology for least-cost design of invulnerable water distribution networks. Civil Engineering Systems 7 (1), 20e28. Masucci, A.P., Smith, D., Crooks, A., Batty, M., 2009. Random planar graphs and the London street network. European Physical Journal B 71 (2), 259e271. Mays, L.W., 2000. Water Distribution Systems Handbook. McGraw-Hill, New York. Mohar, B., 1991. The Laplacian spectrum of graphs. In: Alavi, Y., et al. (Eds.), Graph Theory, Combinatorics and Applications, 2. Wiley, New York, pp. 871e898.

Newman, M.E.J., 2010. Networks, an Introduction. Oxford University Press Inc., New York. Ostfeld, A., Shamir, U., 1993. Incorporating reliability in optimal design of water distribution networks-review and new concepts. Reliability Engineering and System Safety 42, 5e11. Ostfeld, A., Shamir, U., 1996. Design of optimal reliable multi-quality water-supply systems. Journal of Water Resources Planning and Management 122 (5), 322e333. Ostfeld, A., 2005. Water distribution systems connectivity analysis. Journal of Water Resources Planning and Management 131 (1), 58e66. Perelman, L., Ostfeld, A., 2011. Topological clustering for water distribution system analysis. Environmental Modelling & Software 26, 969e972. Prasad, T.D., Park, N.-S., 2004. Multiobjective genetic algorithms for design of water distribution networks. Journal of Water Resources Planning and Management 130 (1), 73e82. R Development Core Team, 2009. R: A Language and Environment for Statistical Computing, R Foundation for Statistical Computing. Vienna, Austria, available online at, ISBN 3-900051-07-0. http://www.R-project.org (accessed 20.05.10). Savic, D.A., Walters, G.A., 1997. Genetic algorithms for least-cost design of water distribution networks. Journal of Water Resources Planning and Management 123 (2), 67e77. Simpson, A.R., Dandy, Graeme C., Murphy, Laurence J, 1994. Genetic algorithms compared to other techniques for pipe optimization. Journal of Water Resources Planning and Management 120 (4), 423e443. Tanyimboh, T., Kalungi, P., 2008. Holistic planning methodology for long-term design and capacity expansion of water networks. Water Science and Technology: Water Supply 8 (4), 481e488. Todini, E., 2000. Looped water distribution network design using resilience index based heuristic approach. Urban Water 2, 115e122. Todini, E., 2009. Design, expansion and rehabilitation of water distribution networks aimed at reducing water losses. Where are we? In: Van-Zyl, K. (Ed.), Proceedings of the 10th Annual Water Distribution Systems Analysis Conference WDSA 2008, p. 33. UNDP, 2006. Human Development Report 2006, Beyond Scarcity: Power, Poverty and Global Water Crisis. Palgrave Macmillan, New York. Walski, T., 1993. Water distribution valve topology for reliability analysis. Reliability Engineering and System Safety 42, 21e27. Walski, T.,M., Chase, D.V., Savic, D.A., Grayman, W., Beckwith, S., Koelle, E., 2003. Advanced Water Distribution Modelling and Management. HAESTAD Press, Waterbury, CT. Walters, G.A., Lohbeck, T., 1993. Optimal layout of tree networks using genetic algorithms. Engineering Optimization 22 (1), 27e48. Wasserman, S., Faust, K., 1994. Social Network Analysis: Methods and Applications. Cambridge University Press, Cambridge. Yang, S.-L., Hsu, N.-S., Loule, P.W.F., Yeh, W.W.-G., 1996. Water distribution network reliability: connectivity analysis. Journal of Infrastructure Systems 2 (2), 54e64. ASCE. Yazdani, A., Jeffrey, P., 2011a. Complex network analysis of water distribution systems. Chaos 21 (1). Yazdani, A., Jeffrey, P., 2011b. Applying graph theory to quantify the redundancy and structural vulnerability of water distribution networks. Journal of Water Resources Planning and Management. doi:10.1061/(ASCE)WR.1943-5452. 0000159 (13 May 2011). Zio, E., Sansavini, G., 2007. Service reliability analysis of a tramway network. ESREL 2007, Risk, Reliability and Societal Safety. In: AvenT., Vinnem, J.E. (Eds.), Proceedings of the European Safety and Reliability Conference 2007, pp. 907e913.