Towards Optimal Robustness of Network Controllability: An Empirical Necessary Condition

Abstract

To better understand the correlation between network topological features and the robustness of network controllability in a general setting, this paper suggests a practical approach to searching for optimal network topologies with given numbers of nodes and edges. Since theoretical analysis seems impossible at least in the present time, exhaustive search based on optimization techniques is employed, firstly for a group of small-sized networks that are realistically workable, where \textit{exhaustive} means 1) all possible network structures with the given numbers of nodes and edges are computed and compared, and 2) all possible node-removal sequences are considered. A main contribution of this paper is the observation of an empirical necessary condition (ENC) from the results of exhaustive search, which shrinks the search space to quickly find an optimal solution. ENC shows that the maximum and minimum in- and out-degrees of an optimal network structure should be almost identical, or within a very narrow range, i.e., the network should be extremely homogeneous. Edge rectification towards the satisfaction of the ENC is then designed and evaluated. Simulation results on large-sized synthetic and real-world networks verify the effectiveness of both the observed ENC and the edge rectification scheme. As more operations of edge rectification are performed, the network is getting closer to exactly satisfying the ENC, and consequently the robustness of the network controllability is enhanced towards optimum.

arXiv comment[article] 18 pages, 12 figures; [supplementary information] 9 pages, 15 figures

References in corpus (21)

• Catastrophic cascade of failures in interdependent networks
• Attack vulnerability of complex networks
• Renormalization group analysis of the small-world network model
• Universal Behavior of Load Distribution in Scale-free Networks
• Mitigation of Malicious Attacks on Networks
• Control Principles of Complex Networks
• Exact Controllability of Complex Networks
• Control centrality and hierarchical structure in complex networks
• The extreme vulnerability of interdependent spatially embedded networks
• Effect of correlations on network controllability
• Enhancing network robustness for malicious attacks
• Network Controllability Is Determined by the Density of Low In-Degree and Out-Degree Nodes
• Robustness of onion-like correlated networks against targeted attacks
• Onion structure and network robustness
• Networkcontrology
• Effects of the network structural properties on its controllability
• Toward Stronger Robustness of Network Controllability: A Snapback Network Model
• Deciphering the imprint of topology on nonlinear dynamical network stability
• Benchmarking measures of network controllability on canonical graph models
• The evolution of network controllability in growing networks
• Improving controllability of complex networks by rewiring links regularly

Cited by in corpus (7)

• Structural Robustness of Complex Networks: A Survey of A Posteriori Measures
• A Learning Convolutional Neural Network Approach for Network Robustness Prediction
• Knowledge-Based Prediction of Network Controllability Robustness
• A Framework of Hierarchical Attacks to Network Controllability
• SPP-CNN: An Efficient Framework for Network Robustness Prediction
• The network asymmetry caused by the degree correlation and its effect on the bimodality in control
• Controllability of a Class of Swarm Signaling Networks