Applying Network Theory to Quantify the Redundancy and Structural Robustness of Water Distribution Systems
Publication: Journal of Water Resources Planning and Management
Volume 138, Issue 2
Abstract
A water distribution system, represented as a spatially organized graph, is a complex network of multiple interconnected nodes and links. The overall robustness of such a system, in addition to the reliability of individual components, depends on the underlying network structure. This paper presents a deterministic network-based approach to study the relationship between the structure and function of water distribution systems and to critically review the application of structural measurements in the analysis of vulnerability and robustness of such systems. Benchmark water supply networks are studied, and their level of resistance to random failures and targeted attacks on their bridges and cut-sets are explored. Qualitative concepts such as redundancy, optimal connectivity, and structural robustness are quantified. Among other measurements, two metrics of meshedness coefficient and algebraic connectivity are found of great use toward quantifying redundancy and optimal connectivity, respectively. A brief discussion on the usefulness, scope, and limitations of the proposed approach in the analysis of real-world water distribution networks is presented.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgements
We would like to thank the Leverhulme Trust UK for their financial support and the Centre for Water Systems at the University of Exeter for providing access to EXNET and other benchmark data. We also wish to thank the reviewers, whose constructive and helpful comments significantly improved the quality of this work.
References
Albert, R., Jeong, H., and Barabási, A.-L. (1999). “Diameter of the World-Wide Web.” Nature (London), 401, 130–131.
Albert, R., Jeong, H., and Barábasi, A.-L. (2000). “Error and attack tolerance of complex networks.” Nature, 406, 378–382.
Alderson, D. L. (2008). “Catching the network science bug: Insight and opportunity for the operations researcher.” Oper. Res., 56(5), 1047–1065.
Babayan, A., Kapelan, Z., Savic, D., and Walters, G. (2005). “Least-cost design of water distribution networks under demand uncertainty.” J. Water Resour. Plan. Manage., 131(5), 375–382.
Boesch, F. T., Satyanarayana, A., and Suffel, C. L. (2009). “A survey of some network reliability analysis and synthesis results.” Networks, 54(2), 99–107.
Bompard, E., Napoli, R., and Xue, F. (2009). “Analysis of structural vulnerabilities in power transmission grids.” Int. J. Crit. Infrastruct. Pro., 2(1–2), 5–12.
Bruneau, M., et al. (2003). “A framework to quantitatively assess and enhance the seismic resilience of communities.” Earthquake Spectra, 19(4), 733–752.
Buhl, J., et al. (2006). “Topological patterns in street networks of self-organized urban settlements.” Eur. Phys. J. B, 49(4), 513–522.
Centre for Research on the Epidemiology of Disasters (CRED). (2009). “Natural disaster trends: World 1900–2009.” 〈http://www.emdat.be/naturaldisasters-trends〉 (July 5, 2010).
Centre for Water Systems. (2007). “CWS benchmarks.” 〈http://centres.exeter.ac.uk/cws/benchmarks〉 (Apr. 20, 2010).
Crucitti, P., Latora, V., and Marchiori, M. (2005). “Locating critical lines in high-voltage electrical power grids.” Fluctuation Noise Lett., 5(2), L201–L208.
Csárdi, G., and Nepusz, T. (2006). “The igraph software package for complex network research.” InterJ. Complex Syst., 1695, 1–9.
Csárdi, G., and Nepusz, T. (2010). “Igraph reference manual” 〈http://igraph.sourceforge.net/documentation.html〉 (Apr. 20, 2011).
Dandy, G. C., Simpson, A. R., and Murphy, L. J. (1996). “An improved genetic algorithm for pipe network optimization.” Water Resour. Res., 32(2), 449–458.
Deuerlein, J. W. (2008). “Decomposition model of a general water supply network graph.” J. Hydraul. Eng., 134(6), 822–832.
Diestel, R. (2005). Graph theory, Springer, New York.
Donetti, L., Neri, F., and Munoz, M. A. (2006). “Optimal network topologies: Expanders, cages, ramanujan graphs, entangled networks and all that.” J. Stat. Mech., 2006, P08007.
Dueñas-Osorio, L., and Vemuru, S. M. (2009). “Cascading failures in complex infrastructure systems.” Struct. Saf., 31, 157–167.
Estrada, E. (2006). “Network robustness to targeted attacks: The interplay of expansibility and degree distribution.” Eur. Phys. J. B, 52(4), 563–574.
Farmani, R., Savic, D. A., and Walters, G. A. (2004). “EXNET benchmark problem for multi-objective optimization of large water systems.” Modell. Control Participatory Plann. Managing Water Syst., Proc. IFAC Workshop, Librerie Universitarie Milanesi, Milan, Italy.
Fiedler, M. (1973). “Algebraic connectivity of graphs.” Czech. Math. J., 23(2), 298–305.
Ghosh, A., and Boyd, S. (2006). “Growing well-connected graphs.” Proc, 45th IEEE Conf. on Decision and Control, IEEE.
Goulter, I. C. (1987). “Current and future use of systems analysis in water distribution network design.” Civ. Eng. Syst., 4(4), 175–184.
Gupta, R., and Prasad, T. D. (2000). “Extended use of linear graph theory for analysis of pipe networks.” J. Hydraul. Eng., 126(1), 56–62.
Hashimoto, T., Loucks, D. P., and Stedinger, J. R. (1982). “Robustness of water resources systems.” Water Resour. Res., 18(1), 21–26.
Holmgren, A. J. (2006). “Using graph models to analyze the vulnerability of electric power networks.” Risk Anal., 26(4), 955–969.
Jacobs, P., and Goulter, I. C. (1988). “Evaluation of methods for decomposition of water distribution networks for reliability analysis.” Civ. Eng. Syst., 5(2), 58–64.
Jacobs, P., and Goulter, I. C. (1989). “Optimization of redundancy in water distribution networks using graph theoretic principles.” Eng. Optim., 15(1), 71–82.
Jamakovic, A., and Uhlig, S. (2007). “On the relationship between the algebraic connectivity and graphs robustness to node and link failures.” Proc., 3rd EURO-NGI Conf. on Next Generation Internet Network, Trondheim, Norway, 96–102.
Jamakovic, A., and Uhlig, S. (2008). “On the relationships between topological metrics in real-world networks.” Networks Heterog., 3(2), 345–359.
Kapelan, Z., Savic, D. A., and Walters, G. A. (2003). “Multi-objective sampling design for water distribution model calibration.” J. Water Resour. Plan. Manage., 129(6), 466–479.
Kapelan, Z., Savic, D. A., Walters, G. A., and Babayan, A. V. (2006). “Risk- and robustness-based solutions to a multi-objective water distribution system rehabilitation problem under uncertainty.” Water Sci. Technol., 53(1), 61–75.
Kesavan, H. K., and Chandrashekar, M. (1972). “Graph-theoretical models for pipe network analysis.” J. Hydraul. Div., 98(2), 345–364.
Kessler, A., Ormsbee, L., and Shamir, U. (1990). “A methodology for least-cost design of invulnerable water distribution networks.” Civ. Eng. Syst., 7(1), 20–28.
Lippai, I. (2005). “Colorado Springs utilities case study: Water system calibration/optimization.” Proc., Pipeline Division Specialty Conf., 1058–1070.
Maier, H. R., et al. (2003). “Ant colony optimization for design of water distribution systems.” J. Water Resour. Plan. Manage., 129(3), 200–209.
Masucci, A. P., Smith, D., Crooks, A., and Batty, M. (2009). “Random planar graphs and the London street network.” Eur. Phys. J. B, 71(2), 259–271.
Mohar, B. (1991). “The Laplacian spectrum of graphs.” Graph theory, combinatorics and applications, Vol. 2, Y. Alavi, et al., eds., Wiley, New York, 871–898.
Newman, M. E. J. (2003). “The structure and function of complex networks.” SIAM Rev., 45, 167–256.
Newman, M. E. J. (2010). Networks, an introduction, Oxford University Press, New York.
Ostfeld, A. (2004). “Reliability analysis of water distribution systems.” J. Hydroinf., 6(4), 281–294.
Ostfeld, A. (2005). “Water distribution systems connectivity analysis.” J. Water Resour. Plan. Manage., 131(1), 58–66.
Ostfeld, A., and Shamir, U. (1993). “Incorporating reliability in optimal design of water distribution networks: Review and new concepts.” Reliab. Eng. Syst. Saf., 42(1), 5–11.
Ostfeld, A., and Shamir, U. (1996). “Design of optimal reliable multi-quality water-supply systems.” J. Water Resour. Plan. Manage., 122(5), 322–333.
R Development Core Team. (2009). R: A language and environment for statistical computing, R Foundation for Statistical Computing, Vienna, Austria. ISBN 3-900051-07-0, 〈http://www.Rproject. org〉 (April 20, 2010).
Savic, D. A., and Walters, G. A. (1997). “Genetic algorithms for least-cost design of water distribution networks.” J. Water Resour. Plan. Manage., 123(2), 67–77.
Strogatz, S. H. (2001). “Exploring complex networks.” Nature, 410, 268–276.
Todini, E. (2000). “Looped water distribution network design using a resilience index based heuristic approach.” Urban Water, 2(2), 115–122.
Van Zyl, J. E., Savic, D. A., and Walters, G. A. (2004). “Operational optimization of water distribution systems using a hybrid genetic algorithm.” J. Water Resour. Plan. Manage., 130(2), 160–170.
Walski, T. (1993). “Water distribution valve topology for reliability analysis.” Reliab. Eng. Syst. Saf., 42(1), 21–27.
Walski, T. M., et al. (1987). “Battle of the network models: epilogue.” J. Water Resour. Plan. Manage., 113(2), 191–203.
Wasserman, S., and Faust, K. (1994). Social network analysis: Methods and applications, Cambridge Univ., Cambridge, U.K.
Xu, C., and Goulter, I. C. (1999). “Reliability-based optimal design of water distribution network.” J. Water Resour. Plan. Manage., 125(6), 352–362.
Zio, E., and Sansavini, G. (2007). “Service reliability analysis of a tramway network.” Risk, reliability, and societal safety, Taylor and Francis Group, London, 907–913.
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 138 • Issue 2 • March 2012
Pages: 153 - 161
Copyright
© 2012 American Society of Civil Engineers.
History
Received: Jun 1, 2010
Accepted: Apr 30, 2011
Published online: May 13, 2011
Published in print: Mar 1, 2012
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.