Structural Controllability of Networks for Non-Interactive Adversarial Vertex Removal

The problem of controllability of networks arises in a number of different domains, including in critical infrastructure systems where control must be maintained continuously. Recent work by Liu et al. has renewed interest in the seminal work by Lin on structural controllability, providing a graph-theoretical interpretation. This allows the identification of driver nodes capable of forcing the system into a desired state, which implies an obvious target for attackers wishing to disrupt the network control. Several methods for identifying driver nodes exist, but require undesirable computational complexity. In this paper, we therefore investigate the ability to regain or maintain controllability in the presence of adversaries able to remove vertices and implicit edges of the controllability graph. For this we rely on the POWER DOMINATING SET (PDS) formulation for identifying the control structure and study different attack strategies for multiple network models. As the construction of a PDS for a given graph is not unique, we further investigate different strategies for PDS construction, and provide a simulative evaluation.