Keywords: clustering, graph theory, kernel methods, multi-agent systems, water supply networks.

Division of water supply networks (WSN) into isolated supply clusters is used in the majority of the big cities around the world and aims at improving the management of the whole system. This working philosophy follows a divide and conquer strategy that splits the large highly interconnected distribution network into smaller networks, virtually independent, each of them supplied by a prefixed number of sources. Looking for leaks, detecting water distribution anomalies or carrying out reliability plans, are instances of the aspects that can be technically improved by this reduction of the inspection area [1].

In this paper we propose gathering graphical information and supply constraints by a semi-supervised spectral clustering algorithm as an adequate solution to achieve this partition [2]. Spectral clustering produces high-quality cluster configurations on small data sets but has some difficulties in large-scale problems. To approach a solution we propose resampling representative subgraphs of the network. This boosting process is based on multi-agent simulations [1] of virus propagation behavior to obtain a final subgraph of the "infected nodes". Next, we build iteratively semi-supervised supply cluster partitions on them. After each individualized solution we reweight the data to obtain the next sample in an adaptive way. This reweighting method links with the proposed sampling methodology through their relation with the variation of a specific parameter. In addition, a measure of clustering validity, such as the silhouette of each node, becomes very important during the whole process and until the final establishment of the clustering configuration by an adaptive voting procedure.

The proposal, tested in a real-world network, allows us to conclude that the methodology developed , which uses both graphical and vectorial information, is robust and is able to partition large size WSNs.

1

J. Izquierdo, M. Herrera, I. Montalvo, R. Pérez-García, "Agent-based division of water distribution systems into District Metered Areas", Proc. of International Conference on Software Data Technologies, 83-90, Sofia, 2009.

2

M. Herrera, S. Canu, A. Karatzoglou, R. Pérez-García, J. Izquierdo, "An approach to water supply clusters by Semi-supervised learning", Proc. of International Congress of Environment Modeling and Software, Ottawa, 2010, accepted.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £125 +P&P)