A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
Volume 10 Issue 7
Jul.  2023

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 11.8, Top 4% (SCI Q1)
    CiteScore: 23.5, Top 2% (Q1)
    Google Scholar h5-index: 77, TOP 5
Turn off MathJax
Article Contents
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
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

Input Structure Design for Structural Controllability of Complex Networks

doi: 10.1109/JAS.2023.123504
Funds:  This work was supported in part by the National Natural Science Foundation of China (U1808205, 62173079), and the Natural Science Foundation of Hebei Province of China (F2000501005)
More Information
  • This paper addresses the problem of the input design of large-scale 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 real-world networks to illustrate the effectiveness of the method.

     

  • loading
  • [1]
    L. Li, L. Wang, W. Wu, H. Jia, and Y. Zhang, “A novel hybrid-jump-based 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 attractor-specific 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 meta-information,” 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, “Label-based 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, “Energy-transfer 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 single-input 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 large-scale 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, “Block-based 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 large-scale 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 graph-based 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 Pastor-Satorras 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, “Depth-first search and linear graph algorithms,” in Proc. IEEE Conf. Rec. 12th Annu. Symp., 1971, pp. 114–121.
    [38]
    J. Hopcroft and R. Karp, “An n5/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.

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(9)  / Tables(3)

    Article Metrics

    Article views (465) PDF downloads(75) Cited by()

    Highlights

    • Present a new method that gives the minimum set of controlled nodes to achieve complete controllability of the networks
    • Propose the number of input node theorem, which provides the range of the number of input nodes to achieve minimal structural controllability
    • Propose the input configuration method, which gives the connection relationship between the input node set and the controlled node set

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return