Optimal percolation in correlated multilayer networks with overlap
arXiv:1910.04783 · doi:10.1103/PhysRevResearch.2.033122
Abstract
Multilayer networks have been found to be prone to abrupt cascading failures under random and targeted attacks, but most of the targeting algorithms proposed so far have been mainly tested on uncorrelated systems. Here we show that the size of the critical percolation set of a multilayer network is substantially affected by the presence of inter-layer degree correlations and edge overlap. We provide extensive numerical evidence which confirms that the state-of-the-art optimal percolation strategies consistently fail to identify minimal percolation sets in synthetic and real-world correlated multilayer networks, thus overestimating their robustness. We propose two new targeting algorithms, based on the local estimation of path disruptions away from a given node, and a family of Pareto-efficient strategies that take into account both intra-layer and inter-layer heuristics, and can be easily extended to multiplex networks with an arbitrary number of layers. We show that these strategies consistently outperform existing attacking algorithms, on both synthetic and real-world multiplex networks, and provide some interesting insights about the interplay of correlations and overlap in determining the hyperfragility of real-world multilayer networks. Overall, the results presented in the paper suggest that we are still far from having fully identified the salient ingredients determining the robustness of multiplex networks to targeted attacks.
arXiv comment14 pages, 9 figures, 1 table
References in corpus (35)
- Error and attack tolerance of complex networks
- Catastrophic cascade of failures in interdependent networks
- Identification of influential spreaders in complex networks
- The structure and dynamics of multilayer networks
- Network robustness and fragility: Percolation on random graphs
- Immunization of complex networks
- Influence maximization in complex networks through optimal percolation
- Efficient Immunization Strategies for Computer Networks and Populations
- Mathematical Formulation of Multi-Layer Networks
- Structural measures for multiplex networks
- Layer aggregation and reducibility of multilayer interconnected networks
- Avalanche Collapse of Interdependent Network
- Explosive transitions in complex networks' structure and dynamics: percolation and synchronization
- Avoiding catastrophic failure in correlated networks of networks
- Network robustness of multiplex networks with interlayer degree correlations
- Measuring and modelling correlations in multiplex networks
- Percolation in Multiplex Networks with Overlap
- Interdependent networks with correlated degrees of mutually dependent nodes
- Percolation in real interdependent networks
- Explosive Phenomena in Complex Networks
- Identifying optimal targets of network attack by belief propagation
- Fast and simple decycling and dismantling of networks
- Immunization and targeted destruction of networks using explosive percolation
- Message passing theory for percolation models on multiplex networks with link overlap
- Optimal percolation on multiplex networks
- Irreducibility of multilayer network dynamics: the case of the voter model
- Correlated Edge Overlaps in Multiplex Networks
- Geometric correlations mitigate the extreme vulnerability of multiplex networks against targeted attacks
- Controlling the uncertain response of real multiplex networks to random damage
- Systematic comparison between methods for the detection of influential spreaders in complex networks
- Efficient algorithm to compute mutually connected components in interdependent networks
- Percolation in real multiplex networks
- Targeted Damage to Interdependent Networks
- Algorithmic complexity of multiplex networks
- Enhancing the robustness of a multiplex network leads to multiple discontinuous percolation transitions