Non-Markovian random walks characterize network robustness to nonlocal cascades
arXiv:2204.08407 · doi:10.1103/PhysRevE.105.044126
Abstract
Localized perturbations in a real-world network have the potential to trigger cascade failures at the whole system level, hindering its operations and functions. Standard approaches analytically tackling this problem are mostly based either on static descriptions, such as percolation, or on models where the failure evolves through first-neighbor connections, crucially failing to capture the nonlocal behavior typical of real cascades. We introduce a dynamical model that maps the failure propagation across the network to a self-avoiding random walk that, at each step, has a probability to perform nonlocal jumps toward operational systems' units. Despite the inherent non-Markovian nature of the process, we are able to characterize the critical behavior of the system out of equilibrium, as well as the stopping time distribution of the cascades. Our numerical experiments on synthetic and empirical biological and transportation networks are in excellent agreement with theoretical expectation, demonstrating the ability of our framework to quantify the vulnerability to nonlocal cascade failures of complex systems with interconnected structure.
References in corpus (26)
- Error and attack tolerance of complex networks
- Random graphs with arbitrary degree distributions and their applications
- Multilayer Networks
- Network robustness and fragility: Percolation on random graphs
- Critical phenomena in complex networks
- Cascade-based attacks on complex networks
- Networks beyond pairwise interactions: structure and dynamics
- A model for cascading failures in complex networks
- Mathematical Formulation of Multi-Layer Networks
- Generation of uncorrelated random scale-free networks
- k-core organization of complex networks
- The physics of spreading processes in multilayer networks
- Emergence of network features from multiplexity
- Suppressing cascades of load in interdependent networks
- Small vulnerable sets determine large network cascades in power grids
- Cascading Failures in Bi-partite Graphs: Model for Systemic Risk Propagation
- Immunization and targeted destruction of networks using explosive percolation
- Bond percolation on multiplex networks
- Magnetotransport of dirty-limit van Hove singularity quasiparticles
- Cascading failures in interdependent systems under a flow redistribution model
- Dynamics on networks: competition of temporal and topological correlations
- Percolation on feature-enriched interconnected systems
- Network Overload due to Massive Attacks
- Effectiveness of dismantling strategies on moderated vs. unmoderated online social platforms
- Abrupt transition due to non-local cascade propagation in multiplex systems
- Kinetic growth walks on complex networks