A Community-Structure-Based Method for Estimating the Fractal Dimension, and its Application to Water Networks for the Assessment of Vulnerability to Disasters

In the last decades, in several fields, from statistical physics to computer science and to biology, the topological and dynamical aspects of systems have been investigated from the perspective of the Complexity Science. Accordingly, Complex Networks Theory (CNT) has been the focus of intensive research (D'Agostino and Scala 2014) for analysing real-world systems (Pagani and Aiello 2013; Fiscon et al. 2018). Complexity Science is an emerging approach to research concerning with complex systems characterized by dynamic and nonlinear relationships occurring between their components and exhibiting non-trivial global behaviours at larger scales. Water distribution systems (WDSs) can also be modelled as spatial complex networks and studied within the approach of the CNT (Giudicianni et al. 2018). WDSs are also among the most important urban infrastructures, delivering drinking and industrial water to metropolitan areas, the operability of which is of crucial importance to ensure social development and economic prosperity. These infrastructures continually face natural and man-made threats that cause economic and social disruption. This leads the operators of water companies to continuously work on improving safety and security, from the design phase (Marinho et al. 2020) for efficiently managing repair crews in emergency circumstances (Wang et al. 2017) and speeding up mitigation actions during disasters (Paez et al. 2018), contaminations (Xin et al. 2017), cyber-attacks (Taormina and Galelli 2018). In addition, as city size increases, these infrastructures are getting ever bigger with an ever more complex behaviour. Consequently, the analysis, the management and the maintenance become difficult tasks to be accomplished, often exacerbated by the lack of site-specific information. CNT has proven to be particularly suitable for the analysis of WDSs, especially in the case of limited information about the system, for unveiling common properties and simplify management and monitoring (Giudicianni et al. 2020).

For testing the proposed approach, nine graphs of WDSs are analyzed; seven out of nine refer to real WDSs and the other two are synthetic (data-file sources in Giudicianni et al. 2018), with size (number of nodes n) ranging between n = 37 and n = 1893 (see Table 2).

According to the values of the robustness metrics listed in Table 2, it is evident that, from a topological point of view, the analysed WDSs are very different from each other, especially in terms of link density q and connectivity λ₂. The choice of working on very different WDSs from a topological viewpoint is crucial for further validating the proposed approach. In Fig. 2, the simulation results obtained by applying the proposed algorithm to estimate the fractal dimension of WDSs are plotted. The existence of power-law relationships between the number of clusters N_C and the average size L_C for all the analysed WDSs is confirmed by the linear regression lines in a log–log plane with coefficient of determinations R² > 0.95. This confirms the spatial self-similarity of WDSs layouts at different scales and in different areas. Accordingly, it can be supposed that also their response (in terms of loss of connectivity) to an event that causes diffuse pipe breakages can be self-similar and a specific attitude to the disconnection can thus be revealed. The last two columns of Table 2 list the values of d_B and F_modal for the analysed WDSs. It is evident that the WDSs, the layout of which is more looped – like Fossolo – show the highest values of F_modal (highest number of pipe failures necessary to disconnect the graph). On the contrary, branched layout WDSs – like Wolf – show the lowest values of F_modal. This agrees with the values of the robustness metrics and their interpretations (Table 1). The study of the relationships between the topological robustness metrics and this new index F_modal, used for expressing the global vulnerability of the WDSs, represents another novel point of the current research.

Fossolo network is characterised by the highest values of link density q, average node degree K and algebraic connectivity λ₂, and the lowest values of average path length l, which lead to suppose that it is the most robust from a topological viewpoint. On the other hand, Wolf network shows the lowest values of q, K, and λ₂, and the second highest value of l, in agreement with the lowest value of F_modal. It is evident that Fossolo also shows the lowest value of d_B while Wolf is characterised by the highest one. Without loss of generality, Fig. 3 reports the frequency histograms of the number of normalised failures necessary to disconnect the network for two of the analysed WDSs. The plots show two different shapes for the histograms, pointing out two different behaviours in response to the same stress conditions for topologically dissimilar WDSs. In Fig. 3a, the frequency distribution has the shape of an asymmetric bell, while in Fig. 3b the histogram resembles a geometric type distribution. For the analysed WDSs, it has been noticed that the bell-shaped histograms are typical of densely looped systems (like Parete), while the geometric types characterise branched (or partly looped) networks (like Matamoros). This aspect further highlights the influence of the topology on the behaviour of WDSs with respect to failures. Such a dissimilarity can be explained by the fact that looped WDSs can be disconnected by both small and big number of failures (depending on where they occur), while branched WDSs are more likely disconnected by small numbers of failures, owing to the absence of highly interconnected zones.

Since the fractal dimension can be considered a measure of network organization, Fig. 4a shows the relationship between d_B and F_modal for the analysed WDSs. It is evident a decreasing trend of d_B as the number of required failures increases, well describing the behaviour of WDSs in terms of leaning to disconnection. Anyway, for some networks this consistency is less clear. In order to enhance this correlation, the fractal dimension d_B has been normalised with respect to the average node degree K, and the trend of d_B/K against F_modal is plotted in Fig. 4b. Different reasons led to choose the average node degree for normalization:

The latter feature assures easily interpretable values of the normalized fractal dimensions. Indeed, using other topological metrics (e.g. average path length, link density, algebraic connectivity, number of nodes composing the graph), for which lower and upper bounds are not well defined, would result in an extremely wide range for the normalized fractal dimension. The normalised fractal dimension d_B/K still decreases as the number of normalised failures increases, but with a clearer trend. Accordingly, WDSs characterised by lower values of d_B/K are less vulnerable to be disconnected (or, equivalently, to be cut) by randomly generated multiple failures. For this reason, the normalised fractal dimension d_B/K can be assumed as a measure of the global vulnerability to pipe failures. Hence, a novel vulnerability index is proposed, called Cut-Vulnerability V_cut, for which higher values indicate higher vulnerability:

The suitability of the proposed Cut-Vulnerability index V_cut has been further validated through the analysis of its relationships with the topological robustness metrics.

Figure 5 shows clear and consistent monotonic trends. Fig. 5a shows that V_cut decreases as the link density q increases; Fig. 5b shows that V_cut increases as the average path length l increases; finally, from Fig. 5c, it is clear that V_cut decreases as the algebraic connectivity λ₂ increases. To further validate the effectiveness of the proposed vulnerability index V_cut with respect to the other topological metrics used as proxies of vulnerability, the Spearman’s correlation coefficient ρ_s (Spearman 1904) between them and F_modal has been calculated. This coefficient quantifies the strength of a monotonic relationship (either decreasing or increasing) linking two data samples when the structure of the relationship is unknown. The values -1 and 1 indicate perfectly negatively and positively correlated variables, respectively. The Spearman’s correlation coefficients ρ_s between F_modal and q, K, l, λ₂, and V_cut are 0.93, 0.42, -0.78, 0.82, and -0.94, respectively, with a significance level α = 0.01. While K and l show the weakest correlations with F_modal, V_cut has the highest absolute value of ρ_s. Furthermore, with respect to the other topological metrics, V_cut index simultaneously considers the global structure of the graphs, i.e. their self-similar feature (through the fractal dimension d_B) and their average level of connectivity (through the average node degree K), providing a more comprehensive information about the structure of the WDSs. This new index highlights how crucial is the combination of connectivity and topological organization for defining network behaviour. Networks with the same connectivity K, but with different values of the fractal dimension d_B, behave differently with respect to failures. In this regard, another contribution of this paper is the analysis of the mutual influence between topology and mechanical failures, and how topology affects the response to pipe failures.

With the aim to study the criticality of water distribution networks facing natural disasters in the frequent case of scarcity of site-specific information and by defining new modelling tools, the present work brings together different fields, such as the statistical physics of complex networks, the topology of water systems and the fractal theory. The fractal structure of WDS layouts has been detected through a novel algorithm, that can be regarded as an approximation of the classical heuristic box-covering algorithms, which exploits the community structure principle. It results to be particularly appealing for application to big-sized systems. The fractal dimension d_B is equal to the exponent of the power-law relationship between the number of clusters necessary for covering the network layout and their average size. The fractality of WDS layouts can be read as a mark of their self-similar topological organization and, consequently, it has been interpreted in terms of their self-similar response to mechanical failures, confirming the crucial role of the topology on the behaviour of water systems facing disasters. The global vulnerability assessment of WDSs under simultaneous failure events, as it could be the case after big disasters (i.e. landslides, floods, sabotages, earthquakes) has been performed. For nine WDSs, several failure scenarios have been generated, unveiling a specific vulnerability for each system, quantified through a novel index F_modal equal to the specific number of random failures that more frequently lead to the disconnection of the system. Additionally, a novel vulnerability index called Cut-Vulnerability V_cut has been defined as the normalized fractal dimension to the average node degree d_B/K. Such index has shown to well describe network topological self-similarity in terms of global vulnerability through its consistency with F_modal and some other topological robustness metrics. The proposed index results particularly interesting in the case of a preliminary assessment of the vulnerability to disasters of water systems, for which geometric and hydraulic information is only partially available. It should be also stressed that during abnormal circumstances the variations of model boundary conditions for the hydraulic simulation become more uncertain and of secondary importance in comparison with the topological changes. This aspect further supports the assessment of the WDS global vulnerability in terms of loss of connectivity. In this regard, simplified methods based on topological knowledge alone, like that proposed and described in this paper, for a preliminary evaluation of WDSs’ vulnerability can represent effective and economic decision-support tools to drive the search for the most disruptive alterations under abnormal events, to prioritize the use of available resources, and consequently to rapidly restore service. Future works will investigate the possibility of applying the novel fractal algorithm to the weighted graph of the water systems, by considering the hydraulic/geometric characteristics of the pipes, in order to better reproduce their physical behaviour. This could reveal hydraulic self-similarity features in the resulting graph and allow simulating targeted attacks by considering the different hydraulic importance of network elements.