Robustness of controllability and recoverability of complex networks

Network robustness describes a network's ability to provide and maintain an acceptable level of service in the face of failures and challenges to normal operation. Unfortunately, failures of networks, such as power outages in power systems, congestions in transportation networks, failures of routers on the Internet, happen frequently in our daily life and introduce a tremendous cascading effect on our society. We naturally expect that these networks have high robustness to maintain their performance in face of failures or attacks. As the first step, it is vital to investigate and analyze the robustness of networks so as to propose effective methods to improve network robustness.

The first part of the thesis mainly focuses on the robustness of network controllability in face of topological perturbations. In Chapter 2, we propose closed-form analytic approximations for the minimum number of driver nodes which denotes the controllability of the network. Inspired by the concept of critical links, we deduce and validate our approximations on both real-world and synthetic networks. We show that when the fraction of removed links is small, our approximations perform well. Besides, we also find that the critical link attack is the most effective among 4 considered attacks, as long as the fraction of removed links is smaller than the fraction of critical links. In Chapter 3, we focus on the controllability of swarm signalling networks with regular out-degree and bi-modal out-degree distribution. We deduce the generating functions in random failure process and then estimate the fraction of driver nodes with simulations. Results show that our estimations have high accuracy in predicting the fraction of driver nodes in case of random link failures. In order to further improve the accuracy of our proposed approximations in Chapter 4, we use a machine learning method to decrease the gap between our analytical approximations and the simulation results. We compare our approximations obtained by machine learning with existing analytical approximations and show that our approximations significantly outperform the existing closed-form analytical approximations in both synthetic and real-world networks. Apart from targeted attacks based upon the removal of critical links, we also propose analytical approximations for out-in degree-based attacks. In Chapter 5, we investigate the reachability-based robustness of controllability considering link-based random attack, targeted attack, as well as random attack under the protection of critical links. We validate our approximations using 200 real-world communication networks and some synthetic networks and find that our approximations perform well in most cases.

In the second part of the thesis, we work on the recoverability of networks. The recoverability of networks refers to the ability of a network to return to a desired performance level after suffering topological perturbations such as link failures. In Chapter 6, we propose a general topological approach and two recoverability indicators to measure the network recoverability for optical networks for two recovery scenarios. Furthermore, we employ the proposed approach to assess 20 real-world optical networks. Numerical results show that the network recoverability is coupled to the network topology, the robustness metric and the recovery strategy. We also find that assortativity, which denotes the tendency of network nodes to connect preferentially to other nodes with similar degree, has the strongest correlation with both recoverability indicators. In Chapter 7, we adopted the framework of network recoverability and investigate the recoverability of network controllability for two recovery scenarios. We employ the proposed approach to assess swarm signalling networks with regular out-degree, and networks with bi-modal out-degree distributions. Besides, we also deduced the analytical results of the recoverability indicators by generating functions, which are close to the results based on simulations. In Chapter 8, we conclude this thesis and come up with some future work.