Recovering the Controllability of Complex Networks

Abstract The studies on the controllability of complex networks popularly existing in natural, social and man-made engineered systems have been a critical and attractive subject for both academic and practical communities. To design and maintain a networked system under control, it is vital to explore the mechanism and relationship between the network layout and its controllability. For a fully-controlled complex system, potential malicious attacks and/or random failures will lead to the damage of its internal structure, such as the breakdown of certain control nodes or the loss of the links between state nodes. In this paper, we first introduce the concept of degree of controllability to quantify the control level of the networks. And for the networks whose degree of controllability is not full, we propose two novel optimal recovering strategies, OAN (short for optimal adding-node) strategy and OAE (short for optimal adding-edge) strategy, to repair their controllability. The results of experiments conducted on the various real and model networks demonstrate the effectiveness of these two strategies and the better performance compared to their randomized counterparts, RAN (short for randomized adding-node) strategy and RAE (short for randomized adding-edge) strategy.