Generalized Normalized Cut and Spanning Trees for Water Distribution Network Partitioning
Publication: Journal of Water Resources Planning and Management
Volume 145, Issue 10
Abstract
This study present an efficient graph-theoretical method for automatic design of district metered areas (DMAs) in water distribution networks (WDNs). The proposed method consists of two main parts, WDN partitioning and DMA connection, and is tested on a real-life WDN for which three spectral partitioning methods, multiple weight cases, and two clustering criteria are compared. The efficiency of the proposed DMA connection algorithm with respect to the traditional combinatorial approach is shown for different numbers of established DMAs. The final solution is selected according to a multicriteria evaluation model, which was developed in order to reduce the subjective influence in the selection process and considers hydraulic, cost, and topological criteria. The results show that all three tested spectral partitioning methods, i.e., the ratio cut, normalized cut, and newly proposed generalized normalized cut, are suitable for WDN partitioning and that the quality of the obtained solutions can be further improved by considering appropriate topological and cost-based WDN information in the partitioning process.
Get full access to this article
View all available purchase options and get full access to this article.
Data Availability Statement
The following data, models, or code generated or used during the study are available from the corresponding author by request: code for the automatic DMA design written in MATLAB 2015a.
References
Alvisi, S. 2015. “A new procedure for optimal design of district metered areas based on the multilevel balancing and refinement algorithm.” Water Resour. Manage. 29 (12): 4397–4409. https://doi.org/10.1007/s11269-015-1066-z.
Alvisi, S., and M. Franchini. 2014. “Heuristic procedure for the automatic creation of district metered areas in water distribution systems.” Urban Water J. 11 (2): 137–159. https://doi.org/10.1080/1573062X.2013.768681.
Arthur, D., and S. Vassilvitskii. 2007. “K-means++: The advantages of careful seeding.” In Proc., 18th Annual ACM-SIAM Symp. on Discrete Algorithms 1027–1035. Philadelphia: Society for Industrial and Applied Mathematics.
Brentan, B. M., E. Campbell, T. Goulart, D. Manzi, G. Meirelles, M. Herrera, J. Izquierdo, and E. Luvizotto Jr. 2018. “Social network community detection and hybrid optimization for dividing water supply into district metered areas.” J. Water Resour. Plann. Manage. 144 (5): 04018020. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000924.
Brentan, B. M., E. Campbell, G. Meirelles, E. Luvizotto Jr., and J. Izquierdo. 2017. “Social network community detection for DMA creation: Criteria analysis through multilevel optimization.” Math. Prob. Eng. 2017: 1–12. https://doi.org/10.1155/2017/9053238.
Campbell, E., J. Izquierdo, I. Montalvo, and R. Pèrez-Garcìa. 2016a. “A novel water supply network sectorization methodology based on a complete economic analysis, including uncertainties.” Water 8 (5): 179. https://doi.org/10.3390/w8050179.
Campbell, E., J. Izquierdo, I. Montalvo, R. Pèrez-Garcìa, and M. Tavera. 2016b. “A flexible methodology to sectorize water supply networks based on social network theory concepts and on multi-objective optimization.” J. Hydroinf. 18 (1): 62–76. https://doi.org/10.2166/hydro.2015.146.
Creaco, E., M. Franchini, and E. Todini. 2016c. “Generalized resilence and failure indices for use with pressure-driven modeling and leakage.” J. Water Resour. Plann. Manage. 142 (8): 04016019. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000656.
Creaco, E., M. Franchini, and E. Todini. 2016d. “The combined use of resilience and loop diameter uniformity as a good indirect measure of network reliability.” Urban Water J. 13 (2): 167–181. https://doi.org/10.1080/1573062X.2014.949799.
De Paola, F., N. Fontana, E. Galdiero, M. Giugni, D. Savic, and G. Sorgenti degli Uberti. 2014. “Automatic multi-objective sectorization of a water distribution network.” Procedia Eng. 89: 1200–1207. https://doi.org/10.1016/j.proeng.2014.11.250.
Diao, K., Y. Zhou, and W. Rauch. 2013. “Automated creation of district metered areas boundaries in water distribution systems.” J. Water Resour. Plann. Manage. 139 (2): 184–190. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000247.
Di Nardo, A., and M. Di Natale. 2010. “A heuristic design support methodology based on graph theory for district metering of water supply networks.” Eng. Optim. 43 (2): 193–211. https://doi.org/10.1080/03052151003789858.
Di Nardo, A., M. Di Natale, S. Chianese, D. Musmarra, and G. F. Santonastaso. 2016. “Combined recursive clustering and partitioning to define optimal DMAs of water distribution networks.” In Proc., 8th Int. Congress on Environmental Modelling and Software, 63. Toulouse, France: International Environmental Modelling and Software Society.
Di Nardo, A., M. Di Natale, C. Giudicianni, R. Greco, and G. F. Santonastaso. 2017a. “Weighted spectral clustering for water distribution network partitioning.” Appl. Network Sci. 2 (1): 19. https://doi.org/10.1007/s41109-017-0033-4.
Di Nardo, A., M. Di Natale, C. Giudicianni, R. Greco, and G. F. Santonastaso. 2018a. “Water distribution network clustering: Graph partitioning or spectral algorithms?” In Vol. 689 of Proc., 6th Int. Conf. on Complex Networks and their Applications: COMPLEX NETWORKS 2017, Studies in Computational Intelligence, 1197–1209. Cham, Switzerland: Springer.
Di Nardo, A., M. Di Natale, C. Giudicianni, D. Musmarra, G. F. Santonastaso, and A. Simone. 2015. “Water distribution system clustering and partitioning based on social network algorithms.” Procedia Eng. 119: 196–205. https://doi.org/10.1016/j.proeng.2015.08.876.
Di Nardo, A., M. Di Natale, C. Giudicianni, G. F. Santonastaso, V. Tzatchkov, and J. M. Rodriguez Varela. 2017e. “Economic and energy criteria for district meter areas design of water distribution networks.” Water 9 (7): 463. https://doi.org/10.3390/w9070463.
Di Nardo, A., M. Di Natale, R. Greco, and G. F. Santonastaso. 2014. “Ant algorithm for smart water network partitioning.” Procedia Eng. 70: 525–534. https://doi.org/10.1016/j.proeng.2014.02.058.
Di Nardo, A., M. Di Natale, G. F. Santonastaso, and S. Venticinque. 2013. “An automated tool for smart water network partitioning.” Water Resour. Manage. 27 (13): 4493–4508. https://doi.org/10.1007/s11269-013-0421-1.
Di Nardo, A., C. Giudicianni, R. Greco, M. Herrera, and G. F. Santonastaso. 2018f. “Applications of graph spectral techniques to water distribution network management.” Water 10 (1): 45. https://doi.org/10.3390/w10010045.
DVGW (Deutsche Vereinigung des Gas- und Wasserfaches). 2003. Arbeitsblatt W 392 Rohrnetzinspektion und Wasserverluste: Maßnahmen, Verfahren und Bewertung. Bonn, Germany: DVGW.
Eliades, D. G., M. Kyriakou, S. Stelios Vrachimis, and M. M. Polycarpou. 2019. “EPANET-MATLAB toolkit: An open-source software for interfacing EPANET with MATLAB.” Proc., 14th Int. Conf. on Computing and Control for the Water Industry. Amsterdam, Netherlands: Computer Control for Water Industry.
Fallis, P., K. Hübschen, E. Oertlè, D. Ziegler, P. Klingel, A. Knobloch, J. Baader, R. Trujillo, and C. Laures. 2011. Guidelines for water loss reduction. A focus on pressure management. Eschborn, Germany: Deutsche Gesellschaft für Internationale Zusammenarbeit (GIZ).
Ferrari, G., and G. Becciu. 2012. “Hybrid graph partitioning approach for dividing a water distribution network into district metered areas.” In Proc., 14th Water Distribution Systems Analysis Conf., 569. Adelaide, Australia: Engineers Australia.
Ferrari, G., D. A. Savic, and G. Becciu. 2014. “Graph-theoretic approach and sound engineering principles for design of district metered areas.” J. Water Resour. Plann. Manage. 140 (12): 04014036. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000424.
Garey, M., and D. S. Johnson. 1972. Computers and intractability: A guide for the theory of NP-completeness. New York: W. H. Freeman.
Gilbert, D., E. Abraham, I. Montalvo, and O. Piller. 2017. “Iterative multistage method for a large water network sectorization into DMAs under multiple design objectives.” J. Water Resour. Plann. Manage. 143 (11): 04017067. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000835.
Hajebi, S., S. Barrett, A. Clarke, and S. Clarke. 2013. “Multi-agent simulation to support water distribution network partitioning.” In Proc., 27th European Simulation and Modelling Conf, 1–6. Lancaster, UK: Lancaster Univ.
Hajebi, S., R. Ehsan, N. Cardozo, S. Barrett, A. Clarke, and S. Clarke. 2016. “Water distribution network sectorisation using graph theory and many-objective optimisation.” J. Hydroinf. 18 (1): 77–95. https://doi.org/10.2166/hydro.2015.144.
Herrera, M., S. Canu, A. Karatzoglou, R. Pèrez-Garcìa, and J. Izquierdo. 2010. “An approach to water supply clusters by semi-supervised learning.” In Proc., iEMSs 4th Biennial Meeting: Int. Congress on Environmental Modelling and Software (iEMSs 2010), 1925–1932. Ottawa: International Environmental Modelling and Software Society.
Herrera, M., J. Izquierdo, R. Pèrez-Garcìa, and I. Montalvo. 2012. “Multi-agent adaptive boosting on semi-supervised water supply clusters.” Adv. Eng. Software 50: 131–136. https://doi.org/10.1016/j.advengsoft.2012.02.005.
Hotz, M. 2015. “Generatespanningtrees(a).” Accessed October 1, 2017. https://www.mathworks.com/matlabcentral/fileexchange/53787-generatespanningtrees-a.
Jung, D., D. G. Yoo, D. Kang, and J. H. Kim. 2016. “Linear model for estimating water distribution distribution reliability.” J. Water Resour. Plann. Manage. 142 (8): 04016022. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000664.
Karypis, G., and V. Kumar. 1999. “A fast and high quality multilevel scheme for partitioning irregular graphs.” SIAM J. Sci. Comput. 20 (1): 359–392. https://doi.org/10.1137/S1064827595287997.
Kozelj, D., M. Gorjup, and M. Kramar Fijavž. 2017. “Uporaba metode spektralnega razbitja grafov za zasnovo merilnih območij v vodovodnem omrežju.” [In Slovenian.] Acta Hydrotechnica 30 (53): 81–96.
Kozelj, D., Z. Kapelan, G. Novak, and F. Steinman. 2014. “Investigating prior parameter distributions in the inverse modelling of water distribution hydraulic models.” Strojniški vestnik 60 (11): 725–734. https://doi.org/10.5545/sv-jme.2014.1741.
Lambert, A. 2003. “Assessing non-revenue water and its components: A practical approach.” Water 21 5 (4): 50–51.
Laucelli, D. B., A. Simone, L. Berardi, and O. Giustolisi. 2017. “Optimal design of district metering areas for the reduction of leakages.” J. Water Resour. Plann. Manage. 143 (6): 04017017. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000768.
Liu, H., D. A. Savic, Z. Kapelan, E. Creaco, and Y. Yuan. 2016. “Reliability surrogate measures for water distribution system design: Comparative analysis.” J. Water Resour. Plann. Manage. 143 (2): 04016072. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000728.
Liu, J., and R. Han. 2018. “Spectral clustering and multicriteria decision for design of district metered areas.” J. Water Resour. Plann. Manage. 144 (5): 04018013. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000916.
Lloyd, S. P. 1982. “Least squares quantization in PCM.” IEEE Trans. Inf. Theory 28 (2): 129–137. https://doi.org/10.1109/TIT.1982.1056489.
Mohar, B., Y. Alavi, G. Chartrand, O. Oellermann, and A. Schwenk. 1992. “The Laplacian spectrum of graphs.” Graph Theory Comb. Appl. 2 (871–898): 12.
Morrison, J., D. Rogers, and S. Tooms. 2007. District metered areas guidance notes. 1st ed. London: Water Loss Task Force, IWA Publications.
QGIS Development Team. 2018. “QGIS geographic information system. Open source geospatial foundation project.” Accessed October 1, 2018. http://qgis.osgeo.org.
Rossman, L. A. 2000. Epanet2 users manual. Cincinnati: USEPA, National Risk Management Research Laboratory.
Salomons, E., O. Skulovich, and A. Ostfeld. 2017. “Battle of water networks DMAs: Multistage design approach.” J. Water Resour. Plann. Manage. 143 (10): 04017059. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000830.
Sela Perelman, L., M. Allen, A. Preis, M. Iqbal, and A. J. Whittle. 2015. “Automated sub-zoning of water distribution systems.” Environ. Modell. Software 65: 1–14. https://doi.org/10.1016/j.envsoft.2014.11.025.
Sempewo, J., A. Pathirana, and K. Vairavamoorthy. 2008. “Spatial analysis tool for development of leakage control zones from the analogy of distributed computing.” In Proc., 10th Annual Water Distribution Systems Analysis Conf., edited by J. E. Van Zyl, A. A. Ilemobade, and H. E. Jacobs, 1–15. Reston, VA: ASCE.
Shi, J., and J. Malik. 2000. “Normalized cuts and image segmentation.” IEEE Trans. Pattern Anal. Mach. Intell. 22 (8): 888–905. https://doi.org/10.1109/34.868688.
Tarjan, R. E. 1974. “A note of finding the bridges of a graph.” Inf. Process. Lett. 2 (6): 160–161. https://doi.org/10.1016/0020-0190(74)90003-9.
Todini, E. 2000. “Looped water distribution networks design using a resilience index based heuristic approach.” Urban Water 2: 115–122. https://doi.org/10.1016/S1462-0758(00)00049-2.
Von Luxburg, U. 2007. “A tutorial on spectral clustering.” Stat. Comput. 17 (4): 395–416. https://doi.org/10.1007/s11222-007-9033-z.
Wei, Y., and C. Cheng. 1992. “Ratio cut partitioning for hierarchical designs.” IEE Trans. Comput.-Aided Des. 10 (7): 911–921. https://doi.org/10.1109/43.87601.
Yen, J. Y. 1971. “Finding the shortest loopless paths in a network.” Manage. Sci. 17 (11): 712–716. https://doi.org/10.1287/mnsc.17.11.712.
Zevnik, J., and D. Kozelj. 2018. “Partition of water distribution networks into district metered areas using a graph theoretical approach.” In Proc., 13th Int. Conf. on Hydroinformatics, edited by G. La Loggia, G. Freni, V. Puleo, and M. De Marchis, 2417–2424. Manchester, UK: EasyChair.
Zhang, Q., Z. Y. Wu, M. Zhao, J. Qi, Y. Huang, and H. Zhao. 2017. “Automatic partitioning of water distribution networks using multiscale community detection and multiobjective optimization.” J. Water Resour. Plann. Manage. 143 (9): 04017057. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000819.
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 145 • Issue 10 • October 2019
Copyright
©2019 American Society of Civil Engineers.
History
Received: Jul 22, 2018
Accepted: Feb 1, 2019
Published online: Jul 19, 2019
Published in print: Oct 1, 2019
Discussion open until: Dec 19, 2019
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.