Target control of complex networks

Abstract

Controlling large natural and technological networks is an outstanding challenge. It is typically neither feasible nor necessary to control the entire network, prompting us to explore target control: the efficient control of a preselected subset of nodes. We show that the structural controllability approach used for full control overestimates the minimum number of driver nodes needed for target control. Here we develop an alternate 'k-walk' theory for directed tree networks, and we rigorously prove that one node can control a set of target nodes if the path length to each target node is unique. For more general cases, we develop a greedy algorithm to approximate the minimum set of driver nodes sufficient for target control. We find that degree heterogeneous networks are target controllable with higher efficiency than homogeneous networks and that the structure of many real-world networks are suitable for efficient target control.

Figure 1. Structural control theory versus the k-walk theory for target control.

To control the whole network, the structural control theory predicts that we need at least three driver nodes. The possible choices for the sets of driver nodes are shown in a–c. If instead we want to control a subset of nodes, for example, {1, 2, 5, 7} (green nodes) with a minimum set of nodes, we need to solve the target control problem. The upper bound obtained by structural control theory indicates that we need at least three driver nodes (the same sets are shown in a,b and c). (d) But, in reality, we only need one driver node (node 1), which can be obtained from both the k-walk theory and the greedy algorithm, because the length of the path from the node 1 to each target node {1, 2, 5, 7} is unique.

Figure 2. Controlling a small network.

(a) A directed network with seven nodes. (b) Maximum matching of the network in its bipartite representation. Matching edges are shown in red, matched nodes {x₂, x₄, x₆, x₇} are green and unmatched nodes {x₁, x₃, x₅} are white. (c) By controlling the three unmatched nodes (driver nodes) and ensuring that there are no inaccessible nodes, the system is guaranteed to be structurally controllable. The underlying control skeleton (or the cactus structure) is highlighted. (d) Greedy algorithm developed for target control. Here the target set is {x₁, x₂, x₄, x₆, x₇} (highlighted in red). In the first iteration, we match all target nodes by solving a maximum matching problem on an induced bipartite graph. Target nodes {x₂, x₄, x₆, x₇} (in green) are matched by {x₁, x₃, x₅, x₆}, which are the new target nodes considered in iteration 2. After four iterations, we obtain that node x₁ is the driver node for the target set {x₁, x₂, x₄, x₆, x₇}. (e) By controlling the unmatched node x₁ calculated from the GA, the target set {x₁, x₂, x₄, x₆, x₇} is guaranteed to be controllable. The red lines are the matched links obtained in the first iteration of greedy algorithm. This can be proved by interpreting GA as a backtracking process on the dynamic graph representation of the system (Supplementary Note 3). The upper bound of P_D can be calculated by the minimal number of disjoint cacti that cover all target nodes, that is, for the target nodes {1, 2, 4, 6, 7}. The lower bound of P_D is just given by the first iteration of the greedy algorithm, that is, for the target nodes {1, 2, 4, 6, 7}, because in the first iteration only node 1 is unmatched.

Figure 3. Full versus target control of the simple network shown in Fig. 1.

(a,b) Full control. (a) The time-dependent input signals u₁(t), u₃(t) and u₅(t) predicted by equation (3) that can drive the state of the network from the initial state (x₁=...=x₇=0) to the final state (x₁=...=x₇=10). (b) The state trajectories of all nodes from initial state to the desired final state. (c,d) Target control. (c) The input required for the driver node 1 to control the state of the target nodes {1, 2, 4, 6, 7} from the initial state (x₁=...=x₇=0) to the final state (x₁=x₂=x₄=x₆=x₇=10). (d) The state trajectories of all nodes for tε[0, 10], where the target nodes go from 0 to the desired state 10 (solid curves) and the uncontrolled nodes go from 0 to other values (dotted curves) when t=10. The inset in d shows the detail of the final state of all seven nodes, which clearly shows that all the target nodes are controlled to be 10 and other uncontrolled nodes are not 10 and with finite values.

Figure 4. Random versus local target controllability of two canonical network models.

(a–c) Random selection scheme. (a) Illustrating random selection of f=1/3 target nodes. (b) For ER networks with average degree ‹k›=5.6, we show the normalized fraction of driver nodes (α_D) in function of the target node fraction f for the random selection scheme. (c) For SF networks with ‹k›=5.6 and exponent γ=2.4, we show the normalized fraction of driver nodes (α_D) as a function of the target node fraction f for the random scheme. (d–f) Local selection scheme. (d) The selection of an f=1/3 target node with the local scheme. (e) For ER networks with the same average degree as in b, we show the normalized fraction of driver nodes (α_D) in function of the target node fraction f for the local scheme. (f) For SF networks with the same ‹k› and γ as in c, we show the normalized fraction of driver nodes (α_D) as a function of the target node fraction f for the local scheme. The black line describes the neutral case, that is, α_D=f (or P_D=fN_D) when the target control has the same efficiency as the full control. In each figure, we denote UB as the upper bound, GA as the greedy algorithm and LB as the lower bound of the minimum number of driver nodes to control an f fraction of target nodes. For ER networks, random target control is always less efficient than the full control, and for local target control efficiency depends on f. For SF networks random target control is as efficient as full control, but significant gains in efficiency are observed for local target control. Furthermore, for ER and SF networks local target control is more efficient than random target control. All results are averaged over 200 independent realizations of the networks with 10⁴ nodes.

Figure 5. Overall target control efficiency of model networks.

(a,b) Random selection scheme. (a) The overall target control efficiency (equation (4)) for SF networks in function of degree exponent γ for different values of average degree ‹k› in the random scheme. (b) The overall target control efficiency (equation (4)) in function of the average degree ‹k› for different values of the degree exponent γ for SF networks and ER networks for random scheme. (c,d) Local selection scheme. (c) The overall target control efficiency (equation (4)) for SF networks in function of degree exponent γ for different values of average degree ‹k› for local scheme. (d) The overall target control efficiency (equation (4)) in function of the average degree ‹k› for different values of degree exponent γ of SF networks and ER networks for local scheme. From a and b we can see that for large ‹k› when γ is small the system has positive target control efficiency, but when γ is greater than a certain value, the efficiency decreases monotonically with γ becoming negative. Comparing a,b with (c,d), we find that the local control can enhance the target control efficiency. The results are obtained by averaging over 200 realizations of networks with 10⁴ nodes.

Figure 6. Target control of real-world networks.

(a–c) show random selection scheme. (a) The normalized fraction of driver nodes (α_D) in function of the target node fraction f for the random scheme for 19 different real-world networks. Network labels are in Table 1. (b) The overall target control efficiency (equation (4)) of the real-world networks for the random scheme. (c) Comparing the target control efficiency of real networks with their randomized counterparts for the random scheme after, we randomly rewire each network using degree-preserving randomization. (d–f) Local selection scheme. (d) The normalized fraction of driver nodes (α_D) in function of the target node fraction f for the local scheme for different real-world networks. (e) The overall target control efficiency (equation (4)) of real-world networks for the local scheme. (f) Comparing the target control efficiency of real networks with their randomized counterparts for the local scheme after, we randomly rewire each network using degree-preserving randomization. The results are averaged over 500 realizations. In general, real networks and more efficient than their randomized counterparts with respect to random target control.