The recoverability of network controllability

Abstract

Network recoverability refers to the ability of a network to return to a desired
performance level after suffering malicious attacks or random failures. A system is controllable if it can be driven from any arbitrary state to any desired state in finite time under the control of the driver nodes, which are attached to external inputs. We use the minimum number of driver nodes as the R-value, which is a typical metric to denote the network controllability. We investigate the recoverability of network controllability under link-based perturbations and node-based perturbations. For link-based perturbations, two recovery scenarios are discussed: (1) only the links which are damaged in the failure process can be recovered; (2) links can be established between any pair of nodes that have no link between them after the failure process. For node-based perturbations, we also investigate two recovery scenarios: (1) only the nodes and their original links that are removed in the failure process are recovered; (2) the nodes are removed during the failure process are recovered, and the same number of removed links are added at random. We propose analytical approximations under link-based and node-based perturbations in two recovery scenarios by using generating
functions. Results show that our approximations fit well with simulation results both in synthetic networks and some real-world networks, such as swarm signaling networks and communication networks.