Control backbone: An index for quantifying a node׳s importance for the network controllability

•Control backbone is introduced for quantifying a single node׳s contribution to the network controllability.•There exists a bijection between the set of the minimal control schemes and the set of the maximum matchings of any directed network.•A random sampling algorithm is developed to compute the control backbone.•The distribution of control backbone is mainly determined by the network׳s underlying degree distribution.•Control backbone of a node is positively correlated to the ratio of the number of its siblings to the number of its superiors.

Control over complex networks has been one of the attractive research areas for both network and control community, and has yielded many promising and significant results. Yet few studies have been dedicated to exploiting a single node׳s effort in the control of the network. In this paper, we introduce the concept of control backbone to quantify a node׳s importance for maintaining the structural controllability of the network. And a random sampling algorithm is developed to effectively compute it. Moreover, we demonstrate the distribution of the control backbone on various real and model networks and find that it is mainly determined by the network׳s underlying degree distribution. We also find the control backbone of a given node is positively correlated to its local topological feature, the ratio of the number of its siblings to the number of its superiors. Inspired by this relationship, we devise an attack strategy against the structural controllability of malicious networks. The simulation results on real and model networks show its effectiveness and efficiency compared to other commonly used attack strategies. The presented findings can help us further understand the relationship between the network׳s structural characteristics and its control.