Effect of correlations on network controllability

Abstract

A dynamical system is controllable if by imposing appropriate external signals on a subset of its nodes, it can be driven from any initial state to any desired state in finite time. Here we study the impact of various network characteristics on the minimal number of driver nodes required to control a network. We find that clustering and modularity have no discernible impact, but the symmetries of the underlying matching problem can produce linear, quadratic or no dependence on degree correlation coefficients, depending on the nature of the underlying correlations. The results are supported by numerical simulations and help narrow the observed gap between the predicted and the observed number of driver nodes in real networks.

Figure 1

(a) We compare N_D for real systems to , representing the number of driver nodes needed to control their randomized counterparts. Randomization eliminates all local and global correlations, only preserving the degree sequence of the original system. We find that the degree sequence predicts the order of magnitude of N_D correctly, however, small deviations are hidden by the log scale, needed to show the whole span of N_D seen in real systems. (b) These deviations are more obvious if we compare the density of driver nodes n_D = N_D/N and in linear scale, finding that for some systems (e.g. regulatory and p2p Internet networks) the degree sequence serves as a good predictor of n_D, while for other systems (e.g. metabolic networks and food webs) n_D deviates from the prediction based solely on the degree sequence.

Figure 2. Effect of the clustering coefficient C and modularity Q on the density of driver nodes, n_D.

Network size is N = 10, 000. Each data point is an average over 50 independent runs; the error bars, typically smaller than the symbol size, represent the standard deviation of the measurements.

Figure 3. The impact of degree-degree correlations on the density of driver nodes (n_D) for the Erdős-Rényi model (N = 10, 000) for average degrees 〈k〉 = 1 (red), 〈k〉 = 3 (green), 〈k〉 = 5 (blue), 〈k〉 = 7 (black) and 〈k〉 = 9 (orange).

The results are similar for the scale-free model (see Fig. 4). Each data point is an average of 100 independent runs.

Figure 4. The impact of degree-degree correlations on the density of driver nodes (n_D) for the scale-free model (N = 10, 000, γ = 2.5) for average degrees 〈k〉 = 1 (red), 〈k〉 = 3 (green), 〈k〉 = 5 (blue), 〈k〉 = 7 (black) and 〈k〉 = 9 (orange).

The results are similar for the Erdős-Rényi model (see Fig. 3). Each data point is an average of 100 independent runs.

Figure 5. One-step out-out correlations induce positive two-step correlation.

Positive (negative) correlation between neighboring nodes means that if node A has high out-degree, then node B is likely to have high (low) out-degree, and hence C will likely have high out-degree.

Figure 6. The analytic formulas are tested with simulations on an (a) Erdős-Rényi model and on a (b) scale-free model.

We used the algorithm proposed in to set e^(α−β)(j_i, j_o; k_i, k_o). For (a) network we choose N = 1, 000 and 〈k〉 = 3; for (b) N = 1, 000, γ = 2.5 and 〈k〉 = 4. Each data point is an average over 100 independent runs; the errors represent by the standard deviation of the measurements.

Figure 7. The observed and predicted deviation between N_D and .

Red line: , the prediction error based on the degree sequence. Dashed lines: correlations relevant to controllability. For each network Δ is calculated by averaging over 50 independent configurations.