Coupling Modularity Optimization and Spectral Clustering of Water Supply Network Partition Algorithm

Abstract:

In order to reduce the leakage of the water supply network， a coupling modularity optimization and spectral clustering algorithm is proposed to implement pipe network partitioning. First， the modularity optimization algorithm is used in this algorithm to obtain the coarse partition of the maximum modularity in the water supply network. Next， a dual graph is constructed with each partition as a node and the partition connection relationship as an edge. The divisional structure of the pipeline network is affected by the combination of the topology of the pipeline network and the layout of the street， land use， and population distribution. After that， the edge weights are calculated based on the number of points of interest in each district， the average degree of the district， the average pipe diameter， the average pipe length， and the average node elevation. Finally， Laplace matrix decomposition and K-means clustering are used to complete the partition. The experiments verify that the community structure of the pipe network identified by the algorithm is consistent with the actual spatial distribution. A comparison of the algorithm with the modularity optimization and spectral clustering algorithms in the modularity and the number of boundaries indicates that the result obtained by the algorithm is more tightly connected within the partition， the connection between the partitions is sparse， and the boundary pipe is fewer.

Key words:water supply networks;district metered area;modularity;spectral clustering