### Matching Algorithms of Minimum Input Selection for Structural Controllability Based on Semi-Tensor Product of Matrices

FAN Naqi1, ZHANG Lijun1,2, ZHANG Shenggui3, LIU Jiuqiang4

1. 1. College of Intelligent Systems Science and Engineering, Harbin Engineering University, Harbin 150001, China;
2. School of Marine Technology, Northwestern Polytechnical University, Xi'an 710072, China;
3. School of Mathematics and Statistics, Northwestern Polytechnical University, Xi'an 710129, China;
4. College of Big Data Statistics, Guizhou University of Finance and Economics, Guiyang 550025, China
• Received:2021-06-02 Revised:2021-09-25 Online:2022-10-25 Published:2022-10-12
• Supported by:
This research was supported by the National Natural Science Foundation of China under Grant Nos.61573288,12071370,U1803263,71973103 and Key Programs in Shaanxi Province of China under Grant No.2021JZ-12.

FAN Naqi, ZHANG Lijun, ZHANG Shenggui, LIU Jiuqiang. Matching Algorithms of Minimum Input Selection for Structural Controllability Based on Semi-Tensor Product of Matrices[J]. Journal of Systems Science and Complexity, 2022, 35(5): 1808-1823.

In 2011,Liu,et al.investigated the structural controllability of directed networks.They proved that the minimum number of input signals,driver nodes,can be determined by seeking a maximum matching in the directed network.Thus,the algorithm for seeking a maximum matching is the key to solving the structural controllability problem of directed networks.In this study,the authors provide algebraic expressions for matchings and maximum matchings proposed by Liu,et al.(2011) via a new matrix product called semi-tensor product,based on which the corresponding algorithms are established to seek matchings and maximum matchings in digraphs,which make determining the number of driver nodes tractable in computer.In addition,according to the proposed algorithm,the authors also construct an algorithm to distinguish critical arcs,redundant arcs and ordinary arcs of the directed network,which plays an important role in studying the robust control problem.An example of a small network from Liu's paper is used for algorithm verification.
 [1] Lin C T, Structural controllability, IEEE Transactions on Automatic Control, 1974, 19(3):201-208.[2] Liu Y, Slotine J J, and Barabási A, Controllability of complex networks, Nature, 2011, 473(7346):167-173.[3] Edmonds J, Maximum matching and a polyhedron with (0, 1) vertices, Res. Nat. Bur. Standards, 1965, 69(1-2):125-130.[4] Yu S S, Zhong S, and Hu S H, Matching algorithms for general graphs based on depth-first search, Computer Engineering and Science, 2008, 30:45-48.[5] Madry A, Navigating central path with electrical flows:From flows to matchings, and back, Foundations of Computer Science, 2013, 253-262.[6] Yuan Z Z, Zhao C, Di Z R, et al., Exact controllability of complex networks, Nature Communications, 2013, 4:2447.[7] Olshevsky A, Minimum input selection for structural controllability, Proceedings of the American Control Conference, 2015, 2218-2223.[8] Yin H L and Zhang S Y, Minimum structural controllability problems of complex networks, Physica A:Statistical Mechanics and Its Applications, 2016, 443:467-476.[9] Bai T, Li S Y, Zou Y Y, et al., Block-based minimum input design for the structural controllability of complex networks, Automatica, 2019, 107:68-76.[10] Cheng D Z, Qi H S, and Zhao Y, An Introduction to Semi-Tensor Product of Matrices and Its Applications, Word Scientific, Beijing, 2012.[11] Wang Y Z, Zhang C H, and Liu Z B, A matrix approach to graph maximum stable set and coloring problems with application to multi-agent systems, Automatica, 2012, 48(7):1227-1236.[12] Meng M and Feng J E, A matrix approach to hypergraph stable set and coloring problems with its application to storing problem, Journal of Applied Mathematics, 2014, 2014(3):1-9.[13] Xu M and Wang Y, Robust graph coloring based on the matrix semi-tensor product with application to examination timetabling, Control Theory and Technology, 2014, 12(2):187-197.[14] Liu Z B and Wu Y Q, L (p, q)-label coloring problem via the semi-tensor product method, Proceedings of the 202039th Chinese Control Conference (CCC), Shenyang, 2020.[15] Zhong J, Lu J Q, Huang C, et al., Finding graph minimum stable set and core via semi-tensor product approach, Neurocomputing, 2016, 174:588-596.[16] Yan Y Y, Yue J M, Chen Z Q, et al., Algebraic expression and construction of control sets of graphs using semi-tensor product of matrices, IEEE Access, 2019, 7:113440-113451.[17] Liu X Y and Zhu J D, On potential equations of finite games, Automatica, 2016, 68:245-253.[18] Guo P L and Wang Y Z, The computation of Nash equilibrium in fashion games via semi-tensor product method, Journal of Systems Science&Complexity, 2016, 29(4):881-896.[19] Chen L, Networked evolutionary model of snow-drift game based on semi-tensor product, Journal of Applied Mathematics and Physics, 2019, 7(3):726-737.[20] Dou W H, Li H T, and Alsaadi F E, Semi-tensor product approach to controllability, reachability, and stabilizability of probabilistic finite automata, Mathematical Problems in Engineering, 2019, 2019:1-7.[21] Yue J M, Yan Y Y, and Chen Z Q, Three matrix conditions for the reduction of finite automata based on the theory of semi-tensor product of matrices, Science China Information Sciences, 2020, 63(2):1-3.[22] Lu J Q, Li M L, Liu Y, et al., Nonsingularity of Grain-like cascade FSRs via semi-tensor product, Science China Information Sciences, 2018, 61(1):1-12.[23] Wang X Y and Gao S, Image encryption algorithm for synchronously updating Boolean networks based on matrix semi-tensor product theory, Information Sciences, 2020, 507:16-36.[24] Wang B and Feng J E, On detectability of probabilistic Boolean networks, Information Sciences, 2019, 483:383-395.[25] Meng M, James L, Feng J E, et al., Stability and stabilization of Boolean networks with stochastic delays, IEEE Transactions on Automatic Control, 2019, 64(2):790-796.[26] Kong X S, Wang S L, Li H T, et al., New developments in control design techniques of logical control networks, Frontiers of Information Technology and Electronic Engineering, 2020, 21:220-233.[27] Wen W Y, Hong Y K, Fang Y M, et al. A visually secure image encryption scheme based on semi-tensor product compressed sensing, Signal Processing, 2020, 173:107580.[28] Liu Y C and Zhang W, Boolean Methodology, Shanghai Technology Literature, Shanghai, 1993.[29] Bondy J A and Murty U S R, Graph Theory, Springer, New York, 2008.
 [1] LIU Aixin, LI Haitao, LI Ping, YANG Xinrong. On Basis and Pure Nash Equilibrium of Finite Pure Harmonic Games [J]. Journal of Systems Science and Complexity, 2022, 35(4): 1415-1428. [2] LIU Peng,TIAN Yu-Ping,ZHANG Ya. Leader Selection for Strong Structural Controllability of Single-Integrator Multi-Agent Systems [J]. Journal of Systems Science and Complexity, 2017, 30(6): 1227-1241. [3] GUO Peilian,WANG Yuzhen. The Computation of Nash Equilibrium in Fashion Games via Semi-Tensor Product Method [J]. Journal of Systems Science and Complexity, 2016, 29(4): 881-896. [4] LI Dequan,WANG Xiaofan,YIN Zhixiang. ROBUST CONSENSUS FOR MULTI-AGENT SYSTEMS OVER UNBALANCED DIRECTED NETWORKS [J]. Journal of Systems Science and Complexity, 2014, 27(6): 1121-1137. [5] LI Haitao, WANG Yuzhen, LIU Zhenbin. ON THE OBSERVABILITY OF FREE BOOLEAN NETWORKS VIA THE SEMI-TENSOR PRODUCT METHOD [J]. Journal of Systems Science and Complexity, 2014, 27(4): 666-678. [6] LI Dequan, LIU Qipeng , WANG Xiaofan. DISTRIBUTED QUANTIZED CONSENSUS FOR AGENTS ON DIRECTED NETWORKS [J]. Journal of Systems Science and Complexity, 2013, 26(4): 489-511. [7] Zhongxin LIU ,Zengqiang CHEN ,Zhuzhi YUAN. EVENT-TRIGGERED AVERAGE-CONSENSUS OF MULTI-AGENT SYSTEMS WITH WEIGHTED AND DIRECT TOPOLOGY [J]. Journal of Systems Science and Complexity, 2012, 25(5): 845-855. [8] Yuichi YOSHIDA;Hiro ITO. TESTING k-EDGE-CONNECTIVITY OF DIGRAPHS [J]. Journal of Systems Science and Complexity, 2010, 23(1): 91-101. [9] Yan LIU;Shi Ying WANG. THE CONNECTIVITY OF MAXIMUM MATCHING GRAPHS [J]. Journal of Systems Science and Complexity, 2004, 14(1): 33-38. [10] Young-Gheel Baik;Yan Quan FENG;Hyo-Seob Sim. THE NORMALITY OF CAYLEY GRAPHS OF FINITE ABELIAN GROUPS WITH VALENCY 5 [J]. Journal of Systems Science and Complexity, 2000, 13(4): 425-431. [11] Cai Maocheng. PACKING AND COVERING WITH ARBORESCENCES [J]. Journal of Systems Science and Complexity, 1991, 4(4): 362-367.
Viewed
Full text

Abstract