Machine learning dismantling and early-warning signals of disintegration in complex systems

Abstract

From physics to engineering, biology and social science, natural and artificial systems are characterized by interconnected topologies whose features - e.g., heterogeneous connectivity, mesoscale organization, hierarchy - affect their robustness to external perturbations, such as targeted attacks to their units. Identifying the minimal set of units to attack to disintegrate a complex network, i.e. network dismantling, is a computationally challenging (NP-hard) problem which is usually attacked with heuristics. Here, we show that a machine trained to dismantle relatively small systems is able to identify higher-order topological patterns, allowing to disintegrate large-scale social, infrastructural and technological networks more efficiently than human-based heuristics. Remarkably, the machine assesses the probability that next attacks will disintegrate the system, providing a quantitative method to quantify systemic risk and detect early-warning signals of system's collapse. This demonstrates that machine-assisted analysis can be effectively used for policy and decision making to better quantify the fragility of complex systems and their response to shocks.

18 pages, 5 figures. Supplementary materials: 35 pages, 10 figures, 4 tables

References in corpus (5)

• Synchronization in complex networks
• The structure and dynamics of multilayer networks
• Hierarchical structure and the prediction of missing links in networks
• Percolation in real interdependent networks
• The statistical physics of Cities

Cited by in corpus (11)

• Robustness and resilience of complex networks
• Structural Robustness of Complex Networks: A Survey of A Posteriori Measures
• From the origin of life to pandemics: Emergent phenomena in complex systems
• A Learning Convolutional Neural Network Approach for Network Robustness Prediction
• Early warning signals for critical transitions in complex systems
• SPP-CNN: An Efficient Framework for Network Robustness Prediction
• wsGAT: Weighted and Signed Graph Attention Networks for Link Prediction
• Deep-learning-aided dismantling of interdependent networks
• Dismantling Complex Networks by a Neural Model Trained from Tiny Networks
• CNN-based Prediction of Network Robustness With Missing Edges
• Interpretable Early Warnings using Machine Learning in an Online Game-experiment