Take the Nature Publishing Group survey for the chance to win a MacBook Air

We'd like to invite you to take part in our annual reader survey.

As a thank you for your participation you will have the opportunity to enter a prize draw to win a MacBook Air.

Take survey

Take the Nature Publishing Group survey for the chance to win a MacBook Air

Take the Nature Publishing Group survey for the chance to win a MacBook Air

Find out more Remove this message

Nature | Article

日本語要約

Controllability of complex networks

Journal name:
Nature
Volume:
473,
Pages:
167–173
Date published:
DOI:
doi:10.1038/nature10011
Received
Accepted
Published online

Abstract

The ultimate proof of our understanding of natural or technological systems is reflected in our ability to control them. Although control theory offers mathematical tools for steering engineered and natural systems towards a desired state, a framework to control complex self-organized systems is lacking. Here we develop analytical tools to study the controllability of an arbitrary complex directed network, identifying the set of driver nodes with time-dependent control that can guide the system’s entire dynamics. We apply these tools to several real networks, finding that the number of driver nodes is determined mainly by the network’s degree distribution. We show that sparse inhomogeneous networks, which emerge in many real complex systems, are the most difficult to control, but that dense and homogeneous networks can be controlled using a few driver nodes. Counterintuitively, we find that in both model and real systems the driver nodes tend to avoid the high-degree nodes.

View full text

At a glance

Figures

First | 1-3 of 5 | Last
view all figures
left
  1. Controlling a simple network.
    Figure 1: Controlling a simple network.

    a, The small network can be controlled by an input vector u = (u1(t), u2(t))T (left), allowing us to move it from its initial state to some desired final state in the state space (right). Equation (2) provides the controllability matrix (C), which in this case has full rank, indicating that the system is controllable. b, Simple model network: a directed path. c, Maximum matching of the directed path. Matching edges are shown in purple, matched nodes are green and unmatched nodes are white. The unique maximum matching includes all links, as none of them share a common starting or ending node. Only the top node is unmatched, so controlling it yields full control of the directed path (ND = 1). d, In the directed path shown in b, all links are critical, that is, their removal eliminates our ability to control the network. e, Small model network: the directed star. f, Maximum matchings of the directed star. Only one link can be part of the maximum matching, which yields three unmatched nodes (ND = 3). The three different maximum matchings indicate that three distinct node configurations can exert full control. g, In a directed star, all links are ordinary, that is, their removal can eliminate some control configurations but the network could be controlled in their absence with the same number of driver nodes ND. h, Small example network. i, Only two links can be part of a maximum matching for the network in h, yielding four unmatched nodes (ND = 4). There are all together four different maximum matchings for this network. j, The network has one critical link, one redundant link (which can be removed without affecting any control configuration) and four ordinary links.

  2. Characterizing and predicting the driver nodes (ND).
    Figure 2: Characterizing and predicting the driver nodes (ND).

    a, b, Role of the hubs in model networks. The bars show the fractions of driver nodes, fD, among the low-, medium- and high-degree nodes in two network models, Erdős–Rényi (a) and scale-free (b), with N = 104 and left fencekright fence = 3 (γ = 3), indicating that the driver nodes tend to avoid the hubs. Both the Erdős–Rényi and the scale-free networks are generated from the static model38 and the results are averaged over 100 realizations. The error bars (s.e.m.), shown in the figure, are smaller than the symbols. c, Mean degree of driver nodes compared with the mean degree of all nodes in real and model networks, indicating that in real systems the hubs are avoided by the driver nodes. d, Number of driver nodes, NDrand-ER, obtained for the fully randomized version of the networks listed in Table 1, compared with the exact value, NDreal. e, Number of driver nodes, NDrand-Degree, obtained for the degree-preserving randomized version of the networks shown in Table 1, compared with NDreal. f, The analytically predicated NDanalytic calculated using the cavity method, compared with NDrand-Degree. In d–f, data points and error bars (s.e.m.) were determined from 1,000 realizations of the randomized networks.

  3. The impact of network structure on the number of driver nodes.
    Figure 3: The impact of network structure on the number of driver nodes.

    a–c, Characteristics of the explored model networks. A random-regular digraph (a), shown here for left fencekright fence = 4, is the most degree-homogeneous network as kin = kout = left fencekright fence/2 for all nodes. Erdős–Rényi networks (b) have Poisson degree distributions and their degree heterogeneities are determined by left fencekright fence. Scale-free networks (c) have power-law degree distributions, yielding large degree heterogeneities. d, Driver node density, nD, as a function of left fencekright fence for Erdős–Rényi (ER) and scale-free (SF) networks with different values of γ. Both the Erdős–Rényi and the scale-free networks are generated from the static model38 with N = 105. Lines are analytical results calculated by the cavity method using the expected degree distribution in the N right arrow ∞ limit. Symbols are calculated for the constructed discrete network: open circles indicate exact results calculated from the maximum matching algorithm, and plus symbols indicate the analytical results of the cavity method using the exact degree sequence of the constructed network. For large left fencekright fence, nD approaches its lower bound, N−1, that is, a single driver node (ND = 1) in a network of size N. e, nD as a function of γ for scale-free networks with fixed left fencekright fence. For infinite scale-free networks, nD right arrow 1 as γ right arrow γc = 2, that is, it is necessary to control almost all nodes to control the network fully. For finite scale-free networks, nD reaches its maximum as γ approaches γc (Supplementary Information). f, nD as a function of degree heterogeneity, H, for Erdős–Rényi and scale-free networks with fixed γ and variable left fencekright fence. g, nD as a function of H for Erdős–Rényi and scale-free networks for fixed left fencekright fence and variable γ. As γ increases, the curves converge to the Erdős–Rényi result (black) at the corresponding left fencekright fence value.

  4. Link categories for robust control.
    Figure 4: Link categories for robust control.

    The fractions of critical (red, lc), redundant (green, lr) and ordinary (grey, lo) links for the real networks named in Table 1. To make controllability robust to link failures, it is sufficient to double only the critical links, formally making each of these links redundant and therefore ensuring that there are no critical links in the system.

  5. Control robustness.
    Figure 5: Control robustness.

    a, Dependence on left fencekright fence of the fraction of critical (red, lc), redundant (green, lr) and ordinary (grey, lo) links for an Erdős–Rényi network: lr peaks at left fencekright fence = left fencekright fencec = 2e and the derivative of lc is discontinuous at left fencekright fence = left fencekright fencec. b, Core percolation for Erdős–Rényi network occurs at k = left fencekright fencec = 2e, which explains the lr peak. c, d, Same as in a and b but for scale-free networks. The Erdős–Rényi and scale-free networks38 have N = 104 and the results are averaged over ten realizations with error bars defined as s.e.m. Dotted lines are only a guide to the eye. e, The core (red) and leaves (green) for small Erdős–Rényi networks (N = 30) at different left fencekright fence values (left fencekright fence = 4, 5, 7). Node sizes are proportional to node degrees. f, The critical (red), redundant (green) and ordinary (grey) links for the above Erdős–Rényi networks at the corresponding left fencekright fence values.

right

References

  1. Kalman, R. E. Mathematical description of linear dynamical systems. J. Soc. Indus. Appl. Math. Ser. A 1, 152–192 (1963)
  2. Luenberger, D. G. Introduction to Dynamic Systems: Theory, Models, & Applications (Wiley, 1979)
  3. Slotine, J.-J. & Li, W. Applied Nonlinear Control (Prentice-Hall, 1991)
  4. Kelly, F. P., Maulloo, A. K. & Tan, D. K. H. Rate control for communication networks: shadow prices, proportional fairness and stability. J. Oper. Res. Soc. 49, 237–252 (1998)
  5. Srikant, R. The Mathematics of Internet Congestion Control (Birkhäuser, 2004)
  6. Chiang, M., Low, S. H., Calderbank, A. R. & Doyle, J. C. Layering as optimization decomposition: a mathematical theory of network architectures. Proc. IEEE 95, 255–312 (2007)
  7. Wang, X. F. & Chen, G. Pinning control of scale-free dynamical networks. Physica A 310, 521–531 (2002)
  8. Wang, W. & Slotine, J.-J. E. On partial contraction analysis for coupled nonlinear oscillators. Biol. Cybern. 92, 38–53 (2005)
  9. Sorrentino, F., di Bernardo, M., Garofalo, F. & Chen, G. Controllability of complex networks via pinning. Phys. Rev. E 75, 046103 (2007)
  10. Yu, W., Chen, G. & Lü, J. On pinning synchronization of complex dynamical networks. Automatica 45, 429–435 (2009)
  11. Marucci, L. et al. How to turn a genetic circuit into a synthetic tunable oscillator, or a bistable switch. PLoS ONE 4, e8083 (2009)
  12. Strogatz, S. H. Exploring complex networks. Nature 410, 268–276 (2001)
  13. Dorogovtsev, S. N. & Mendes, J. F. F. Evolution of Networks: From Biological Nets to the Internet and WWW (Oxford Univ. Press, 2003)
  14. Newman, M., Barabási, A.-L. & Watts, D. J. The Structure and Dynamics of Networks (Princeton Univ. Press, 2006)
  15. Caldarelli, G. Scale-Free Networks: Complex Webs in Nature and Technology (Oxford Univ. Press, 2007)
  16. Albert, R. & Barabási, A.-L. Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 47–97 (2002)
  17. Tanner, H. G. in Proc. 43rd IEEE Conf. Decision Contr. Vol. 3. 2467–2472 (2004)
  18. Lombardi, A. & Hörnquist, M. Controllability analysis of networks. Phys. Rev. E 75, 56110 (2007)
  19. Liu, B., Chu, T., Wang, L. & Xie, G. Controllability of a leader–follower dynamic network with switching topology. IEEE Trans. Automat. Contr. 53, 1009–1013 (2008)
  20. Rahmani, A., Ji, M., Mesbahi, M. & Egerstedt, M. Controllability of multi-agent systems from a graph-theoretic perspective. SIAM J. Contr. Optim. 48, 162–186 (2009)
  21. Kim, D.-H. & Motter, A. E. Slave nodes and the controllability of metabolic networks. N. J. Phys. 11, 113047 (2009)
  22. Mesbahi, M. & Egerstedt, M. Graph Theoretic Methods in Multiagent Networks (Princeton Univ. Press, 2010)
  23. Motter, A. E., Gulbahce, N., Almaas, E. & Barabási, A.-L. Predicting synthetic rescues in metabolic networks. Mol. Syst. Biol. 4, 168 (2008)
  24. Pastor-Satorras, R. & Vespignani, A. Evolution and Structure of the Internet: A Statistical Physics Approach (Cambridge Univ. Press, 2004)
  25. Lezon, T. R., Banavar, J. R., Cieplak, M., Maritan, A. & Fedoroff, N. V. Using the principle of entropy maximization to infer genetic interaction networks from gene expression patterns. Proc. Natl Acad. Sci. USA 103, 19033–19038 (2006)
  26. Lin, C.-T. Structural controllability. IEEE Trans. Automat. Contr. 19, 201–208 (1974)
  27. Shields, R. W. & Pearson, J. B. Structural controllability of multi-input linear systems. IEEE Trans. Automat. Contr. 21, 203–212 (1976)
  28. Lohmiller, W. & Slotine, J.-J. E. On contraction analysis for nonlinear systems. Automatica 34, 683–696 (1998)
  29. Yu, W., Chen, G., Cao, M. & Kurths, J. Second-order consensus for multiagent systems with directed topologies and nonlinear dynamics. IEEE Trans. Syst. Man Cybern. B 40, 881–891 (2010)
  30. Hopcroft, J. E. & Karp, R. M. An n5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2, 225–231 (1973)
  31. Albert, R., Jeong, H. & Barabási, A.-L. Error and attack tolerance of complex networks. Nature 406, 378–382 (2000)
  32. Cohen, R., Erez, K., Ben-Avraham, D. & Havlin, S. Resilience of the Internet to random breakdowns. Phys. Rev. Lett. 85, 4626–4628 (2000)
  33. Pastor-Satorras, R. & Vespignani, A. Epidemic spreading in scale-free networks. Phys. Rev. Lett. 86, 3200–3203 (2001)
  34. Nishikawa, T., Motter, A. E., Lai, Y.-C. & Hoppensteadt, F. C. Heterogeneity in oscillator networks: are smaller worlds easier to synchronize? Phys. Rev. Lett. 91, 014101 (2003)
  35. Erdős, P. & Rényi, A. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. 5, 17–60 (1960)
  36. Bollobás, B. Random Graphs (Cambridge Univ. Press, 2001)
  37. Barabási, A.-L. & Albert, R. Emergence of scaling in random networks. Science 286, 509–512 (1999)
  38. Goh, K.-I., Kahng, B. & Kim, D. Universal behavior of load distribution in scale-free networks. Phys. Rev. Lett. 87, 278701 (2001)
  39. Chung, F. & Lu, L. Connected component in random graphs with given expected degree sequences. Ann. Combin. 6, 125–145 (2002)
  40. Maslov, S. & Sneppen, K. Specificity and stability in topology of protein networks. Science 296, 910–913 (2002)
  41. Milo, R. et al. Network motifs: simple building blocks of complex networks. Science 298, 824–827 (2002)
  42. Mézard, M. & Parisi, G. The Bethe lattice spin glass revisited. Eur. Phys. J. B 20, 217–233 (2001)
  43. Zdeborová, L. & Mézard, M. The number of matchings in random graphs. J. Stat. Mech. 05, 05003 (2006)
  44. Zhou, H. & Ou-Yang, Z.-c. Maximum matching on random graphs. Preprint at left fencehttp://arxiv.org/abs/cond-mat/0309348right fence (2003)
  45. Callaway, D. S., Newman, M. E. J., Strogatz, S. H. & Watts, D. J. Network robustness and fragility: percolation on random graphs. Phys. Rev. Lett. 85, 5468–5471 (2000)
  46. Boguñá, M., Pastor-Satorras, R. & Vespignani, A. Cut-offs and finite size effects in scale-free networks. Eur. Phys. J. B 38, 205–209 (2004)
  47. Lovász, L. & Plummer, M. D. Matching Theory (American Mathematical Society, 2009)
  48. Bauer, M. & Golinelli, O. Core percolation in random graphs: a critical phenomena analysis. Eur. Phys. J. B 24, 339–352 (2001)
  49. Newman, M. E. J. Assortative mixing in networks. Phys. Rev. Lett. 89, 208701 (2002)
  50. Pastor-Satorras, R., Vázquez, A. & Vespignani, A. Dynamical and correlation properties of the Internet. Phys. Rev. Lett. 87, 258701 (2001)

Download references

Author information

Affiliations

  1. Center for Complex Network Research and Departments of Physics, Computer Science and Biology, Northeastern University, Boston, Massachusetts 02115, USA

    • Yang-Yu Liu &
    • Albert-László Barabási

  2. Center for Cancer Systems Biology, Dana-Farber Cancer Institute, Boston, Massachusetts 02115, USA

    • Yang-Yu Liu &
    • Albert-László Barabási

  3. Nonlinear Systems Laboratory, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA

    • Jean-Jacques Slotine

  4. Department of Mechanical Engineering and Department of Brain and Cognitive Sciences, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA

    • Jean-Jacques Slotine

  5. Department of Medicine, Brigham and Women’s Hospital, Harvard Medical School, Boston, Massachusetts 02115, USA

    • Albert-László Barabási

Contributions

All authors designed and did the research. Y.-Y.L. analysed the empirical data and did the analytical and numerical calculations. A.-L.B. was the lead writer of the manuscript.

Competing financial interests

The authors declare no competing financial interests.

Corresponding author

Correspondence to:

Author details

Supplementary information

PDF files

  1. Supplementary Information (972K)

    This file contains Supplementary Text and Data comprising: 1 Introduction; II Previous Work and Relation of Controllability to Other Problems; III Structural Control Theory; IV Maximum Matching; V Control Robustness and VI Network Datasets (see Contents list for full details), Supplementary Figures 1-11 with legends, Supplementary Table 1 and additional references.

Comments

Subscribe to comments

Additional data