Networks in the real world do not exist in isolation, but they rely on or interact with other networks. For example, critical infrastructural networks, such as those serving for communication and power generation,  are interdependent one on another. Interdependencies among networks generally improve their operational efficiency. However, they also make them more vulnerable. Recent worldwide events, such as the 9/11 terrorist attack, the 2005 hurricane Katrina, the 2007-2008 global financial crisis, and the 2011 Japanese earthquake, have highlighted that interdependencies among critical infrastructures not only increase the potential for cascading failures, amplifying the impact of small-scale initial failures to catastrophic proportions, but also substantially delay the restoration of the interdependent system after collapse. This project has contributed to the development analytic and computational methods able to characterize and predict the robustness of interdependent networks under failure and/or attack, and applied these methods to the study of real networks representing US critical infrastructural systems.

For example, one of the outcomes of the project was to introduce and fully characterize a novel percolation model for interdependent networks. The model is able to quantify the robustness of networks with redundant interdependencies. According to the new model, interdependencies make a system more fragile than it would be by considering each layer independently. On the other hand, redundancy of interdependencies across multiple layers favors system robustness. This is a fundamental difference with respect to previous models adopted to study the robustness of interdependent networks, where instead increasing the number of layers generates more and more fragile systems. The model serves to properly describe infrastructural systems where the addition of new layer of interactions to a preexisting infrastructure is performed with the goal of increasing the overall robustness of the system. The theoretical characterization of the model was given in terms of solutions of message-passing equations describing the effect of arbitrary types of failures in the system.

Also, the project allowed to generalize the so-called optimal percolation problem from isolated to interdependent networks. Optimal percolation is a NP-hard problem which consists in finding the minimal set of nodes such that, if its members are removed from the network, the network is dismantled. The solution to the problem provides important information on the microscopic parts that should be maintained in a functional state to keep the overall system functioning, in a scenario of maximal stress. We devised multiple algorithms able to approximate solutions to this NP-hard problem in polynomial (generally linear) time. Also, the mathematical analysis of the problem allowed us to devise a new metric, named safeguard centrality, able to single out the nodes that control the response of the entire interdependent system to damage.

Finally, the project funded research aimed at leveraging geometric representations of networks to characterize the robustness and navigability of infrastructural networks. We demonstrated that the higher-order correlations between the layers of an interdependent network predict how robust the system is against the random damage of its components. Also, we showed that embedding networks in the Euclidean space is useful for the design of effective and efficient routing protocols.

The project directly involved and educated a total of about 10 undergraduate and graduate students as research assistants and summer research interns. In particular, 2 graduate students were supported by the project for multiple years. These students are now writing their dissertations and will graduate by the end of the current academic year. The project supported the development of new classes in complex networks and systems, as well as the development of two invited lectures at the flagship conferences of the network science and the complex systems societies.

Last Modified: 10/19/2021
Modified by: Filippo Radicchi