The Performance of Spectral Clustering Algorithms on Water Distribution Networks: Further Evidence
Received: 2 June 2022 | Revised: 15 June 2022 | Accepted: 17 June 2022 | Online: 7 August 2022
Corresponding author: F. Belloum
Abstract
The aim of the current paper is to revisit the performance of spectral clustering algorithms for water distribution networks. In the literature, there have been attempts to introduce improved algorithms based on graph theory. We focus on a class of these algorithms that applies the concepts of the spectral clustering approach. We assess the performance of spectral clustering algorithms on a wider range of water network types (i.e. large, medium, and small sized networks) using a wider range of clustering methods (both partitioning and hierarchical) and performance indicators. Our findings suggest that partitioning methods, such as k-means are not consistently efficient in all types of networks. Nonetheless, the Partitioning Around Medoids (PAM) algorithm shows a relatively good performance according to modularity, while the internal indices of k-means and hierarchical clustering algorithms are more efficient. Stability indices show that PAM and CLARA algorithms are more efficient.
Keywords:
sectorization, clustering methods, spectral clustering algorithmsDownloads
References
K. B. Adedeji, Y. Hamam, B. T. Abe, and A. M. Abu-Mahfouz, "Pressure Management Strategies for Water Loss Reduction in Large-Scale Water Piping Networks: A Review," in Advances in Hydroinformatics, P. Gourbesville, J. Cunge, and G. Caignaert, Eds. New York, NY, USA: Springer, 2018, pp. 465–480. DOI: https://doi.org/10.1007/978-981-10-7218-5_33
S. Ates, "Hydraulic modelling of closed pipes in loop equations of water distribution networks," Applied Mathematical Modelling, vol. 40, no. 2, pp. 966–983, Jan. 2016. DOI: https://doi.org/10.1016/j.apm.2015.06.017
A. Di Nardo and M. Di Natale, "A Design Support Methodology for District Metering of Water Supply Networks," in 12th Annual Conference on Water Distribution Systems Analysis, Arizona, USA, Sep. 2010, pp. 870–887.
H. E. Mutikanga, S. K. Sharma, and K. Vairavamoorthy, "Methods and Tools for Managing Losses in Water Distribution Systems," Journal of Water Resources Planning and Management, vol. 139, no. 2, pp. 166–174, Mar. 2013. DOI: https://doi.org/10.1061/(ASCE)WR.1943-5452.0000245
A. Di Nardo, M. di Natale, G. Santonastaso, and S. Venticinque, "Graph partitioning for automatic sectorization of a water distribution system," in Proceedings of 11th International Conference on Computing and Control for Water Industry (CCWI). Urban Water Management: Challenges and Opportunities, Jan. 2011, pp. 841–846.
X. Khoa Bui, M. S. Marlim, and D. Kang, "Water Network Partitioning into District Metered Areas: A State-Of-The-Art Review," Water, vol. 12, no. 4, Apr. 2020, Art. no. 1002. DOI: https://doi.org/10.3390/w12041002
J. Saldarriaga et al., "Battle of the Water Networks District Metered Areas," Journal of Water Resources Planning and Management, vol. 145, no. 4, Apr. 2019. DOI: https://doi.org/10.1061/(ASCE)WR.1943-5452.0001035
P. Korkana, V. Kanakoudis, M. Patelis, and K. Gonelas, "Forming District Metered Areas in a Water Distribution Network Using Genetic Algorithms," Procedia Engineering, vol. 162, pp. 511–520, Jan. 2016. DOI: https://doi.org/10.1016/j.proeng.2016.11.095
L. Perelman and A. Ostfeld, "Topological clustering for water distribution systems analysis," Environmental Modelling & Software, vol. 26, no. 7, pp. 969–972, Jul. 2011. DOI: https://doi.org/10.1016/j.envsoft.2011.01.006
J.-P. Attal, "Nouveaux algorithmes pour la detection de communautes disjointes et chevauchantes bases sur la propagation de labels et adaptes aux grands graphes.," Ph.D. dissertation, Universite de Cergy Pontoise, Cergy-Pontoise, France, 2017.
A. Di Nardo, C. Giudicianni, R. Greco, M. Herrera, and G. F. Santonastaso, "Applications of Graph Spectral Techniques to Water Distribution Network Management," Water, vol. 10, no. 1, Jan. 2018, Art. no. 45. DOI: https://doi.org/10.3390/w10010045
V. G. Tzatchkov, V. H. Alcocer-Yamanaka, V. G. Tzatchkov, and V. H. Alcocer-Yamanaka, "Graph theory based single and multiple source water distribution network partitioning," Tecnologia y ciencias del agua, vol. 10, no. 6, pp. 197–221, Dec. 2019. DOI: https://doi.org/10.24850/j-tyca-2019-06-08
E. Price and A. Ostfeld, "Optimal Water System Operation Using Graph Theory Algorithms," Procedia Engineering, vol. 89, pp. 502–508, Jan. 2014. DOI: https://doi.org/10.1016/j.proeng.2014.11.245
U. von Luxburg, "A tutorial on spectral clustering," Statistics and Computing, vol. 17, no. 4, pp. 395–416, Dec. 2007. DOI: https://doi.org/10.1007/s11222-007-9033-z
B. Gharnali and S. Alipour, "MRI Image Segmentation Using Conditional Spatial FCM Based on Kernel-Induced Distance Measure," Engineering, Technology & Applied Science Research, vol. 8, no. 3, pp. 2985–2990, Jun. 2018. DOI: https://doi.org/10.48084/etasr.1999
H. Alizadeh and B. M. Bidgoli, "Introducing A Hybrid Data Mining Model to Evaluate Customer Loyalty," Engineering, Technology & Applied Science Research, vol. 6, no. 6, pp. 1235–1240, Dec. 2016. DOI: https://doi.org/10.48084/etasr.741
S. P. Singh and S. C. Sharma, "A Novel Energy Efficient Clustering Algorithm for Wireless Sensor Networks," Engineering, Technology & Applied Science Research, vol. 7, no. 4, pp. 1775–1780, Aug. 2017. DOI: https://doi.org/10.48084/etasr.1277
B. Nica, A Brief Introduction to Spectral Graph Theory. Zürich, Switzerland: European Mathematical Society, 2018. DOI: https://doi.org/10.4171/188
R. Horaud, "A Short Tutorial on Graph Laplacians, Laplacian Embedding, and Spectral Clustering," 2009.
Y. P. Raykov, A. Boukouvalas, F. Baig, and M. A. Little, "What to Do When K-Means Clustering Fails: A Simple yet Principled Alternative Algorithm," PLOS ONE, vol. 11, no. 9, Aug. 2016, Art. no. e0162259. DOI: https://doi.org/10.1371/journal.pone.0162259
R. Han and J. Liu, "Spectral Clustering and Genetic Algorithm for Design of District Metered Areas in Water Distribution Systems," Procedia Engineering, vol. 186, pp. 152–159, Jan. 2017. DOI: https://doi.org/10.1016/j.proeng.2017.03.221
X. Jin and J. Han, "K-Medoids Clustering," in Encyclopedia of Machine Learning, C. Sammut and G. I. Webb, Eds. Boston, MA, USA: Springer, 2010, pp. 564–565. DOI: https://doi.org/10.1007/978-0-387-30164-8_426
I. Tyuryukanov, J. Quiros-Tortos, M. Naglic, M. Popov, M. A. M. M. van der Meijden, and V. Terzija, "A post-processing methodology for robust spectral embedded clustering of power networks," in 17th International Conference on Smart Technologies, Ohrid, Macedonia, Jul. 2017, pp. 805–809. DOI: https://doi.org/10.1109/EUROCON.2017.8011221
A. Candelieri, D. Conti, and F. Archetti, "Improving Analytics in Urban Water Management: A Spectral Clustering-based Approach for Leakage Localization," Procedia - Social and Behavioral Sciences, vol. 108, pp. 235–248, Jan. 2014. DOI: https://doi.org/10.1016/j.sbspro.2013.12.834
J. L. Diaz, M. Herrera, J. Izquierdo, I. Montalvo, and R. Perez, "A Particle Swarm Optimization derivative applied to cluster analysis," in 4th international congress on environmental modelling and software, Barcelona, Spain, Jul. 2008.
R. J. Sanchez-Garcia et al., "Hierarchical Spectral Clustering of Power Grids," IEEE Transactions on Power Systems, vol. 29, no. 5, pp. 2229–2237, Sep. 2014. DOI: https://doi.org/10.1109/TPWRS.2014.2306756
A. K. Patnaik, P. K. Bhuyan, and K. V. Krishna Rao, "Divisive Analysis (DIANA) of hierarchical clustering and GPS data for level of service criteria of urban streets," Alexandria Engineering Journal, vol. 55, no. 1, pp. 407–418, Mar. 2016. DOI: https://doi.org/10.1016/j.aej.2015.11.003
S. Emmons, S. Kobourov, M. Gallant, and K. Borner, "Analysis of Network Clustering Algorithms and Cluster Quality Metrics at Scale," PLOS ONE, vol. 11, no. 7, Jun. 2016, Art. no. e0159161. DOI: https://doi.org/10.1371/journal.pone.0159161
O. Giustolisi and L. Ridolfi, "New Modularity-Based Approach to Segmentation of Water Distribution Networks," Journal of Hydraulic Engineering, vol. 140, no. 10, Oct. 2014, Art. no. 04014049. DOI: https://doi.org/10.1061/(ASCE)HY.1943-7900.0000916
J. Handl and J. Knowles, "Exploiting the Trade-off — The Benefits of Multiple Objectives in Data Clustering," in Evolutionary Multi-Criterion Optimization, Guanajuato, Mexico, Mar. 2005, pp. 547–560. DOI: https://doi.org/10.1007/978-3-540-31880-4_38
G. Brock, V. Pihur, S. Datta, and S. Datta, "clValid: An R Package for Cluster Validation," Journal of Statistical Software, vol. 25, no. 4, pp. 1–22, Mar. 2008. DOI: https://doi.org/10.18637/jss.v025.i04
J. C. Dunn, "Well-Separated Clusters and Optimal Fuzzy Partitions," Journal of Cybernetics, vol. 4, no. 1, pp. 95–104, Jan. 1974. DOI: https://doi.org/10.1080/01969727408546059
V. V. Ryazanov, "Collective Solutions on Sets of Stable Clusterings," in Recent Applications in Data Clustering, H. Pirim, Ed. London, UK: IntechOpen, 2018, pp. 221–236. DOI: https://doi.org/10.5772/intechopen.76189
H. Liu, M. Zhao, C. Zhang, and G. Fu, "Comparing Topological Partitioning Methods for District Metered Areas in the Water Distribution Network," Water, vol. 10, no. 4, Apr. 2018, Art. no. 368. DOI: https://doi.org/10.3390/w10040368
E. Pournaras, R. Taormina, M. Thapa, S. Galelli, V. Palleti, and R. Kooij, "Cascading Failures in Interconnected Power-to-Water Networks," ACM SIGMETRICS Performance Evaluation Review, vol. 47, no. 4, pp. 16–20, Dec. 2020. DOI: https://doi.org/10.1145/3397776.3397781
D. Gilbert, E. Abraham, I. Montalvo, and O. Piller, "Iterative Multi-Stage Method for a Large Water Network Sectorization into DMAs under Multiple Design Objectives," Journal of Water Resources Planning and Management, vol. 143, no. 11, Nov. 2017, Art. no. 04017067. DOI: https://doi.org/10.1061/(ASCE)WR.1943-5452.0000835
Downloads
How to Cite
License
Copyright (c) 2022 F. Belloum, L. Houichi, M. Kherouf
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain the copyright and grant the journal the right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) after its publication in ETASR with an acknowledgement of its initial publication in this journal.
