1932
0
  1. Home
  2. A-Z Publications
  3. Annual Review of Control, Robotics, and Autonomous Systems
  4. Volume 4, 2021
  5. Article

Annual Review of Control, Robotics, and Autonomous Systems

Volume 4, 2021

Model Reduction Methods for Complex Network Systems

Abstract

Network systems consist of subsystems and their interconnections and provide a powerful framework for the analysis, modeling, and control of complex systems. However, subsystems may have high-dimensional dynamics and a large number of complex interconnections, and it is therefore relevant to study reduction methods for network systems. Here, we provide an overview of reduction methods for both the topological (interconnection) structure of a network and the dynamics of the nodes while preserving structural properties of the network. We first review topological complexity reduction methods based on graph clustering and aggregation, producing a reduced-order network model. Next, we consider reduction of the nodal dynamics using extensions of classical methods while preserving the stability and synchronization properties. Finally, we present a structure-preserving generalized balancing method for simultaneously simplifying the topological structure and the order of the nodal dynamics.

Keyword(s): graph clustering, interconnected systems, multiagent systems, network systems, reduced-order modeling, semistability, structure-preserving, synchronization
Loading

Article metrics loading...

/content/journals/10.1146/annurev-control-061820-083817
2021-05-03
2024-05-04
Loading full text...

Full text loading...

/deliver/fulltext/control/4/1/annurev-control-061820-083817.html?itemId=/content/journals/10.1146/annurev-control-061820-083817&mimeType=html&fmt=ahah

Literature Cited

  1. 1. 
    Mesbahi M, Egerstedt M. 2010. Graph Theoretic Methods in Multiagent Networks Princeton, NJ: Princeton Univ. Press
  2. 2. 
    Newman ME. 2003. The structure and function of complex networks. SIAM Rev 45:167–256
     [Google Scholar]
  3. 3. 
    Ren W, Beard RW, Atkins EM 2005. A survey of consensus problems in multi-agent coordination. Proceedings of the 2005 American Control Conference1859–64 Piscataway, NJ: IEEE
     [Google Scholar]
  4. 4. 
    Rao S, van der Schaft AJ, Jayawardhana B 2013. A graph-theoretical approach for the analysis and model reduction of complex-balanced chemical reaction networks. J. Math. Chem. 51:2401–22
     [Google Scholar]
  5. 5. 
    Ahsendorf T, Wong F, Eils R, Gunawardena J 2014. A framework for modelling gene regulation which accommodates non-equilibrium mechanisms. BMC Biol 12:102
     [Google Scholar]
  6. 6. 
    Proskurnikov AV, Tempo R. 2017. A tutorial on modeling and analysis of dynamic social networks. Part I. Annu. Rev. Control 43:65–79
     [Google Scholar]
  7. 7. 
    Dörfler F, Bullo F. 2012. Synchronization and transient stability in power networks and nonuniform kuramoto oscillators. SIAM J. Control Optim. 50:1616–42
     [Google Scholar]
  8. 8. 
    Chow JH 2013. Power System Coherency and Model Reduction New York: Springer
  9. 9. 
    Antoulas AC. 2005. Approximation of Large-Scale Dynamical Systems. Philadelphia: Soc. Ind. Appl. Math.
     [Google Scholar]
  10. 10. 
    Bai Z. 2002. Krylov subspace techniques for reduced-order modeling of large-scale dynamical systems. Appl. Numer. Math. 43:9–44
     [Google Scholar]
  11. 11. 
    Astolfi A. 2010. Model reduction by moment matching for linear and nonlinear systems. IEEE Trans. Autom. Control 55:2321–36
     [Google Scholar]
  12. 12. 
    Moore BC. 1981. Principal component analysis in linear systems: controllability, observability, and model reduction. IEEE Trans. Autom. Control 26:17–32
     [Google Scholar]
  13. 13. 
    Glover K. 1984. All optimal Hankel-norm approximations of linear multi-variable systems and their L∞-error bounds. Int. J. Control 39:1115–93
     [Google Scholar]
  14. 14. 
    Besselink B, Tabak U, Lutowska A, Van de Wouw N, Nijmeijer H et al. 2013. A comparison of model reduction techniques from structural dynamics, numerical mathematics and systems and control. J. Sound Vib. 332:4403–22
     [Google Scholar]
  15. 15. 
    Summers TH, Lygeros J. 2014. Optimal sensor and actuator placement in complex dynamical networks. IFAC Proc. Vol. 47:33784–89
     [Google Scholar]
  16. 16. 
    Gates AJ, Rocha LM. 2016. Control of complex networks requires both structure and dynamics. Sci. Rep. 6:24456
     [Google Scholar]
  17. 17. 
    Kim JZ, Soffer JM, Kahn AE, Vettel JM, Pasqualetti F, Bassett DS 2018. Role of graph architecture in controlling dynamical networks with applications to neural systems. Nat. Phys. 14:91–98
     [Google Scholar]
  18. 18. 
    Ishizaki T, Chakrabortty A, Imura JI 2018. Graph-theoretic analysis of power systems. Proc. IEEE 106:931–52
     [Google Scholar]
  19. 19. 
    Obinata G, Anderson BDO. 2012. Model Reduction for Control System Design London: Springer
  20. 20. 
    Mustafa D, Glover K. 1991. Controller reduction by H∞ balanced truncation. IEEE Trans. Autom. Control 36:668–82
     [Google Scholar]
  21. 21. 
    Jain AK, Murty MN, Flynn PJ 1999. Data clustering: a review. ACM Comput. Surv. 31:264–323
     [Google Scholar]
  22. 22. 
    Schaeffer SE. 2007. Graph clustering. Comput. Sci. Rev. 1:27–64
     [Google Scholar]
  23. 23. 
    van der Schaft AJ. 2014. On model reduction of physical network systems. Proceedings of the 21st International Symposium on Mathematical Theory of Networks and Systems1419–25 Groningen, Neth: Univ. Groningen
     [Google Scholar]
  24. 24. 
    Ishizaki T, Kashima K, Imura JI, Aihara K 2014. Model reduction and clusterization of large-scale bidirectional networks. IEEE Trans. Autom. Control 59:48–63
     [Google Scholar]
  25. 25. 
    Monshizadeh N, Trentelman HL, Camlibel MK 2014. Projection-based model reduction of multi-agent systems using graph partitions. IEEE Trans. Control Netw. Syst. 1:145–54
     [Google Scholar]
  26. 26. 
    Deng K, Goyal S, Barooah P, Mehta PG 2014. Structure-preserving model reduction of nonlinear building thermal models. Automatica 50:1188–95
     [Google Scholar]
  27. 27. 
    Besselink B, Sandberg H, Johansson KH 2016. Clustering-based model reduction of networked passive systems. IEEE Trans. Autom. Control 61:2958–73
     [Google Scholar]
  28. 28. 
    Cheng X, Kawano Y, Scherpen JMA 2017. Reduction of second-order network systems with structure preservation. IEEE Trans. Autom. Control 62:5026–38
     [Google Scholar]
  29. 29. 
    Cheng X, Kawano Y, Scherpen JMA 2019. Model reduction of multi-agent systems using dissimilarity-based clustering. IEEE Trans. Autom. Control 64:1663–70
     [Google Scholar]
  30. 30. 
    Jongsma HJ, Mlinarić P, Grundel S, Benner P, Trentelman HL 2018. Model reduction of linear multi-agent systems by clustering with h2 and H∞ error bounds. Math. Control Signals Syst. 30:6
     [Google Scholar]
  31. 31. 
    Martin N, Frasca P, Canudas-de Wit C 2018. Large-scale network reduction towards scale-free structure. IEEE Trans. Netw. Sci. Eng. 6:711–23
     [Google Scholar]
  32. 32. 
    Reis T, Stykel T. 2008. A survey on model reduction of coupled systems. Model Order Reduction: Theory, Research Aspects and Applications WHA Schilders, HA van der Vorst, J Rommes 133–55 Berlin: Springer
     [Google Scholar]
  33. 33. 
    Vandendorpe A, Van Dooren P 2008. Model reduction of interconnected systems. Model Order Reduction: Theory, Research Aspects and Applications WHA Schilders, HA van der Vorst, J Rommes 305–21 Berlin: Springer
     [Google Scholar]
  34. 34. 
    Sandberg H, Murray RM. 2009. Model reduction of interconnected linear systems. Optim. Control Appl. Methods 30:225–45
     [Google Scholar]
  35. 35. 
    Monshizadeh N, Trentelman HL, Camlibel MK 2013. Stability and synchronization preserving model reduction of multi-agent systems. Syst. Control Lett. 62:1–10
     [Google Scholar]
  36. 36. 
    Cheng X, Scherpen JMA, Zhang F 2019. Model reduction of synchronized homogeneous Lur'e networks with incrementally sector-bounded nonlinearities. Eur. J. Control 50:11–19
     [Google Scholar]
  37. 37. 
    Ishizaki T, Ku R, Imura Ji 2016. Clustered model reduction of networked dissipative systems. Proceedings of the 2016 American Control Conference3662–67 Piscataway, NJ: IEEE
     [Google Scholar]
  38. 38. 
    Cheng X, Scherpen JMA, Besselink B 2019. Balanced truncation of networked linear passive systems. Automatica 104:17–25
     [Google Scholar]
  39. 39. 
    Bullo F. 2019. Lectures on Network Systems Seattle, WA: Kindle Direct Publ.
  40. 40. 
    Wu CW. 2007. Synchronization in Complex Networks of Nonlinear Dynamical Systems Singapore: World Sci.
  41. 41. 
    Fax JA, Murray RM. 2001. Graph Laplacians and stabilization of vehicle formations. IFAC Proc. Vol. 35:155–60
     [Google Scholar]
  42. 42. 
    Mirzaev I, Gunawardena J. 2013. Laplacian dynamics on general graphs. Bull. Math. Biol. 75:2118–49
     [Google Scholar]
  43. 43. 
    Dörfler F, Simpson-Porco JW, Bullo F 2018. Electrical networks and algebraic graph theory: models, properties, and applications. Proc. IEEE 106:977–1005
     [Google Scholar]
  44. 44. 
    van der Schaft AJ. 2017. Modeling of physical network systems. Syst. Control Lett. 101:21–27
     [Google Scholar]
  45. 45. 
    Newman ME, Barabási ALE, Watts DJ 2006. The Structure and Dynamics of Networks Princeton, NJ: Princeton Univ. Press
  46. 46. 
    Fagnani F, Frasca P. 2017. Introduction to Averaging Dynamics over Networks Cham, Switz: Springer
  47. 47. 
    Rantzer A. 2015. Scalable control of positive systems. Eur. J. Control 24:72–80
     [Google Scholar]
  48. 48. 
    Rantzer A, Valcher ME. 2018. A tutorial on positive systems and large scale control. 2018 IEEE Conference on Decision and Control,3686–97 Piscataway, NJ: IEEE
     [Google Scholar]
  49. 49. 
    Ishizaki T, Kashima K, Girard A, Imura J, Chen L, Aihara K 2015. Clustered model reduction of positive directed networks. Automatica 59:238–47
     [Google Scholar]
  50. 50. 
    Johnson CR. 1990. Matrix Theory and Applications Providence, RI: Am. Math. Soc.
  51. 51. 
    Scardovi L, Sepulchre R. 2008. Synchronization in networks of identical linear systems. Proceedings of the 47th IEEE Conference on Decision and Control546–51 Piscataway, NJ: IEEE
     [Google Scholar]
  52. 52. 
    Li Z, Duan Z, Chen G, Huang L 2010. Consensus of multiagent systems and synchronization of complex networks: a unified viewpoint. IEEE Trans. Circuits Syst. I 57:213–24
     [Google Scholar]
  53. 53. 
    Willems JC 1976. Realization of systems with internal passivity and symmetry constraints. J. Franklin Inst. 301:605–21
     [Google Scholar]
  54. 54. 
    Arcak M. 2007. Passivity as a design tool for group coordination. IEEE Trans. Autom. Control 52:1380–90
     [Google Scholar]
  55. 55. 
    Chopra N. 2012. Output synchronization on strongly connected graphs. IEEE Trans. Autom. Control 57:2896–901
     [Google Scholar]
  56. 56. 
    Bhat SP, Bernstein DS. 1999. Lyapunov analysis of semistability. Proceedings of the 1999 American Control Conference, Vol. 31608–12 Piscataway, NJ: IEEE
     [Google Scholar]
  57. 57. 
    Hui Q, Haddad WM, Bhat SP 2009. Semistability, finite-time stability, differential inclusions, and discontinuous dynamical systems having a continuum of equilibria. IEEE Trans. Autom. Control 54:2465–70
     [Google Scholar]
  58. 58. 
    Cheng X, Scherpen JMA. 2020. Novel Gramians for linear semistable systems. Automatica 115:108911
     [Google Scholar]
  59. 59. 
    Cheng X, Scherpen JMA. 2017. A new controllability Gramian for semistable systems and its application to approximation of directed networks. Proceedings of the 56th IEEE Conference on Decision and Control3823–28 Piscataway, NJ: IEEE
     [Google Scholar]
  60. 60. 
    Cheng X, Yu L, Ren D, Scherpen JMA 2020. Reduced order modeling of diffusively coupled network systems: an optimal edge weighting approach. arXiv:2003.03559 [math.OC]
  61. 61. 
    Farina L, Rinaldi S. 2011. Positive Linear Systems: Theory and Applications New York: Wiley & Sons
  62. 62. 
    Cheng X, Scherpen JMA. 2020. Clustering-based model reduction of Laplacian dynamics with weakly connected topology. IEEE Trans. Autom. Control 65:4393–99
     [Google Scholar]
  63. 63. 
    Zhang S, Cao M, Camlibel MK 2013. Upper and lower bounds for controllable subspaces of networks of diffusively coupled agents. IEEE Trans. Autom. Control 59:745–50
     [Google Scholar]
  64. 64. 
    Aguilar CO, Gharesifard B. 2017. Almost equitable partitions and new necessary conditions for network controllability. Automatica 80:25–31
     [Google Scholar]
  65. 65. 
    Mlinarić P, Grundel S, Benner P 2015. Efficient model order reduction for multi-agent systems using QR decomposition-based clustering. Proceedings of the 54th IEEE Conference on Decision and Control4794–99 Piscataway, NJ: IEEE
     [Google Scholar]
  66. 66. 
    Cheng X, Yu L, Scherpen JMA 2019. Reduced order modeling of linear consensus networks using weight assignments. Proceedings of the 17th European Control Conference2005–10 Piscataway, NJ: IEEE
     [Google Scholar]
  67. 67. 
    Zelazo D, Schuler S, Allgöwer F 2013. Performance and design of cycles in consensus networks. Syst. Control Lett. 62:85–96
     [Google Scholar]
  68. 68. 
    Leiter N, Zelazo D. 2017. Graph-based model reduction of the controlled consensus protocol. IFAC-PapersOnLine 50:19456–61
     [Google Scholar]
  69. 69. 
    Cheng X, Kawano Y, Scherpen JMA 2016. Graph structure-preserving model reduction of linear network systems. Proceedings of the 15th European Control Conference1970–75 Piscataway, NJ: IEEE
     [Google Scholar]
  70. 70. 
    Cheng X, Scherpen JMA. 2016. Introducing network Gramians to undirected network systems for structure-preserving model reduction. Proceedings of the 55th IEEE Conference on Decision and Control5756–61 Piscataway, NJ: IEEE
     [Google Scholar]
  71. 71. 
    Cheng X, Scherpen JMA. 2018. Clustering approach to model order reduction of power networks with distributed controllers. Adv. Comput. Math. 44:1917–39
     [Google Scholar]
  72. 72. 
    Kawano Y, Besselink B, Scherpen JM, Cao M 2020. Data-driven model reduction of monotone systems by nonlinear DC gains. IEEE Trans. Autom. Control 65:2094–106
     [Google Scholar]
  73. 73. 
    Zha H, He X, Ding C, Gu M, Simon HD 2002. Spectral relaxation for K-means clustering. Advances in Neural Information Processing Systems 14 TG Dietterich, S Becker, Z Ghahramani 1057–64 Cambridge, MA: MIT Press
     [Google Scholar]
  74. 74. 
    Niazi MUB, Cheng X, Canudas-de-Wit C, Scherpen JMA 2019. Structure-based clustering for model reduction of large-scale networks. Proceedings of the 58th IEEE Conference on Decision and Control5038–43 Piscataway, NJ: IEEE
     [Google Scholar]
  75. 75. 
    Aoki M. 1968. Control of large-scale dynamic systems by aggregation. IEEE Trans. Autom. Control 13:246–53
     [Google Scholar]
  76. 76. 
    Feliachi A, Bhurtun C. 1987. Model reduction of large-scale interconnected systems. Int. J. Syst. Sci. 18:2249–59
     [Google Scholar]
  77. 77. 
    Ishizaki T, Imura JI. 2015. Clustered model reduction of interconnected second-order systems. Nonlinear Theory Appl 6:26–37
     [Google Scholar]
  78. 78. 
    Cheng X, Necoara I, Lupu D 2020. A suboptimal h2 clustering-based model reduction approach for linear network systems. Proceedings of the 17th European Control Conference1961–66 Piscataway, NJ: IEEE
     [Google Scholar]
  79. 79. 
    Lacoste-Julien S. 2016. Convergence rate of Frank-Wolfe for nonconvex objectives. arXiv:1607.00345 [math.OC]
  80. 80. 
    Dinh QT, Gumussoy S, Michiels W, Diehl M 2011. Combining convex-concave decompositions and linearization approaches for solving BMIs, with application to static output feedback. IEEE Trans. Autom. Control 57:1377–90
     [Google Scholar]
  81. 81. 
    Kokotovic PV, O'Malley RE Jr, Sannuti P 1976. Singular perturbations and order reduction in control theory—an overview. Automatica 12:123–32
     [Google Scholar]
  82. 82. 
    Anderson J, Chang YC, Papachristodoulou A 2011. Model decomposition and reduction tools for large-scale networks in systems biology. Automatica 47:1165–74
     [Google Scholar]
  83. 83. 
    Hancock EJ, Stan GB, Arpino JA, Papachristodoulou A 2015. Simplified mechanistic models of gene regulation for analysis and design. J. R. Soc. Interface 12:20150312
     [Google Scholar]
  84. 84. 
    Chow JH, Galarza R, Accari P, Price WW 1995. Inertial and slow coherency aggregation algorithms for power system dynamic model reduction. IEEE Trans. Power Syst. 10:680–85
     [Google Scholar]
  85. 85. 
    Bıyık E, Arcak M. 2008. Area aggregation and time-scale modeling for sparse nonlinear networks. Syst. Control Lett. 57:142–49
     [Google Scholar]
  86. 86. 
    Romeres D, Dörfler F, Bullo F 2013. Novel results on slow coherency in consensus and power networks. Proceedings of the 2013 European Control Conference742–47 Piscataway, NJ: IEEE
     [Google Scholar]
  87. 87. 
    Dörfler F, Bullo F. 2013. Kron reduction of graphs with applications to electrical networks. IEEE Trans. Circuits Syst. I 60:150–63
     [Google Scholar]
  88. 88. 
    Monshizadeh N, De Persis C, van der Schaft AJ, Scherpen JMA 2017. A novel reduced model for electrical networks with constant power loads. IEEE Trans. Autom. Control 63:1288–99
     [Google Scholar]
  89. 89. 
    Deng K, Mehta PG, Meyn SP 2011. Optimal Kullback-Leibler aggregation via spectral theory of Markov chains. IEEE Trans. Autom. Control 56:2793–808
     [Google Scholar]
  90. 90. 
    Martin N, Frasca P, Canudas-de-Wit C 2018. MergeToCure: a new strategy to allocate cure in an epidemic over a grid-like network using a scale-free abstraction. IFAC-PapersOnLine 51:2334–39
     [Google Scholar]
  91. 91. 
    Cheng X, Scherpen JMA. 2017. Balanced truncation approach to linear network system model order reduction. IFAC-PapersOnLine 50:12451–56
     [Google Scholar]
  92. 92. 
    Yu L, Cheng X, Scherpen JMA 2019. h2 suboptimal model reduction for second-order network systems.. Proceedings of the 58th IEEE Conference on Decision and Control5062–67 Piscataway, NJ: IEEE
     [Google Scholar]
  93. 93. 
    Yu L, Cheng X, Scherpen JMA 2019. Synchronization preserving model reduction of multi-agent network systems by eigenvalue assignments. Proceedings of the 58th IEEE Conference on Decision and Control7794–99 Piscataway, NJ: IEEE
     [Google Scholar]
  94. 94. 
    Fujimoto K, Scherpen JMA. 2010. Balanced realization and model order reduction for nonlinear systems based on singular value analysis. SIAM J. Control Optim. 48:4591–623
     [Google Scholar]
  95. 95. 
    Scherpen JMA. 2011. Balanced realization, balanced truncation and the Hankel operator. The Control Handbook: Control System Advanced Methods W Levine 4–124 Boca Raton, FL: CRC
     [Google Scholar]
  96. 96. 
    Scarciotti G, Astolfi A. 2005. Nonlinear model reduction by moment matching. Found. Trends Syst. Control 4:224–409
     [Google Scholar]
  97. 97. 
    Ishizaki T, Sandberg H, Johansson KH, Kashima K, Imura J, Aihara K 2013. Structured model reduction of interconnected linear systems based on singular perturbation. Proceedings of the 2013 American Control Conference5524–29 Piscataway, NJ: IEEE
     [Google Scholar]
  98. 98. 
    Jaoude DA, Farhood M. 2017. Balanced truncation model reduction of nonstationary systems interconnected over arbitrary graphs. Automatica 85:405–11
     [Google Scholar]
  99. 99. 
    Necoara I, Ionescu TC. 2020. H2 model reduction of linear network systems by moment matching and optimization. IEEE Trans. Autom. Control 65:5328–35
     [Google Scholar]
  100. 100. 
    Cheng X, Scherpen JMA. 2018. Robust synchronization preserving model reduction of Lur'e networks. Proceedings of the 16th European Control Conference2254–59 Piscataway, NJ: IEEE
     [Google Scholar]
  101. 101. 
    Forrow A, Woodhouse FG, Dunkel J 2018. Functional control of network dynamics using designed Laplacian spectra. Phys. Rev. X 8:041043
     [Google Scholar]
  102. 102. 
    Jongsma HJ, Trentelman HL, Camlibel KM 2017. Model reduction of networked multiagent systems by cycle removal. IEEE Trans. Autom. Control 63:657–71
     [Google Scholar]
/content/journals/10.1146/annurev-control-061820-083817
Loading
Model Reduction Methods for Complex Network Systems
Annual Review of Control, Robotics, and Autonomous Systems 4, 425 (2021); https://doi.org/10.1146/annurev-control-061820-083817
/content/journals/10.1146/annurev-control-061820-083817
/content/journals/10.1146/annurev-control-061820-083817
Loading

Data & Media loading...

  • Article Type: Review Article

Most Cited Most Cited RSS feed

This is a required field
Please enter a valid email address
Approval was a Success
Invalid data
An Error Occurred
Approval was partially successful, following selected items could not be processed due to error