Control Centrality and Hierarchical Structure in Complex Networks

We introduce the concept of control centrality ($C_{\mathrm{c}}$) to quantify the ability of a single node to control a directed weighted network. We map the control centrality into a combinatorial optimization problem. We calculate the distribution of control centrality for several real networks and find that it is mainly determined by the network's degree distribution. We show that the underlying hierarchical structure of a general directed network plays an important role in determining the distribution of control controllability. We rigorously prove that in directed acyclic graphs, i.e. directed networks without loops, a node's control centrality is uniquely determined by its topological position in the underlying hierarchical structure of the network. Our finding on the relation between control centrality and the hierarchical structure inspires us to design an effective random attack strategy against the controllability of malicious networks, without requiring the detailed knowledge of the network structure. We test our random attack strategy on several real networks and find it is indeed effective and even comparable to those targeted attacks which rely on the detailed knowledge of the network structure.