IEEE/CAA Journal of Automatica Sinica
Citation:  L. F. Wang, Z. F. Li, G. T. Zhao, G. Guo, and Z. Kong, “Input structure design for structural controllability of complex networks,” IEEE/CAA J. Autom. Sinica, vol. 10, no. 7, pp. 1571–1581, Jul. 2023. doi: 10.1109/JAS.2023.123504 
This paper addresses the problem of the input design of largescale complex networks. Two types of network components, redundant inaccessible strongly connected component (RISCC) and intermittent inaccessible strongly connected component (IISCC) are defined, and a subnetwork called a driver network is developed. Based on these, an efficient method is proposed to find the minimum number of controlled nodes to achieve structural complete controllability of a network, in the case that each input can act on multiple state nodes. The range of the number of input nodes to achieve minimal control, and the configuration method (the connection between the input nodes and the controlled nodes) are presented. All possible input solutions can be obtained by this method. Moreover, we give an example and some experiments on realworld networks to illustrate the effectiveness of the method.
[1] 
L. Li, L. Wang, W. Wu, H. Jia, and Y. Zhang, “A novel hybridjumpbased sampling method for complex social networks,” IEEE Trans. Comput. Soc. Syst., vol. 6, no. 2, pp. 241–249, Apr. 2019. doi: 10.1109/TCSS.2019.2893889

[2] 
Y. Wang, C. Piao, C. Liu, C. Zhou, and J. Tang, “Modeling user interests with online social network influence by memory augmented sequence learning,” IEEE Trans. Netw. Sci. Eng., vol. 8, no. 1, pp. 541–554, Jan. 2021. doi: 10.1109/TNSE.2020.3044964

[3] 
J. M. Yang, C. K. Lee, and K. H. Cho, “Stabilizing control of complex biological networks based on attractorspecific network reduction,” IEEE Trans. Control Netw. Syst., vol. 8, no. 2, pp. 928–939, Jun. 2021. doi: 10.1109/TCNS.2020.3041423

[4] 
A. Zarkali, P. Mccolgan, M. Ryten, R. Reynolds, L. A. Leyland, A. J. Lees, G. Rees, and R. S. Weil, “Differences in network controllability and regional gene expression underlie hallucinations in Parkinson's disease,” Brain, vol. 143, no. 11, pp. 3435–3448, Nov. 2020. doi: 10.1093/brain/awaa270

[5] 
B. H. Lee and W. S. Jung, “Analysis on the urban street network of Korea: Connections between topology and metainformation,” Phys. A,Stat. Mech. Appl., vol. 497, pp. 15–25, May 2018. doi: 10.1016/j.physa.2017.12.131

[6] 
X. Niu, T. Chen, C. Q. Wu, J. Niu, and Y. Li, “Labelbased trajectory clustering in complex road networks,” IEEE Trans. Intell. Transp. Syst., vol. 21, no. 10, pp. 4098–4110, Oct. 2020. doi: 10.1109/TITS.2019.2937882

[7] 
P. Cong, Y. Zhang, W. Wang, and N. Zhang, “DND: Driver node detection for control message diffusion in smart transportations,” IEEE Trans. Netw. Service Manag., vol. 18, no. 3, pp. 3583–3594, Sept. 2021. doi: 10.1109/TNSM.2021.3059696

[8] 
D. Zhou, F. Hu, S. Wang, and J. Chen, “Power network robustness analysis based on electrical engineering and complex network theory,” Phys. A,Stat. Mech. Appl., vol. 564, pp. 1–11, Feb. 2021.

[9] 
D. Yang, Y. Sun, B. Zhou, X. Gao, and H. Zhang, “Critical nodes identification of complex power systems based on electric cactus structure,” IEEE Syst. J., vol. 14, no. 3, pp. 4477–4488, Sept. 2020. doi: 10.1109/JSYST.2020.2967403

[10] 
R. E. Kalman, “Mathematical description of linear dynamical systems,” J. Soc. Indust. Appl. Math. Ser. A, vol. 1, no. 2, pp. 152–192, 1963. doi: 10.1137/0301010

[11] 
C. T. Lin, “Structural controllability,” IEEE Trans. Autom. Control, vol. 19, no. 3, pp. 201–208, Jun. 1974. doi: 10.1109/TAC.1974.1100557

[12] 
Y. Liu, J. J. Slotine, and A. L. Barabási, “Controllability of complex networks,” Nature, vol. 473, no. 7346, pp. 167–173, May 2011. doi: 10.1038/nature10011

[13] 
X. Wang, Y. Xi, W. Huang, and S. Jia, “Deducing complete selection rule set for driver nodes to guarantee network’s structural controllability,” IEEE/CAA J. Autom. Sinica, vol. 6, no. 5, pp. 1152–1165, Sept. 2019. doi: 10.1109/JAS.2017.7510724

[14] 
S. Terasaki and K. Sato, “Minimal controllability problems on linear structural descriptor systems,” IEEE Trans. Autom. Control, vol. 67, no. 5, pp. 2522–2528, May 2022. doi: 10.1109/TAC.2021.3079359

[15] 
Y. Lin, J. Sun, G. Li, G. Xiao, C. Wen, L. Deng, and H. Stanley, “Spatiotemporal input control: Leveraging temporal variation in network dynamics,” IEEE/CAA J. Autom. Sinica, vol. 9, no. 4, pp. 635–651, Apr. 2022. doi: 10.1109/JAS.2022.105455

[16] 
J. Jia, H. L. Trentelman, W. Baar, and M. K. Camlibel, “Strong structural controllability of systems on colored graphs,” IEEE Trans. Autom. Control, vol. 65, no. 10, pp. 3977–3990, Oct. 2020. doi: 10.1109/TAC.2019.2948425

[17] 
T. Menara, D. S. Bassett, and F. Pasqualetti, “Structural controllability of symmetric networks,” IEEE Trans. Autom. Control, vol. 64, no. 9, pp. 3740–3747, Sept. 2019. doi: 10.1109/TAC.2018.2881112

[18] 
J. Li, X. Chen, S. Pequito, G. J. Pappas, and V. M. Preciado, “On the structural target controllability of undirected networks,” IEEE Trans. Autom. Control, vol. 66, no. 10, pp. 4836–4843, Oct. 2021. doi: 10.1109/TAC.2020.3041420

[19] 
L. Xiang, Wa ng, F. Chen, and G. Chen, “Controllability of directed networked MIMO systems with heterogeneous dynamics,” IEEE Trans. Control Netw. Syst., vol. 7, no. 2, pp. 807–817, Jun. 2020. doi: 10.1109/TCNS.2019.2948994

[20] 
A. Li, S. Cornelius, Y. Liu, L. Wang, and A. L. Barabási, “The fundamental advantages of temporal networks,” Science, vol. 358, no. 6366, pp. 1042–1046, Nov. 2017. doi: 10.1126/science.aai7488

[21] 
Y. Zhang and T. Zhou, “Minimal structural perturbations for controllability of a networked system: Complexities and appro ximations,” Int. J. Robust Nonlinear Control, vol. 29, no. 12, pp. 4191–4208, Aug. 2019.

[22] 
V. Chanekar, E. Nozari, and J. Cortés, “Energytransfer edge centrality and its role in enhancing network controllability,” IEEE Trans. Netw. Sci. Eng., vol. 8, no. 1, pp. 331–346, Jan. 2021. doi: 10.1109/TNSE.2020.3038309

[23] 
X. Chen, S. Pequito, G. J. Pappas, and V. M. Preciado, “Minimal edge addition for network controllability,” IEEE Trans. Control Netw. Syst., vol. 6, no. 1, pp. 312–323, Mar. 2019. doi: 10.1109/TCNS.2018.2814841

[24] 
P. Yao, B. Y. Hou, Y. J. Pan, and X. Li, “Structural controllability of temporal networks with a single switching controller,” PLoS One, vol. 12, no. 1, pp. 1–15, Jan. 2017.

[25] 
Y. Cui, S. He, M. Wu, C. Zhou, and J. Chen, “Improving the controllability of complex networks by temporal segmentation,” IEEE Trans. Netw. Sci. Eng., vol. 7, no. 4, pp. 2765–2774, Oct. 2020. doi: 10.1109/TNSE.2020.2991056

[26] 
C. Commault and J. M. Dion, “The singleinput minimal controllability problem for structured systems,” Syst. Control Lett., vol. 80, pp. 50–55, Jun. 2015. doi: 10.1016/j.sysconle.2015.03.010

[27] 
S. Pequito, S. Kar, and A. Aguiar, “On the complexity of the constrained input selection problem for structural linear systems,” Automatica, vol. 62, pp. 193–199, Dec. 2015. doi: 10.1016/j.automatica.2015.06.022

[28] 
S. Pequito, S. Kar, and A. Aguiar, “A framework for structural input/output and control configuration selection in largescale systems,” IEEE Trans. Autom. Control, vol. 61, no. 2, pp. 303–318, Feb. 2016. doi: 10.1109/TAC.2015.2437525

[29] 
H. Yin and S. Zhang, “Minimum structural controllability problems of complex networks,” Phys. A,Stat. Mech. Appl., vol. 443, pp. 467–476, Feb. 2016. doi: 10.1016/j.physa.2015.09.010

[30] 
T. Bai, S. Li, Y. Zou, and X. Yin, “Blockbased minimum input design for the structural controllability of complex networks,” Automatica, vol. 107, pp. 68–76, Sept. 2019. doi: 10.1016/j.automatica.2019.05.006

[31] 
M. Doostmohammadian, “Minimal driver nodes for structural controllability of largescale dynamical systems: Node classification,” IEEE Syst. J., vol. 14, no. 3, pp. 4209–4216, Sept. 2020. doi: 10.1109/JSYST.2019.2956501

[32] 
C. Commault and J. van der Woude, “A classification of nodes for structural controllability,” IEEE Trans. Autom. Control, vol. 64, no. 9, pp. 3877–3882, Sept. 2019. doi: 10.1109/TAC.2018.2886181

[33] 
C. Commault and J. M. Dion, “Input addition and leader selection for the controllability of graphbased systems,” Automatica, vol. 49, no. 11, pp. 3322–3328, Nov. 2013. doi: 10.1016/j.automatica.2013.07.021

[34] 
Y. Liu and A. L. Barabási, “Control principles of complex systems,” Rev. Modern Phys., vol. 88, no. 3, p. 035006, Sept. 2016. doi: 10.1103/RevModPhys.88.035006

[35] 
R PastorSatorras and A Vespignani, Evolution and Structure of the Internet: A Statistical Physics Approach, Cambridge, UK: Cambridge University Press, 2004.

[36] 
T. R. Lezon, J. R. Banavar, M. Cieplak, A. Maritan, and N. V. Fedoroff, “Using the principle of entropy maximization to infer genetic interaction networks from gene expression patterns,” Proc. Natl. Acad. Sci., vol. 103, no. 50, pp. 19033–19038, 2006. doi: 10.1073/pnas.0609152103

[37] 
R. Taijan, “Depthfirst search and linear graph algorithms,” in Proc. IEEE Conf. Rec. 12th Annu. Symp., 1971, pp. 114–121.

[38] 
J. Hopcroft and R. Karp, “An n^{5/2} algorithm for maximum matching in bipartite graphs,” SIAM J. Comput., vol. 2, no. 4, pp. 225–231, Dec. 1973. doi: 10.1137/0202019

[39] 
G. Zhao, L. Wang, and B. Guan, “A class of edge set affecting network controllability,” Acta Phys. Sin., vol. 70, no. 14, Jul. 2021.

[40] 
T. Jia, Y. Liu, E. Csóka, M. Pósfai, J. J. Slotine, and A. L. Barabási, “Emergence of bimodality in controlling complex networks,” Nat. Commun., vol. 4. p. 2002, Jun. 2013.

[41] 
R. Zhang, X. Wang, M. Cheng, and T. Jia, “The evolution of network controllability in growing networks,” Phys. A,Stat. Mech. Appl., vol. 520, no. 15, pp. 257–266, Apr. 2019.

[42] 
J. Kunegis, “Konect: The koblenz network collection,” in Proc. 22nd Int. Conf. World Wide Web, 2013, pp. 1343–1350.
