# Avalanche Entropy as an Information-Theoretic approach to Analyze the Effect of Cascading Failures in a Multiplex Transportation Network

Om Roy, Guillaume Bouleux, Giacomo Kahn, Aurelie Charles

► To cite this version:

Om Roy, Guillaume Bouleux, Giacomo Kahn, Aurelie Charles. Avalanche Entropy as an Information-Theoretic approach to Analyze the Effect of Cascading Failures in a Multiplex Transportation Network. 14th International Conference on Complex Networks and their Applications (Complex Networks 2024), Dec 2024, Istanbul, Turkey. hal-04818807

HAL Id: hal-04818807

https://hal.science/hal-04818807v1

Submitted on 4 Dec 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# Avalanche Entropy as an Information-Theoretic approach to Analyze the Effect of Cascading Failures in a Multiplex Transportation Network

Om Roy¹,², Guillaume Bouleux¹, Giacomo Kahn¹, and Aurélie Charles¹

¹ Université Jean Monnet Saint-Etienne, INSA Lyon, Université Lumière Lyon 2, Université
Claude Bernard Lyon 1, DISP UR4570, F-69007, Lyon, France

² Computer and Information Sciences, University of Strathclyde, Glasgow, UK

o.roy.2022@uni.strath.ac.uk, guillaume.bouleux@insa-lyon.fr,
giacomo.kahn@univ-lyon2.fr, a.charles@univ-lyon2.fr

## 1 Introduction

The quantification of robustness of multi-modal transport systems has been an area of particular research interest in recent years [1, 2]. More specifically, it is of interest to uncover specific routes or modes of transport that may be particularly vulnerable. This has various important applications, for example, in resource allocation during humanitarian crises [3, 4]. In these scenarios we have to consider not only the individual impact of a loss of a route but also its resulting effect on other routes in the network. We must also consider the effect of switching modes of transport in terms of flow re-distribution and capacity overflows. Using Cascading failures as a medium for this seems like a natural choice [5, 6].

Previous research, however, has not considered the effect on the overall information flow of network when the loss of a route causes a cascading failure. While subsets of node and edge centrality measures such as degree and betweenness centrality have been used to determine important actors in the network, these do not consider the entire topology of the network, including its dynamics [7]. It is well established that key structural components in a network are often crucial for information flow, though not always vice versa. Consequently, spectral entropy can reveal vulnerable and critical components in a network [8].

In this preliminary study, we introduce Avalanche Entropy (AE), a novel measure of edge importance in multiplex systems, leveraging recent advances in information theory tailored for complex networks. AE assesses edge significance by analyzing cascading failures, flow redistribution, and their impact on information dynamics. We demonstrate the practical utility of AE by applying it to a multiplex transportation network in Haiti, showcasing its effectiveness in a real-world scenario.

## 2 Multiplex Avalanche Entropy as a Measure of Robustness

We assume here that the multiplex network represents transportation efficiency between cities, with larger edge weights indicating more efficient routes.
## 2.1 Cascading Failures

Robustness against attacks and failures is a key research area, often focused on single-layer networks. However, real-world systems, like transportation networks, involve multiple layers of interaction. Perturbations in one layer can trigger cascading failures across the entire network, leading to widespread disruptions. To study this, we use the local weighted flow redistribution rule (LWFRR) to simulate the impact of edge failures [9, 10]. The capacity of an edge, proportional to its initial load $e_{ij}^M$, is defined as $C_{ij}^M = (1 + \alpha)e_{ij}^M$, where $\alpha \in \mathbb{R}$. There are two scenarios for edge failures:

1. If an edge $e_{ij}$ fails in one layer, a fraction $z$ of its weight is redistributed to its replicas across layers according to $z \cdot \frac{e_{ij}}{N-1}$. The remaining $(1-z)$ is distributed among

neighbors in the current layer such as $\Delta e_{im} = (1-z)e_{ij} \cdot e_{im} \left( \frac{1}{\sum_{a \in \Gamma_i} e_{ia} + \sum_{b \in \Gamma_j} e_{jb}} \right)$

2. If no replica exists, the entire weight is redistributed in the current layer.

## 2.2 Multiplex Avalanche Entropy

We define the Avalanche Entropy of an edge $AE_{ij}$ as the Quantum K-L Divergence between the density matrices of the original network $G_\rho$ and the network after cascading failures $G_{cap_{ij}}$ due to the removal of edge $ij$

$$AE_{ij} = D_1(G_\rho \| G_{cap_{ij}})$$

Here the K-L Divergence is given by $D_1(\rho \| \sigma) = \text{Tr}[\rho(\log_2 \rho - \log_2 \sigma)]$ where $\rho$ and $\sigma$ are the density matrices of two networks and $\rho = \frac{e^{-\beta \mathcal{L}}}{Z}$, $Z = \text{Tr}(e^{-\beta \mathcal{L}})$, with $\mathcal{L} = I - D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$ the normalized (Supra) Laplacian Matrix.

# 3 Results

Figure 1 depicts the multiplex transportation network of Haiti [11], with edges color-coded according to Avalanche Entropy (AE) values, normalized within each layer. The network includes three layers:

**Roads ($L_R$):** Edge weights are based on the inverse of normalized travel time between cities, **Airports ($L_A$):** Edge weights are derived from the inverse of normalized Haversine distance between cities with airports and **Helipads ($L_H$):** Edge weights combine normalized inverse Haversine distance and helipad count, with weights adjusted by a factor $\lambda = 0.5$.

Critical points of interest include edges with extreme AE values. For instance, the road link from Bombardopolis to Jean-Rabel shows a low AE value, indicating minimal impact on the multiplex network in case of failure. This link's lack of nearby helipads or airports suggests that isolated cities like these may require increased resource allocation. Conversely, Hinche exhibits many high AE paths, primarily because several nearby cities lack air access, underscoring Hinche's role as a vital road hub. Loss of these roads would significantly disrupt the road layer and potentially lead to cascading failures across other layers. Mirebalais presents another notable case: low AE values in the
helipad layer for paths leaving the city indicate its isolation in terms of air travel due to
the absence of an airport. This highlights that damage to Mirebalais' road network could
severely impact the entire transportation system, including air travel, due to its crucial
role as a road hub. In general AE provides a readily interpretable measure of paths
of interest in the transport system and this can be explored far beyond the examples
mentioned above.

*Summary.* In conclusion, we have introduced Avalanche Entropy (AE) for multiplex systems as a measure of robustness that considers cascading failures across various transport modes and capacity constraints. AE evaluates the impact of edge failures not only on local neighborhoods but also on the entire network, utilizing the Quantum K-L divergence, which accounts for global graph topology through the Graph Laplacian. We demonstrated AE's practical utility with a real-world dataset from Haiti, highlighting its effectiveness in identifying critical transportation paths. Future research should investigate AE across different time scales by adjusting the beta parameter and compare it with existing edge importance metrics through rigorous statistical analysis. Additionally, exploring changes in AE following major events, such as humanitarian crises, could provide further insights.

References

1. Artime, O., Grassia, M., De Domenico, M. et al. Robustness and resilience of complex networks. Nat Rev Phys 6, 114–131 (2024). https://doi.org/10.1038/s42254-023-00676-y

2. Aparicio, J.T., Arsenio, E. and Henriques, R. Assessing robustness in multimodal transportation systems: a case study in Lisbon. Eur. Transp. Res. Rev. 14, 28 (2022). https://doi.org/10.1186/s12544-022-00552-3

3. Taniguchi, E., Ferreira, F. and Nicholson, A., 2012. A conceptual road network emergency model to aid emergency preparedness and response decision-making in the context of humanitarian logistics. Procedia-Social and Behavioral Sciences, 39, pp.307-320.

4. Rezaei-Malek, Mohammad, and Reza Tavakkoli-Moghaddam. "Robust humanitarian relief logistics network planning." Uncertain Supply Chain Management 2, no. 2 (2014): 73-96.

5. Barrett, Chris, Richard Beckman, Karthik Channakeshava, Fei Huang, VS Anil Kumar, Achla Marathe, Madhav V. Marathe, and Guanhong Pei. "Cascading failures in multiple infrastructures: From transportation to communication network." In 2010 5th International Conference on Critical Infrastructure (CRIS), pp. 1-8. IEEE, 2010.

6. Crucitti, Paolo, Vito Latora, and Massimo Marchiori. "Model for cascading failures in complex networks." Physical Review E 69, no. 4 (2004): 045104.

7. De Domenico, M. More is different in real-world multilayer networks. Nat. Phys. 19, 1247–1262 (2023). https://doi.org/10.1038/s41567-023-02132-1

8. De Domenico, M. and Biamonte, J. Spectral entropies as information-theoretic tools for complex network comparison. Phys. Rev. X 6, 041062 (2016).

9. Wang, Wen-Xu, and Guanrong Chen. "Universal robustness characteristic of weighted networks against cascading failure." Physical Review E—Statistical, Nonlinear, and Soft Matter Physics 77, no. 2 (2008): 026101.

10. Jianxin Pei, Ying Liu, Wei Wang, Jie Gong, Cascading failures in multiplex network under flow redistribution, Physica A: Statistical Mechanics and its Applications, Volume 583, 2021, 126340, ISSN 0378-4371, https://doi.org/10.1016/j.physa.2021.126340.

11. Charles, A., Bouleux, G., and Cherifi, C. "Understanding the situation at a glance: The powerful value added of complex networks to analyse humanitarian operations", International Journal of Disaster Risk Reduction, Vol 75, 2022, DOI:10.1016/j.ijdrr.2022.102932
<figure><img src="image_2.png" /><figcaption>((a)) Road</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>((b)) Helipad</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>((c)) Airport</figcaption></figure>

<caption>Fig. 1: The Map of Haiti for all three layers in the multiplex with edges colored according to AE values</caption>