logo

SCIENCE CHINA Information Sciences, Volume 62, Issue 4: 042202(2019) https://doi.org/10.1007/s11432-018-9450-8

Graph partitions and the controllability of directed signed networks

More info
  • ReceivedFeb 13, 2018
  • AcceptedMay 3, 2018
  • PublishedMar 1, 2019

Abstract

This paper studies the controllability problem of signed networks which is presented by weighted and directed signed graphs. Graph partitions such as structural balance and almost equitable partitions (AEPs) are studied. We generalize the definition of AEPs to any graphs, directed or undirected, signed or unsigned, with or without edge weights.Based on AEP theory, a graph-theoretic necessary condition is proposed for the controllability of directed signed networks and an algorithm is given for the computation of the coarsest partition. Besides, the upper bound on the controllable subspace is derived when the system is uncontrollable.


Acknowledgment

This work was supported by National Natural Science Foundation of China (Grant Nos. 61873136, 61374062, 61603288, 61673013), Natural Science Foundation of Shandong Province for Distinguished Young Scholars (Grant No. JQ201419), and Natural Science Foundation of Shandong Province (Grant No. ZR2016JL022).


References

[1] Ren W, Beard R W. Consensus seeking in multiagent systems under dynamically changing interaction topologies. IEEE Trans Autom Control, 2005, 50: 655-661 CrossRef Google Scholar

[2] Liu K, Ji Z, Ren W. Necessary and Sufficient Conditions for Consensus of Second-Order Multiagent Systems Under Directed Topologies Without Global Gain Dependency.. IEEE Trans Cybern, 2017, 47: 2089-2098 CrossRef PubMed Google Scholar

[3] Liu K, Ji Z, Xie G. Consensus for heterogeneous multi-agent systems under fixed and switching topologies. J Franklin Institute, 2015, 352: 3670-3683 CrossRef Google Scholar

[4] Zhang Z, Zhang L, Hao F. Leader-Following Consensus for Linear and Lipschitz Nonlinear Multiagent Systems With Quantized Communication.. IEEE Trans Cybern, 2017, 47: 1970-1982 CrossRef PubMed Google Scholar

[5] Liu K, Ji Z. Consensus of multi-agent systems with time delay based on periodic sample and event hybrid control. Neurocomputing, 2017, 270: 11-17 CrossRef Google Scholar

[6] Jing G, Zheng Y, Wang L. Consensus of Multiagent Systems With Distance-Dependent Communication Networks.. IEEE Trans Neural Netw Learning Syst, 2017, 28: 2712-2726 CrossRef PubMed Google Scholar

[7] Cai N, Diao C, Khan M J. A Novel Clustering Method Based on Quasi-Consensus Motions of Dynamical Multiagent Systems. Complexity, 2017, 2017: 1-8 CrossRef Google Scholar

[8] Xiao F, Shi Y, Ren W. Robustness Analysis of Asynchronous Sampled-Data Multiagent Networks With Time-Varying Delays. IEEE Trans Autom Control, 2018, 63: 2145-2152 CrossRef Google Scholar

[9] Xiao F, Chen T, Gao H. Consensus in time-delayed multi-agent systems with quantized dwell times. Syst Control Lett, 2017, 104: 59-65 CrossRef Google Scholar

[10] Xiao F, Chen T. Adaptive Consensus in Leader-Following Networks of Heterogeneous Linear Systems. IEEE Trans Control Netw Syst, 2018, 5: 1169-1176 CrossRef Google Scholar

[11] Tang H, Li T. Convergence rates of discrete-time stochastic approximation consensus algorithms: Graph-related limit bounds. Syst Control Lett, 2018, 112: 9-17 CrossRef Google Scholar

[12] Tang H, Li T. Continuous-time stochastic consensus: Stochastic approximation and Kalman-Bucy filtering based protocols. Automatica, 2015, 61: 146-155 CrossRef Google Scholar

[13] Xi J, Fan Z, Liu H. Guaranteed-cost consensus for multiagent networks with Lipschitz nonlinear dynamics and switching topologies. Int J Robust NOnlinear Control, 2018, 28: 2841-2852 CrossRef Google Scholar

[14] Liu Y Y, Slotine J J, Barabási A L. Controllability of complex networks. Nature, 2011, 473: 167-173 CrossRef PubMed ADS Google Scholar

[15] Tanner H G. On the controllability of nearest neighbor interconnections. In: Proceedings of the 43rd IEEE Conference on Decision and Control (CDC), 2004. 2467--2472. Google Scholar

[16] Ji Z, Lin H, Lee T H. A graph theory based characterization of controllability for multi-agent systems with fixed topology. In: Proceedings of the 47th IEEE Conference on Decision and Control, 2008. 5262--5267. Google Scholar

[17] Rahmani A, Ji M, Mesbahi M. Controllability of Multi-Agent Systems from a Graph-Theoretic Perspective. SIAM J Control Optim, 2009, 48: 162-186 CrossRef Google Scholar

[18] Ji Z J, Lin H, Tong H L. Controllability of multi-agent systems with switching topology on robotics, automation and mechatronics. In: Proceedings of Conference on Robotics, Automation and Mechatronics, 2008. 421--426. Google Scholar

[19] Ji Z J, Lin H, Gao J W. Eigenvector based design of uncontrollable topologies for networks of multiple agents. In: Proceedings of the 32nd Chinese Control Conference, 2013. 6797--6802. Google Scholar

[20] Parlangeli G, Notarstefano G. On the Reachability and Observability of Path and Cycle Graphs. IEEE Trans Autom Control, 2012, 57: 743-748 CrossRef Google Scholar

[21] Ji Z, Lin H, Yu H. Leaders in multi-agent controllability under consensus algorithm and tree topology. Syst Control Lett, 2012, 61: 918-925 CrossRef Google Scholar

[22] Aguilar C O, Gharesifard B. Graph Controllability Classes for the Laplacian Leader-Follower Dynamics. IEEE Trans Autom Control, 2015, 60: 1611-1623 CrossRef Google Scholar

[23] Li A, Cornelius S P, Liu Y Y. The fundamental advantages of temporal networks. Science, 2017, 358: 1042-1046 CrossRef PubMed ADS arXiv Google Scholar

[24] Ji Z, Lin H, Yu H. Protocols Design and Uncontrollable Topologies Construction for Multi-Agent Networks. IEEE Trans Autom Control, 2015, 60: 781-786 CrossRef Google Scholar

[25] Hsu S P. A necessary and sufficient condition for the controllability of single-leader multi-chain systems. Int J Robust NOnlinear Control, 2017, 27: 156-168 CrossRef Google Scholar

[26] Lu Z, Zhang L, Ji Z. Controllability of discrete-time multi-agent systems with directed topology and input delay. Int J Control, 2016, 89: 179-192 CrossRef Google Scholar

[27] Guan Y, Wang L. Structural controllability of multi-agent systems with absolute protocol under fixed and switching topologies. Sci China Inf Sci, 2017, 60: 092203 CrossRef Google Scholar

[28] Chao Y, Ji Z. Necessary and sufficient conditions for multi-agent controllability of path and star topologies by exploring the information of second-order neighbours. IMA J Math Control Info, 2016, 228: dnw013 CrossRef Google Scholar

[29] Zhao B, Guan Y, Wang L. Non-fragility of multi-agent controllability. Sci China Inf Sci, 2018, 61: 052202 CrossRef Google Scholar

[30] Ji Z, Yu H. A New Perspective to Graphical Characterization of Multiagent Controllability.. IEEE Trans Cybern, 2017, 47: 1471-1483 CrossRef PubMed Google Scholar

[31] Guan Y, Ji Z, Zhang L. Controllability of multi-agent systems under directed topology. Int J Robust NOnlinear Control, 2017, 27: 4333-4347 CrossRef Google Scholar

[32] Liu X, Ji Z. Controllability of multiagent systems based on path and cycle graphs. Int J Robust Nonlin, 2017, 28: 296--309. Google Scholar

[33] Xi J, He M, Liu H. Admissible output consensualization control for singular multi-agent systems with time delays. J Franklin Institute, 2016, 353: 4074-4090 CrossRef Google Scholar

[34] Cai N, He M, Wu Q X, et al. On Almost Controllability of Dynamical Complex Networks with Noises. J Syst Sci Complex, doi: 10.1007/s11424-017-6273-7. Google Scholar

[35] Ji M, Egerstedt M. A graph-theoretic characterization of controllability for multi-agent systems. In: Proceedings of American Control Conference, 2007. 4588--4593. Google Scholar

[36] Egerstedt M. Controllability of networked systems, In: Proceedings of the 19th International Symposium on Mathematical Theory of Networks and Systems, 2010. Google Scholar

[37] Egerstedt M, Martini S, Cao M, et al. Interacting with Networks: How Does Structure Relate to Controllability in Single-Leader, Consensus Networks?. IEEE Contr Syst, 2012, 32: 66-73. Google Scholar

[38] Martini S, Egerstedt M, Bicchi A. Controllability analysis of multi-agent systems using relaxed equitable partitions. INT J SYSTEMS, 2010, 2: 100-121. Google Scholar

[39] Aguilar C O, Gharesifard B. Almost equitable partitions and new necessary conditions for network controllability. Automatica, 2017, 80: 25-31 CrossRef Google Scholar

[40] Zhang S, Cao M, Camlibel M K. Upper and Lower Bounds for Controllable Subspaces of Networks of Diffusively Coupled Agents. IEEE Trans Autom Control, 2014, 59: 745-750 CrossRef Google Scholar

[41] Camlibel M K, Zhang S, Cao M. Comments on 'Controllability analysis of multi-agent systems using relaxed equitable partitions'. IJSCC, 2012, 4: 72-75 CrossRef Google Scholar

[42] Harary F. On the notion of balance of a signed graph. Michigan Math J, 1953, 2143--146. Google Scholar

[43] Sun C, Hu G, Xie L. Controllability of Multiagent Networks With Antagonistic Interactions. IEEE Trans Autom Control, 2017, 62: 5457-5462 CrossRef Google Scholar

[44] Trentelman H L, Stoorvogel A A, Hautus M. Control Theory for Linear Systems. Berlin: Springer, 2001. Google Scholar

[45] Godsil C, Royle G. Algebraic Graph Theory. Berlin: Springer, 2001. Google Scholar

[46] Kalman R E. Mathematical description of linear dynamical systems. Siam J Control, 1963, 1: 152-192. Google Scholar

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1       京公网安备11010102003388号