The Performance of Spectral Clustering Algorithms on Water Distribution Networks: Further Evidence

Authors

  • F. Belloum Laboratory of Civil and Hydraulic Engineering, Civil and Hydraulic Engineering Department, University of Guelma, Algeria
  • L. Houichi Department of Hydraulic Engineering, Faculty of Technology, University of Batna 2, Algeria
  • M. Kherouf Laboratory of Civil and Hydraulic Engineering, Civil and Hydraulic Engineering Department, University of Guelma, Algeria
Volume: 12 | Issue: 4 | Pages: 9056-9062 | August 2022 | https://doi.org/10.48084/etasr.5116

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 algorithms

Downloads

Download data is not yet available.

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

[1]
Belloum, F., Houichi, L. and Kherouf, M. 2022. The Performance of Spectral Clustering Algorithms on Water Distribution Networks: Further Evidence. Engineering, Technology & Applied Science Research. 12, 4 (Aug. 2022), 9056–9062. DOI:https://doi.org/10.48084/etasr.5116.

Metrics

Abstract Views: 503
PDF Downloads: 458

Metrics Information