  Leak detection in urban water distribution networks (WDNs) is challenging
given their scale, complexity, and limited instrumentation. We present an
algorithm for leak detection in WDNs, which involves making additional flow
measurements on-demand, and repeated use of water balance. Graph partitioning
is used to determine the location of flow measurements, with the objective to
minimize the measurement cost. We follow a multi-stage divide and conquer
approach. In every stage, a section of the WDN identified to contain the leak
is partitioned into two or more sub-networks, and water balance is used to
trace the leak to one of these sub-networks. This process is recursively
continued until the desired resolution is achieved. We investigate different
methods for solving the arising graph partitioning problem like integer linear
programming (ILP) and spectral bisection. The proposed methods are tested on
large scale benchmark networks, and our results indicate that on average, less
than 3% of the pipes need to be measured for finding the leak in large
networks.
