Robustness and resilience of complex networks

This repository contains the scripts and data from the "Robustness and resilience of complex networks" Nature Review Physics paper by Oriol Artime, Marco Grassia, Manlio De Domenico, James P. Gleeson, Hernán A. Makse, Giuseppe Mangioni, Matjaž Perc and Filippo Radicchi.

Citations

How to cite the paper

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

BibTex:

@article{artime2024robustness,
	abstract = {Complex networks are ubiquitous: a cell, the human brain, a group of people and the Internet are all examples of interconnected many-body systems characterized by macroscopic properties that cannot be trivially deduced from those of their microscopic constituents. Such systems are exposed to both internal, localized, failures and external disturbances or perturbations. Owing to their interconnected structure, complex systems might be severely degraded, to the point of disintegration or systemic dysfunction. Examples include cascading failures, triggered by an initially localized overload in power systems, and the critical slowing downs of ecosystems which can be driven towards extinction. In recent years, this general phenomenon has been investigated by framing localized and systemic failures in terms of perturbations that can alter the function of a system. We capitalize on this mathematical framework to review theoretical and computational approaches to characterize robustness and resilience of complex networks. We discuss recent approaches to mitigate the impact of perturbations in terms of designing robustness, identifying early-warning signals and adapting responses. In terms of applications, we compare the performance of the state-of-the-art dismantling techniques, highlighting their optimal range of applicability for practical problems, and provide a repository with ready-to-use scripts, a much-needed tool set.},
	author = {Artime, Oriol and Grassia, Marco and De Domenico, Manlio and Gleeson, James P. and Makse, Hern{\'a}n A. and Mangioni, Giuseppe and Perc, Matja{\v z} and Radicchi, Filippo},
	date = {2024/01/08},
	date-added = {2024-01-09 08:22:35 +0100},
	date-modified = {2024-01-09 08:23:03 +0100},
	doi = {10.1038/s42254-023-00676-y},
	id = {Artime2024},
	isbn = {2522-5820},
	journal = {Nature Reviews Physics},
	title = {Robustness and resilience of complex networks},
	url = {https://doi.org/10.1038/s42254-023-00676-y},
	year = {2024},
	bdsk-url-1 = {https://doi.org/10.1038/s42254-023-00676-y}
}

RIS:

TY  - JOUR
AB  - Complex networks are ubiquitous: a cell, the human brain, a group of people and the Internet are all examples of interconnected many-body systems characterized by macroscopic properties that cannot be trivially deduced from those of their microscopic constituents. Such systems are exposed to both internal, localized, failures and external disturbances or perturbations. Owing to their interconnected structure, complex systems might be severely degraded, to the point of disintegration or systemic dysfunction. Examples include cascading failures, triggered by an initially localized overload in power systems, and the critical slowing downs of ecosystems which can be driven towards extinction. In recent years, this general phenomenon has been investigated by framing localized and systemic failures in terms of perturbations that can alter the function of a system. We capitalize on this mathematical framework to review theoretical and computational approaches to characterize robustness and resilience of complex networks. We discuss recent approaches to mitigate the impact of perturbations in terms of designing robustness, identifying early-warning signals and adapting responses. In terms of applications, we compare the performance of the state-of-the-art dismantling techniques, highlighting their optimal range of applicability for practical problems, and provide a repository with ready-to-use scripts, a much-needed tool set.
AU  - Artime, Oriol
AU  - Grassia, Marco
AU  - De Domenico, Manlio
AU  - Gleeson, James P.
AU  - Makse, Hernán A.
AU  - Mangioni, Giuseppe
AU  - Perc, Matjaž
AU  - Radicchi, Filippo
DO  - 10.1038/s42254-023-00676-y
ID  - Artime2024
SN  - 2522-5820
T2  - Nature Reviews Physics
TI  - Robustness and resilience of complex networks
UR  - https://doi.org/10.1038/s42254-023-00676-y
PY  - 2024
ER  -

Also, please cite the original papers of the algorithms, of the Dataset, and of the libraries you use (see the Setup section).

How to cite this repository

If you use the code, please cite the paper as described here.

License

The code implemented for the review (that is, the wrappers, the dismantlers and the output scripts) available in this repository is released under the GPLv3 License. See the LICENSE file for more information. However, please note that the code of the specific integrated algorithms is redistributed from their original repositories and may be subject to different licenses. Thus, the GPLv3 License may not apply to them and to the code in their folders. If you wish to use them, please refer to their original LICENSE files (in the respective folders), and to the original authors.

Algorithms

This library integrates and provides a common interface to the following algorithms:

Brute Force
Collective Influence (CI): reference
CoreGDM (almost ready, needs some fixes): reference
CoreHD: reference
Ensemble GND (EGND): reference
Explosive Immunization (EI): reference
FINDER: reference
Generalized Network Dismantling (GND): reference
Graph Dismantling Machine (GDM): reference
Min-Sum: reference
NetworkEntanglement: reference
VertexEntanglement: reference
Node heuristics (to be integrated in the main dismantler, need to use the separate script for now)
- Degree
- Betweenness
- Eigenvector centrality
- PageRank

The package also includes the greedy reinsertion algorithm proposed for the reinsertion phase of Min-Sum.

If you use any of these algorithms, please also cite the original papers. See the Citations file for more information.

Setup

Expected time for this step: 30m - 1h

This package is written in Python (tested with version 3.9), and uses graph-tool[1] for the graph processing. The bundled scripts should take cake of building and setting up the included algorithms. However, the users may need to manually install some dependencies, see Requirements for more information.

Regarding the Python environment, we recommend you to use Conda environments and avoid installing any package in your main Python environment in order to avoid conflicts or issues with your operating system. This step is crucial, since some of the algorithms depend (directly and/or indirectly) on different libraries version (e.g., pytorch and tensorflow with different library version requirements).

Requirements

This package includes many C/C++ algorithms, which require a C++ compiler and some libraries. Make sure you have the following libraries installed on your system:

GCC (tested with version 12.x)
Build essentials (e.g., make, cmake, etc.)
OpenMP
Boost
CMake

In an Ubuntu system, you can install them with the following command:

sudo apt install build-essential gcc-12 g++-12 cmake libboost-all-dev libomp-dev

While in a Fedora system, you can use the following command:

sudo dnf install development-tools gcc gcc-c++ make cmake boost-devel libomp-devel

To install Conda, please refer to the miniconda official documentation, or to the full Anaconda distribution.

Building your own environment

In this section, we will show how to build the Conda environments with the required dependencies for the various algorithms. Remember to switch to the right environment before running the algorithms. If you have any issues, please refer to the official documentation of the specific algorithms. You can find them in their sub-folders.

All algorithms except FINDER and GDM

conda create -n dismantling python=3.9 boost boost-cpp graph-tool dill tqdm numpy scipy pandas seaborn matplotlib -c anaconda -c conda-forge

conda activate dismantling

GDM

Create an environment like the generic one, but also install PyTorch and PyTorch Geometric (PyG).

Please refer to the PyTorch installation matrix and to the PyG documentation to choose the right configuration.

Just as an example, if your host machine supports CUDA (11.8), the command should look like the following:

conda create --name gdm boost boost-cpp graph-tool dill tqdm numpy scipy pandas seaborn matplotlib python pytorch torchvision t

Review

Install / Use

README