A Dimensionality-Reduction Strategy to Compute Shortest Paths in Urban Water Networks
Carlo Giudicianni Armando di Nardo Gabriele Oliva Antonio Scala Manuel Herrera






1]Carlo Giudiciannicor1 
[cor1]Corresponding author: 
  Tel.: +39-081-000-0000;
carlo.giudicianni@unicampania.it
1,2]Armando Di Nardo
3]Gabriele Oliva
2]Antonio Scala
4]Manuel Herrera

[1]Dipartimento di Ingegneria, Università degli Studi della Campania 'L. Vanvitelli', via Roma 29, Aversa 81031, Italy
[2]Institute for Complex Systems – Italian National Research Council, via dei Taurini 19, Roma 00185, Italy
[3]Dipartimento di Ingegneria, Università Campus Bio-Medico di Roma, via Álvaro del Portillo 21, Roma 00128, Italy
[4]Institute for Manufacturing – Dept. of Engineering, University of Cambridge, 17 Charles Babbage Rd., CB3 0FS Cambridge, United Kingdom


The efficient computation of shortest paths in complex networks is essential to face new challenges related to critical infrastructures such as a near real-time monitoring and control and the management of big size systems. In particular, using information on the minimum paths in water distribution networks (WDNs) allows to track the diffusion of contaminants and to quantify the resilience and criticality of the system. This is, ultimately, approached by considering dynamically changing path-weights that depend on the flow or on other information available at run-time. These analyses tipically include all the WDN assets but reducing the high degree of physical details with a minimum lost of key information for their performance assessment. This paper proposes a strategy to compute minimum paths that is based on a dimensionality-reduction process. Specifically, the network is partitioned into communities and suitably modified to obtain a reduced complexity representation (e.g., in terms of number of nodes and links). The paper shows how this novel, reduced representation is equivalent to the traditional network on computing the shortest paths. The proposed approach is validated considering two utility networks as case studies. The results show that the proposed method provides the exact solution for the shortest path with a computational-time reduction consistently over 50% and up to 90% for some cases. Furthermore, the application of the proposal on WDNs partitioning shows both hydraulic and economic advantages thanks to their monitoring and controlling at near real-time.



Utility networks Critical infrastructures Water distribution systems Shortest Paths Dimensionality Reduction Clustering Complex networks











§ INTRODUCTION


Modern society is strongly dependent on infrastructure systems (i.e. transportation, power grids, telecommunications, water systems), which support city growth and economic prosperity. These infrastructures continually face natural and man-made threats that cause economic and social disruption, leading their operators to continuously work on improving safety and security and on speeding up mitigation actions. Today, the reliability and performance assessment, continuous operation, monitoring, and protection of critical infrastructures are national priorities for countries worldwide <cit.>. Furthermore, as cities increase in their size, these infrastructures are getting larger and tangled, showing a complex behaviour due to the high degree of interdependency among them. As a consequence, the management of such infrastructures is becoming an arduous task to address, and there is a need to develop new, agile tools and methodologies to analyse and control them. This is especially true for water distribution networks (WDNs), which are among the most important civil networks as they deliver drinking and industrial water to metropolitan areas. WDNs constitute essential and critical infrastructures, as systems whose operability is of crucial importance to ensure social survival and welfare. They must to face two major threats:

    
  * Contamination: water infrastructures are strongly vulnerable to malicious and intentional attacks since they are made up of thousands of  exposed  elements <cit.>; as a consequence, water can be easily polluted by chemical or biological contaminants, which spread all over the system by flowing, with dramatic effects on the citizen health <cit.>;
    
  * Leakages: water infrastructures are constituted by aged buried pipelines, and as a consequence, pipelines are easily eroded by the moist environment. Furthermore, the daily pressure variability strongly stresses the pipes. These factors lead to the failure and burst of the pipes <cit.>, causing leakages and wasting huge amount of water <cit.>.


The downside in the management of such infrastructures is that the underlying details of the physics involved in their functioning complicates the analysis to a relevant extent, making it difficult to achieve useful insights in reasonable time <cit.>. Complexity Science has proven to be a particularly adequate tool for the timely and agile analysis and management of WDNs (and more in general for critical infrastructures) <cit.>, especially in the case of limited information about the system <cit.>. In particular, a complex network representation of infrastructures allows to abstract away from the high degree of physical details of the systems and focus only on a few crucial aspects in a manageable way <cit.>. At this end, knowledge on the minimum paths (eventually considering dynamically changing weights that depend on the flow or on other information available at run-time) allows to track the diffusion of contaminants and quantify the resilience and criticality of the system and its composing elements <cit.>.

The work of <cit.> encompasses an extensive survey of various heuristic shortest path (SP) algorithms developed in the last years. It is worth to mention the interesting strategy adopted for practitioners and applied researchers to exploit network's domain-specific information. This is the case of traffic systems researchers adopting the natural hierarchies of the roads to signiﬁcantly speed up the SP computational time <cit.>. Overall, there are two widely investigated strategies for approximate the SP computation in large-scale complex networks. One of them is the landmark-based method. This requires to pre-compute the shortest paths between special nodes (landmark nodes) and all the other nodes in the network, saving these distances in a database. The shortest-path between two nodes is, then, approximated by combining those distances stored in the database <cit.>. The other one is a topology-based approach. This strategy lies on the structure of networks through their partition into discrete areas <cit.>. In this regard, <cit.> propose an approximated landmark-based method for point-to-point distance estimation in large-scale networks, also adding the partitioning variant. The landmark set is selected for each network area and the shortest paths consequently saved in a database. The Authors also demonstrate that selecting the optimal set of landmark nodes is an NP-hard problem.

This paper proposes a strategy to compute minimum paths, namely Multiscale Shortest Path (MS-SP), that is based on a dimensionality-reduction process. Specifically, we make a network partition into communities and suitably modify such network to obtain a representation with reduced complexity (e.g., in terms of the number of nodes and edges), namely Multiscale Network (MS), but equivalent in terms of computing the shortest paths. The proposed approach is validated considering two real-world WDNs as case studies.

An antecedent of this paper can be found on the work of <cit.> which provides a valid approximation to the shortest path problem for social networks. In such work, the authors propose a combined process for community detection and network reduction, by collapsing communities into nodes of a new network. The proposed algorithm has a similar scope, but the main innovation proposed herein is that the network reduction process identifies a subset of key nodes that lie at the boundary of the communities and transforms the  community into hyper-links connecting such boundary nodes, rather than collapsing the communities in single nodes. As a result, the network collapses into a reduced-size graph were boundary nodes are interconnected by edges that are weighted in a suitable manner to guarantee that the minimum path between two nodes in the original network can be computed in terms of the minimum path between the boundary nodes that are closest to the source and destination, respectively.

Two utility networks validate the proposal. One is the well-known network of Colorado Springs <cit.> at Colorado, US. This network is investigated to facilitate repeating further the proposed MS-SP algorithm. The second case-study corresponds to the operational network supplying water to Alcalá de Henares (Madrid, Spain). In this network is more evident the usefulness of the proposal to speed-up the SP computation in large-scale, urban infrastructure networks. In addition to the advantages of the compuation, the dimensionality-reduction process leads to a novel representation of WDNs where it is even possible to obtain a visualisation of the shortest paths.

The outline of the paper is as follows: in Section <ref> the proposed algorithm is presented from a mathematical point of view. Section <ref> shows the two case studies. Section <ref> reports the simulation results with special emphasis on their associated computational efforts. Section <ref> presents a further application of the algorithm for the management of water networks. The paper closes with a conclusions section which also points out future research directions.



§ METHODS





 §.§ Graphs

Let's G={V,E,W} denote a weighted graph with a finite number n of nodes v_i∈ V with i∈{1,…, n} and edges  from node v_i to node v_j.
For each edge (v_i,v_j)∈ E we denote by w_ij∈ W the associated weight.
A graph is said to be undirected if (v_i,v_j)∈E whenever (v_j,v_i)∈E, and it is said to be directed otherwise. In the following we will consider undirected graphs.
For undirected graphs, we assume the weights satisfy w_ij=w_ji for all (v_i,v_j)∈E.
Let's the weighted adjacency matrix of a graph G={V,E,W} be the n × n matrix A with the same structure as G, i.e., such that A_ij=w_ij if  (v_i,v_j)∈E and A_ij=0, otherwise.
In the case of undirected graphs, matrix A is symmetric.
A path over a graph G={V,E,W}, starting from a node v_i∈ V and ending in a node v_j∈ V, is a subset of links in E that connect v_i and v_j; the length of the path is the sum of the weights associated to the links in the path.
A minimum path that connects v_i and v_j is the path from v_i to v_j of minimum length.
An undirected graph is connected if for each pair of nodes v_i,v_j∈ V there is a path over G that connects them.



 §.§ Shortest path algorithm

One of the most well known algorithms to compute the shortest path between two nodes in a weighted graph is Dijkstra's Algorithm (D-SP) <cit.>, which can be summarized as follows. Given a weighted graph G={V,E,W} with |V|=n nodes, a start node v_s and a goal node v_g, the algorithm keeps track of three variables for each node: 


  * (v_i) which is equal to one if the node has already been visited during the algorithm and is zero otherwise;

  * (v_i) which is the current estimate for the distance of node v_i from the start node v_s;

  * (v_i) which is the identifier of the node immediately before node v_i in the path connecting v_s and v_i.

Moreover, the algorithm keeps track of the node currently being examined, which is referred to as v_*.

During the initialisation phase, the algorithm sets (v_s)=1 and (v_i)=0, for all v_i∈ V∖{v_s}. Moreover, it sets (v_s)=0 and (v_i)=∞, for all v_i∈ V∖{v_s}. Finally, the algorithm selects (v_i)=∅ for all v_i∈ V and  sets v_*=v_s.
Then, the main cycle of the algorithm is executed; such a main cycle is composed of the following conceptual steps:


  Step 1 For all neighbours v_i of v_* such that (v_i)=0 set the distance of node v_i from v_s as the minimum between the previous estimate and the sum of the distance of v_* from v_s and the weight of the link w_* i connecting v_* and v_i, i.e., 

    (v_i)=min{(v_i),(v_*)+w_* i};

moreover, if the distance is updated for node v_i the algorithm keeps track of the fact that the minimum path from v_s to v_i features the edge (v_*,v_i) by setting

    (v_i)=v_*.


  Step 2 Set (v_*)=1 

  Step 3 If (v_t)=1 then stop, the algorithm is terminated.

  Step 4 Otherwise, select the node with minimum current distance among the not visited ones as the new current node, i.e.,

    v_*=v_j,   j=i | (v_i)=0min{(v_i)}

and go back to Step 3.


Notice that a straightforward application of the above algorithm yields a computational complexity 𝒪(|V|^2) where |V| is the number of nodes in the graph; moreover, when the graph is particularly sparse, i.e., when |E|≪ |V|(|V|-1)/2, where |E| is the number of edges,  it is possible to reduce complexity by using an implementation that relies on data structures such as the so-called Fibonacci heaps  <cit.>.




 §.§ Clustering approach

A network community detection algorithm <cit.> can be used in case the initial partition of the network is not available. These communities (clusters) are formed by grouping elements with similar characteristics or with a higher connection density than that external to the community. There is a large set of community detection algorithms proposed in literature. 
In this paper the Louvain method <cit.> is adopted, which uses an iterative process to improve the scalability of the overall community detection. Louvain algorithm is a heuristic method based on modularity optimisation <cit.>. In particular, it is divided in two iteratively repeated phases. 


    
  * The algorithm starts assigning a different community to each node of the network, then, for each node i the neighbour j is considered and the gain of modularity that would take place by removing i from its community and by placing it in the community of j is evaluated. After that, the node i is placed in the community for which this gain is maximum. The process is applied for all nodes until no further improvement can be achieved. The first phase stops when a local maxima of the modularity is attained, and no individual move can improve the modularity.
    
  * The second phase of the algorithm builds a new network whose nodes are the communities found during the first phase; once it is completed, the first phase of the algorithm is reapplied to the resulting network. The passes are iterated until the maximum of modularity is attained.


It is known that, the Louvain algorithm appears to run in time 𝒪(|E|), where |E| is the number of edges in the graph <cit.>.



 §.§ Multiscale Shortest Path (MS-SP) algorithm

Given a graph G={V,E,W}, the proposed approach to calculate the shortest path from a node v_s to a node v_t is based on a dimensionality reduction procedure, where the network is decomposed into clusters and the nodes/edges in each clusters are collapsed in a suitable way that guarantees that the shortest path computed over the resulting graph corresponds to the one on the original graph.

Specifically, we apply the Louvain clustering algorithm to G, decomposing the set of nodes V into q disjoint sets V_1,…,V_q, each corresponding to a cluster.
In the following, we denote by E_i the set of edges in the original edge set E that connect nodes in the same cluster, i.e.,

    E_i={(v_a,v_b)∈ E |  v_a,v_b∈ V_i};

moreover, we define

    Ê_ij={(v_a,v_b)∈ E | v_a∈ V_i  v_b∈ V_j}

and 

    E_ij=Ê_ij⋃Ê_ji.

Finally, we define the set of boundary nodes V_i^b⊆ V_i as the set of nodes in V_i that belong to at least one edge in E_ij for some j∈{1,…,q}∖{i}, i.e.

    V_i^b={v_a∈ V_i |  ∃ (v_a,v_b) ∈ E,   v_b∉V_i}.

 In other words, E_ij is the set of edges that connect nodes in V_i and nodes in V_j, and it holds E_ij=E_ji.
Specifically, by running the clustering procedure described above, the network is decomposed into q clusters.

The dimensionality reduction strategy consists in the construction of a graph

    G={V,E,W},

where V includes the set of boundary nodes and the start and goal nodes, i.e.,

    V={v_s,v_t}⋃_i=1^q V_i^b.

As for the edge set E, we have that

    E=E_⋃E_,

where E_ is the union of the edges connecting boundary nodes, i.e.,

    E_=⋃_i,j∈{1,…,q} E_ij

and E_ is the union of sets E_^i of edges that directly connect the boundary nodes in the i-th cluster. Note that, if the start or goal nodes are in the i-th cluster, then the start or goal nodes are considered as a boundary node.

As for the weights, we select w_ab= w_ab whenever (v_a,v_b)∈E_, while for each  pair of boundary nodes v_a,v_b that belong to the same cluster i (including the start or goal node if they belong to cluster i), we compute the minimum path p^i_ab between v_a and v_b over the subgraph of G induced by considering just the nodes V_i in the i-th cluster and we set the weight as the length of the path p^i_ab, i.e.,

    w_ab=∑_(v_h,v_k)∈ p^i_abw_hk .

At this point, the algorithm finds the minimum path between nodes v_s and v_t by computing  the minimum path between v_s and v_t over G. Note that, by keeping track of the minimum paths involving boundary nodes in each cluster (treating v_s and v_t as boundary nodes), we are able to reconstruct the minimum path over G in terms of the minimum path over G.
 
The algorithm is graphically explained by Figure <ref> in which there are 3 groups: the upper-left cluster contains three boundary nodes (and the start node), the right cluster has three boundary nodes and the lower cluster has two boundary nodes (plus the target node). As a result of the decomposition, we obtain a network with |V|=10 nodes (i.e., the boundary nodes plus the start and goal) and |E|=16 edges; in particular, the four edges connecting nodes in different clusters are kept, while for each pair of boundary (or start/goal) nodes in each cluster a new link is added, whose weight corresponds to the length of the minimum path, computed over the subgraph induced by the nodes in the cluster. At this point, the minimum path is computed by computing the minimum path over G.







 §.§ Correctness of the algorithm

The following theorem establishes that the path found via the proposed algorithm is, indeed, a minimum path.

The minimum path between nodes v_s and v_t over G is equivalent to the one connecting v_s and v_t over the original graph G.


Let's v_s and v_t belonging to the same cluster in G. Then, by construction, the minimum path found over G corresponds to the one over G.

Let's assume now that v_s and v_t belong to different clusters with node sets V_s and V_t. By construction, since the clusters are connected only via edges joining boundary nodes belonging to different clusters, the minimum path joining v_s and v_t in G features a path from v_s to a node v_s'∈ V_s, a path from v_s' to a node v_t'∈ V_t and path from a node v_t' to v_t (note that if v_s=v_s' or v_t=v_t' the path joining them is the empty set).

At this point, we observe that the path connecting v_s to any v_s'∈ V_s and the path connecting v_t to any v_t'∈ V_t are, by construction, minimum paths; similarly, the path connecting any v_s'∈ V_s and v_t'∈ V_t with (recall that we assumed s≠ t) is a minimum path. Hence, by construction, the minimum path found over G corresponds to a minimum path
 p_st=p_ss'⋃ p_s't'⋃ p_t't
 over the original graph, for some v_s'∈ V_s and v_t'∈ V_t.
The proof is complete.




 §.§ Time complexity of the MS-SP algorithm

In the following, it is shown the computational cost of the proposed algorithm. It is important to point out that, the core idea of working on a size-reduced graph does not depending on the chosen clustering algorithm. As a consequence, a faster method can be adopted making the proposed algorithm even more convenient from a computational point of view. 


The computational complexity of the proposed approach, including the clustering procedure and the construction of the reduced graph G, is equal to

    max{𝒪(|E|), 𝒪(n_b^2), 𝒪(∑_i=1^q |V_i|^2 |V_i^b|^2)},

where V_i is the set of nodes in the i-th cluster and V_i^b is the set of boundary nodes in the i-th cluster and n_b=∑_i=1^q |V_i^b| is the cardinality of the set of all boundary nodes identified by applying Louvain algorithm.


The computational complexity of the Louvain method is 𝒪(|E|).
Moreover, once the clusters are formed, we need to scan all the edges to identify the set of boundary nodes, a procedure that requires 𝒪(|E|).

At this point, the proposed algorithm computes the shortest path over the subgraph induced by each cluster among each pair of boundary nodes in that cluster; each cluster has |V_i| nodes, hence the computation of the shortest path from one node in the cluster to all other nodes in the cluster requires O(|V_i|^2), since each cluster has 𝒪( |V_i^b|) distinct pairs of boundary nodes, we have that the computational complexity for each cluster is 𝒪(|V_i|^2 |V_i^b|^2).
Since the clusters are q we get 𝒪(∑_i=1^q |V_i|^2 |V_i^b|^2).

To conclude, the application of Dijsktra's algorithm on the reduced-size network has a complexity 𝒪(n_b^2); the proof follows since the two operations are done in series, hence the computational complexity is
equal to the largest among the computational complexities of the above procedures.


Note that the computational complexity of the computation of the minimum path, after the graph  G has been created is remarkably smaller, being n_b≪|V| for real world networks. Similarly, the complexity of the clustering procedure, although being theoretically upper bounded by 𝒪(|V|^2), is likely to be remarkably smaller,  especially when the graph is sparse and |E|≪|V|(|V|-1)/2, |V|(|V|-1)/2 being the number of edges in a complete graph.

As for the calculation of the minimum paths among the boundary nodes in the same cluster, we observe that there may be instances where complexity is above Dijsktra's algorithm[Consider for instance the case where the graph is full and is arbitrarily divided into 4 clusters with the same number of nodes; in this extreme case V_i^b=V_i and thus the complexity of the proposed algorithm would be 𝒪(|V|^4).]; however the likelihood of facing such instances is nearly zero in the case of WDNs and, in general, for graphs that have high sparsity and modularity. In fact, as discussed in the next remark, for those graphs the complexity of the construction of G is likely to be well below the one of Dijsktra's Algorithm. This fact is experimentally demonstrated in the next section.

Note that the complexity of computing the minimum paths locally at every cluster has a complexity
𝒪(∑_i=1^q |V_i|^2 |V_i^b|^2).
However, especially when the network has a clear modular structure, the number q of clusters is likely to be sublinear[ For instance, in <cit.> it is shown that for real WDNs the optimal number of clusters is q≈ n^0.3.] in |V| (e.g., q=|V|^γ with γ∈(0,1)). Hence, on average, also the cardinality |V_i| of the node set of the clusters  is likely to be sublinear, i.e.,

    |V_i|≈ n/q= |V|^1-γ.
. 
Moreover, the cardinality of V_i^b is likely to satisfy |V_i^b|≪ |V_i| and, in several practical cases, can be assumed to be constant for planar graphs and WDNs (see <cit.>), i.e., |V_i^b|≈𝒪(1).
Hence, in practical cases of interest for this paper, we have 

    𝒪(∑_i=1^q |V_i|^2 |V_i^b|^2)≈𝒪( |V|^1+γ)<𝒪( |V|^2).




Note that the construction of G can be slightly modified in order to be the base for the calculation of all shortest paths. In fact, it is sufficient to compute all shortest paths among every node in each cluster (i.e., requiring a computational complexity 𝒪(∑_i=1^q |V_i|^2 |V_i|^2)=𝒪(∑_i=1^q |V_i|^4)) and storing information on the paths within each cluster. In this way, the graph G for calculating a path from any node v_s to any node v_t can be constructed by considering the links connecting boundary nodes and those connecting the start and goal nodes to the boundary nodes, an operation that requires at most 𝒪(|V|) in the worst case).




§ EXPERIMENTAL STUDY


Urban utilities such as water, gas, or electric power networks can be modelled as quasi-planar graphs (e.g., networks forming vertices wherever two edges cross) with spatially organised weighted graphs G=(V,E,w). In the case of water distribution systems the set V of n vertices/nodes encompasses junctions, water sources and demand points. The set E of m edges/links includes pipes, pump stations, and valves. Eventually, w is a function that assigns a weight to each edge quantifying the physical characteristics (diameter, length, roughness) for each pipe <cit.>. In particular, WDNs are strongly constrained by their geographical embedding <cit.> in that connections between distant nodes are
unlikely to be found, due to physical and economic constraints. 



 §.§ Benchmarking water distribution system

MS-SP is firstly tested on the real medium-size Colorado Springs (US) water utility - which  currently serves a population of about 370,000 inhabitants. Figure <ref> shows its network layout. This encompasses 1,782 junctions and 4 reservoirs (n = 1,786 nodes), 1,985 pipes, 6 pumps and 4 valves (m = 1995 links). Figure <ref> clearly demonstrates the size reduction of the Colorado water network after its transformation into a MS network. 
From a visual analytics point of view, Figure <ref> naturally highlights both the more inter-connected network areas and bottleneck links likely related to most vulnerable parts of the system.





 §.§ Large scale water distribution system

The second case-study corresponds to the large-scale water utility which serves the Spanish city of Alcalá de Henares. It is located 22 miles northeast of the country's capital, Madrid, and it counts on a population of 201,000 inhabitants. The water distribution network model (see Figure <ref>) encompasses 11,473 junctions, 3 reservoirs (n = 11,476 nodes), and 12,454 pipes, (m = 12,454 links).  Figure <ref> shows the corresponding MS network layout. 





§ RESULTS


The first results this section introduces are those corresponding to the topological analysis of the original water network and the MS network, for both case studies. A comparison between the original layout and the collapsed one is carried out in terms of: 


    
  * Links Density q which is the ratio between the total number m of network edges and the maximum number of edges m^*= n(n-1)/2 of a network with n nodes:
                                                           

    q=2m/n(n-1)
  
                                                          
    
  * Average Node Degree K is the average value of the node degree k_i (number of edges concurring in the node) over all nodes n: 


    K=2m/n


    
  * Diameter D <cit.> is defined as the maximum shortest distance (the maximum geodesic length) d_ij between any pair of vertices i to node j (computed as the number of edges along the shortest path connecting them): 


    D=max d_ij


    
  * Average Path Length l <cit.> is the average number of steps along the shortest paths for all possible pairs of nodes in the network: 

    l =2∑ d_ij/n(n-1)


     
  * Algebraic Connectivity λ_2 <cit.> corresponds to the second smallest eigenvalue of graph Laplacian matrix L 
    
     
  * Spectral Gap Δλ <cit.> is the difference between the first and second eigenvalue of the adjacency matrix A.


Table <ref> enumerates the main topological metrics computed for both case studies on the original and the MS network. The total number of links m_b for the MS network is equal to the sum of the boundary links m_ex and the internal hyper-links m_in. The size problem reduction is evident on nodes (from n = 1,786 to n_b = 33 for Colorado and from n = 11,476 to n_b = 114 for Alcalá) and also on links (from m = 1992 to m_b = 83 for Colorado and from m = 12.454 to m_b = 596 for Alcalá). The connectivity K strongly increases for the both the MS network (from K = 2.23 to K = 5.03 for Colorado and from K = 2.17 to K = 10.46 for Alcalá).

The dimensionality reduction working with the MS network makes the network density increases up to 2 orders of magnitude (from q = 0.001 to q = 0.157 for Colorado and from q = 0.0002 to q = 0.0933 for Alcalá). This augmented inter-connectivity is also reflected by the two spectral metrics measuring the robustness of network. The algebraic connectivity and the spectral gap also increase when moving from the original to the MS network, as it is shown in Table <ref>. These changes in the topological metrics reflect the shift in the structure of the MS network which can be regarded now as low interconnected small-world clusters (whose links are the internal hyper-links). In fact, after the size reduction due to the application of the MS-SP algorithm, each cluster of the MS network becomes into a fully connected layout, weakly linked to other clusters by the boundary links. The typical small-world behaviour is also confirmed by the low value of the communication metrics as they are the diameter and the average path length which scale approximately with the log(n), as happens for the small world networks (Table <ref>).



The simulation results for Colorado and Alcalá water utilities are reported in Table <ref> and Table <ref>, respectively. A suitable number of clusters C is taken on both cases to optimise the overall connectivity of the partitioned network, according to the relationship C_opt∝ n^0.28 reported in <cit.>, where C_opt is the optimal number of clusters from a topological point of view. As a result, the number of clusters for Colorado is set to C=8, while C=13 for Alcalá's network. Up to 10 paths are generated by connecting random pairs of source and target to validate the proposed MS-SP algorithm. For each pair, the shortest path is computed by running the code 10 times and averaging the computational time.



MS-SP algorithm provides the exact value of the shortest path between each pairs of randomly generated source and target nodes. This represents a clear advantage with respect to previous methodologies whom provide approximated results. Table <ref> and Table <ref> clearly state the D-SP and the MS-SP provide the same results (difference is equal to zero).



The computational time for D-SP algorithm grows with the distance between source and target nodes. However, computational times for MS-SP show to be a plateau value of an order of magnitude smaller than that D-SP method. This is clearly shown in figures <ref> and <ref> (with the results on Colorado and Alcalá utility networks).






Table <ref> shows the difference in percentage between the D-SP and the proposed MS-SP computational time for Colorado. This difference on time ranges from 66% to 90%. Table <ref> shows the difference in percentage between the D-SP and the proposed MS-SP computational time for Alcalá. This difference on time ranges from 50% to 92%. Both differences on computational time stand as a conspicuous time reduction for computing the shortest path.

The MS-SP algorithm is implemented in Python 3.6. All the simulations were run on a Linux Xubuntu 16.04 PC with 2.13 GHz Intel® Core™ i3 CPU m330 64 GB of memory and 4.00 GB of RAM.



§ DISCUSSION


An appealing by-product of the current research is the Small-World properties of the collapsed layout of the original network which preserves essential information about the system, but it is simultaneously characterised by a dramatically size reduction. Indeed, one of the most useful management strategies for WDNs is the sectorisation, which consists in dividing the system in smaller and monitored districts, connected each other by a few number of pipes. Sectorisation helps the pressure management, the leakage detection and reduction, the spreading reduction of contaminants. For this reason, clustering algorithms have been largely applied in hydraulic engineering to define the optimal configuration of districts that balance the aforementioned positive aspects to the resilience reduction that could happen as consequence of the closure of some boundary pipes (boundary links m_ex in the model). The spatial-temporal variability of the functioning conditions, such as the change in water request all over the system, could invalidate the designed sectorisation, by compromising the performance of the WDN. An adaptive/dynamic approach could be a valid solution, providing the aggregation/desegregation of districts (clusters) according to specific conditions. In this regard, the following constraints should be respected: 

        
  * the new aggregate districts include the former ones without splitting them;
        
  * the previous clustering layout and the devices already installed have to be exploited; 
        
  * the set of new boundary links is included in the set of boundary links of the original partitioning; 


As a consequence of working with the MS network layout the management of the system is simplified. In addition, the new investment costs is minimised, even nullified, and the computational burden of the whole procedure is reduced. This structural knowledge comes in the form of pairwise must-link (boundary links) and cannot link (internal links) constraints to be respected at each step of clustering by means a semi-supervised approach (which is particularly suitable for working with real-world systems if background knowledge about the structure are available).

The MS network implicitly takes into account the aforementioned structural knowledge, thanks to the shift in the structure to a low interconnected small-world clusters. In this way, it is ensured that any clustering algorithm provides a solution in which the novel set of boundary links constitutes a sub-set of the boundary links of the original cluster layout. On top of this, a network community detection algorithm splits a network in such way that each cluster is formed by elements having a high density connection between each other and a lower probability to be connected to items belonging to other clusters. 



The steps of the procedure are shown in Figure <ref>. First, the actual clustering layout of the WDN is detected (see Figure <ref>) and then the corresponding MS network is built (see Figure <ref> in which it is evident the size reduction of the WDN) This figure also shows the key elements, such as the boundary nodes of each cluster (highlighted by their corresponding district colour at Figure Figure <ref>), the boundary links (bold black line), and the internal links (thin dashed grey line). The set of hyper-links (boundary links and internal links) is crucial for automatically implementing the semi-supervised clustering during the aggregation phase. Boundary links represent the connectivity between different clusters, while the internal links constitute the internal connectivity of each cluster (according to the shortest path linking each pairs of boundary nodes belonging to the same cluster). After that, the previous districts are aggregated in the MS network (see Figure <ref>), by applying a clustering algorithm to provide the new clustering layout. Finally, in Figure <ref> the new district configuration is shown, with the new bigger clusters that perfectly include the former ones (avoiding to split them), and the boundary set which constitutes a sub-set of the previous one. This dynamic aggregation / disaggregation process ensures that the districts in each phase are kept in control, exploiting the devices already installed in the WDN.




§ CONCLUSIONS


This paper proposes a novel method to efficiently solve the shortest path problem for large-scale water networks (and other utility networks), showing the potentialities on its application to their management and protection. The algorithm is based on a community structure principle, which aids to collapse the original network into a limited set of key elements. This is made through the novel concept of a multiscale (MS) network that reduces the original system into a series of interconnected, landmark, nodes. These landmark nodes are connected by a family of links coming both from the original network and the scale process where links and nodes are aggregated into hyper-links. The hyper-links are weighted by the shortest-path distances between their corresponding extreme nodes. The MS network structure easier the shortest path computation as the network's dimensionality is significantly reduced. Computing the shortest path is broken down to be done in several but smaller areas instead of directly using the whole original network. 
The simulation results over two urban water utilities confirm the efficiency of the proposed multiscale shortest path algorithm. This provides an exact solution for the problem in a significantly lower computational time than using Dijkstra's algorithm. The approach conveniently scales to big-size networks.
The reduced size of the multiscale network coming from the application of the proposed algorithm results in a dramatic advantage for speeding up and simplifying the management of water systems by means the definition of optimal metered districts.

Further works will benefit of this process since, in general, links connecting key nodes are often closed (i.e. most of the boundary pipes connecting nodes belonging to different network areas). In addition to utility networks applications, the multiscale shortest path usefulness extends to critical infrastructures such as transportation, communication, logistic and supply networks. The proposal will also improve the communication speed in general big-size networked systems and will back-up further near real-time operations. 



model2-names


