Towards Optimal Robustness of Network Controllability by Nested-Edge Rectification

Abstract

When a network is attacked, the network controllability decreases and the network is at risk of collapse. A network with good controllability robustness can better maintain its own controllability while under attack to provide time for network recovery. In order to explore how to build a network with optimal controllability robustness, an exhaustive search with adding edges was executed on a given set of small-sized networks. By exhaustive search, we mean: (1) All possible ways of adding edges, except self-loops, were considered and calculated at the time of adding each edge. (2) All possible node removal sequences were taken into account. The nested ring structure (NRS) was obtained from the result of the exhaustive search. NRS has a backbone ring, and the remaining edges of each node point to the nearest nodes along the direction of the backbone ring’s edges. The NRS satisfies an empirically necessary condition (ENC) and has great ability to resist random attacks. Therefore, nested edge rectifcation (NER) was designed to optimize the network for controllability robustness by constructing NRS in networks. NER was compared with the random edge rectification (RER) strategy and the unconstrained rewiring (UCR) strategy on synthetic networks and real-world networks by simulation. The simulation results show that NER can better improve the robustness of network’s controllability, and NER can also quickly improve the initial network controllability for networks with more than one driver node. In addition, as NER is executed, NRS gains more edges in the network, so the network has better controllability robustness. NER will be helpful for network model design or network optimization in future.

Keywords

• complex network
• network controllability
• controllability robustness
• optimization
• nested ring structure
• edge rectification