Network Robustness: the whole story

Monday, 15 December 2014
Anthony Longjas, St. Anthony Falls Laboratory, Minneapolis, MN, United States, Alejandro Tejedor, Saint Anthony Falls Laboratory, Minneapolis, MN, United States, Ilya V Zaliapin, University of Nevada, Reno, Reno, NV, United States, Samuel Ambroj, Steinbuch Centre for Computing, Karlsruhe Institute of Technology, Karlsruhe, Germany and Efi Foufoula-Georgiou, Univ Minnesota, Minneapolis, MN, United States
A multitude of actual processes operating on hydrological networks may exhibit binary outcomes such as clean streams in a river network that may become contaminated. These binary outcomes can be modeled by node removal processes (attacks) acting in a network. Network robustness against attacks has been widely studied in fields as diverse as the Internet, power grids and human societies. However, the current definition of robustness is only accounting for the connectivity of the nodes unaffected by the attack. Here, we put forward the idea that the connectivity of the affected nodes can play a crucial role in proper evaluation of the overall network robustness and its future recovery from the attack. Specifically, we propose a dual perspective approach wherein at any instant in the network evolution under attack, two distinct networks are defined: (i) the Active Network (AN) composed of the unaffected nodes and (ii) the Idle Network (IN) composed of the affected nodes. The proposed robustness metric considers both the efficiency of destroying the AN and the efficiency of building-up the IN. This approach is motivated by concrete applied problems, since, for example, if we study the dynamics of contamination in river systems, it is necessary to know both the connectivity of the healthy and contaminated parts of the river to assess its ecological functionality. We show that trade-offs between the efficiency of the Active and Idle network dynamics give rise to surprising crossovers and re-ranking of different attack strategies, pointing to significant implications for decision making.