A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
Advanced Search
Volume 6 Issue 5
Sep.  2019

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 15.3, Top 1 (SCI Q1)
    CiteScore: 23.5, Top 2% (Q1)
    Google Scholar h5-index: 77， TOP 5
Turn off MathJax
Article Contents
Article Navigation >  IEEE/CAA Journal of Automatica Sinica  > 2019  >  6(5): 1152-1165
Xichen Wang, Yugeng Xi, Wenzhen Huang and Shuai 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
Citation: Xichen Wang, Yugeng Xi, Wenzhen Huang and Shuai 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
shu

Deducing Complete Selection Rule Set for Driver Nodes to Guarantee Network's Structural Controllability

doi: 10.1109/JAS.2017.7510724

  • Department of Automation, Shanghai Jiao Tong University, Key Laboratory of System Control and Information Processing, Ministry of Education of China, Shanghai, 200240

Funds:

the National Science Foundation of China 61333009

the National Science Foundation of China 61473317

the National Science Foundation of China 61433002

the National Science Foundation of China 61521063

the National Science Foundation of China 61590924

the National Science Foundation of China 61673366

the National High Technology Research and Development Program of China 2015AA043102

More Information
    Abstract
  • Structural controllability is critical for operating and controlling large-scale complex networks. In real applications, for a given network, it is always desirable to have more selections for driver nodes which make the network structurally controllable. Different from the works in complex network field where structural controllability is often used to explore the emergence properties of complex networks at a macro level, in this paper, we investigate it for control design purpose at the application level and focus on describing and obtaining the solution space for all selections of driver nodes to guarantee structural controllability. In accord with practical applications, we define the complete selection rule set as the solution space which is composed of a series of selection rules expressed by intuitive algebraic forms. It explicitly indicates which nodes must be controlled and how many nodes need to be controlled in a node set and thus is particularly helpful for freely selecting driver nodes. Based on two algebraic criteria of structural controllability, we separately develop an input-connectivity algorithm and a relevancy algorithm to deduce selection rules for driver nodes. In order to reduce the computational complexity, we propose a pretreatment algorithm to reduce the scale of network's structural matrix efficiently, and a rearrangement algorithm to partition the matrix into several smaller ones. A general procedure is proposed to get the complete selection rule set for driver nodes which guarantee network's structural controllability. Simulation tests with efficiency analysis of the proposed algorithms are given and the result of applying the proposed procedure to some real networks is also shown, and these all indicate the validity of the proposed procedure.

     

    • FullText(HTML)
  • loading
    • References(41)
  • [1]
    Y. Y. Liu, J. J. Slotine and A. L. Barabasi, "Controllability of complex networks, " Nature, vol. 473, no. 7346, pp. 167-173, May 2011.
    [2]
    J. Ding, Y. Z. Lu, and J. Chu, "Studies on controllability of directed networks with extremal optimization, " Phys. Part A, vol. 392, no. 24, pp. 6603-6615, Dec. 2013.
    [3]
    Z. Yuan, C. Zhao, Z. Di, W X. Wang, and Y. C. Lai, "Exact controllability of complex networks, " Nat. Commun, vol. 4, no. 2447, pp. 6603-6615, Sept. 2013.
    [4]
    X. Zhang, T. Lv, X Y. Yang, and B. Zhang, "Structural controllability of complex networks based on preferential matching, " PLOS One, vol. 9, no. 11, Nov. 2014.
    [5]
    L. Ubeda, C. Herrera-Yage, I. Barriales-Valbuena, and J. Zufiria P., "An algorithm for controllability in complex networks, " Int. J. Comp. Syst. Sci, vol. 3, no. 1, pp. 63-70, Dec. 2013.
    [6]
    D. Das, A. Chatterjee, N. Pal, A. Mukherjee, and M. K Naskar, "A degree-first greedy search algorithm for the evaluation of structural controllability of real world directed complex networks, " Netw. Protoc. Algorithms, vol. 6, no. 1, pp. 1-18, Apr. 2014.
    [7]
    S. A. Mengiste, A. Aertsen, and A. Kumar, "Effect of edge pruning on structural controllability and observability of complex networks, " Sci. Rep, vol. 5, no. 18145, Dec. 2015.
    [8]
    A. Olshevsky, "Minimum input selection for structural controllability, " IEEE ACC, Chicago, USA, pp. 2218-2223, 2015. http://d.old.wanfangdata.com.cn/NSTLHY/NSTL_HYCC0215020507/
    [9]
    S. Assadi, S. Khanna, Y. Li, and M. Preciado V., "Complexity of the minimum input selection problem for structural controllability, " IFAC-PapersOnLine, vol. 48, no. 22, pp. 70-75, Sept. 2015.
    [10]
    R. Haghighi, and H. R. Namazi, "Algorithm for identifying minimum driver nodes based on structural controllability, " Math. Probl. Eng., Oct. 2015.
    [11]
    S. Pequito, S. Kar, and A. P. Aguiar, "On the complexity of the constrained input selection problem for structural linear systems, " Automatica, vol. 62, pp. 193-199, Dec. 2015.
    [12]
    S. Pequito, S. Kar, and A. P. 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.
    [13]
    S. Pequito, Q. Liu, S. Kar, and D. Ilic M., "PMU placement to ensure observable frequency and voltage dynamics: a structured system approach, " HICSS Wailea, USA, pp. 2327-2336, 2013.
    [14]
    X. Liu, and L. Pan, "Detection of driver metabolites in the human liver metabolic network using structural controllability analysis, " BMC Syst. Biol., vol. 8, no. 51, May 2014.
    [15]
    C. Luo, "Local controllability of biological networks, " Ph.D. Dissertation, Dept. Math., NKU, Nanjing, CN, 2015.
    [16]
    A. Vinayagam, T. E. Gibson, H. J. Lee, et al., "Controllability analysis of the directed human protein interaction network identifies disease genes and drug targets, " arXiv preprint arXiv: 1511.07768, Nov. 2015.
    [17]
    C. T. Lin, "Structural controllability, " IEEE Trans. Autom. Control, vol. 19, no. 3, pp. 201-208, Jun. 1974.
    [18]
    R. W. Shields, and J. B. Pearson, "Structural controllability of multi-input linear systems, " in Proc. of 14th IEEE CDC, Houston, USA, pp. 807-809, 1975.
    [19]
    R. W. Shields, and J. B. Pearson, "Structural controllability of multi-input linear systems, " IEEE Trans. Autom. Control, vol. 21, no. 2, pp. 203-212, Apr. 1976.
    [20]
    K. Glover, and L. M. Silverman, "Characterization of structural controllability, " IEEE Trans. Autom. Control, vol. 21, no. 4, pp. 534-537, Aug. 1976.
    [21]
    C. Lin, "System structure and minimal structure controllability, " IEEE Trans. Autom. Control, vol. 22, no. 5, pp. 855-862, Oct. 1977.
    [22]
    M. Morari, and G. Stephanopoulos, "Comments on finding the generic rank of a structural matrix, " IEEE Trans. Autom. Control, vol. 23, no. 3, pp. 509-510, Jun. 1978.
    [23]
    M. Morari and G. Stephanopoulos, "Studies in the synthesis of control structures for chemical processes: Part Ⅱ: structural aspects and the synthesis of alternative feasible control schemes, " AIChE J., vol. 26, no. 2, pp. 232-246, Mar. 1980.
    [24]
    C. R. Burrows and M. N. Sahinkaya, "A new algorithm for determining structural controllability, " Int. J. Control, vol. 33, no. 2, pp. 379-392, 1981. doi: 10.1080/00207178108922931
    [25]
    C. R. Burrows and M. N. Sahinkaya, "A modified algorithm for determining structural controllability, " Int. J. Control, vol. 37, no. 6, pp. 1417-1431, 1983. doi: 10.1080/00207178308933054
    [26]
    G. W. Barton, R. D. Johnston, and M. L. Brisk, "Comments on determining structural controllability, " Int. J. Control, vol. 38, no. 5, pp. 1081-1083, 1983. doi: 10.1080/00207178308933130
    [27]
    R. D. Johnston, G. W. Barton, and M. L. Brisk, "Determination of the generic rank of structural matrices, " Int. J. Control, vol. 40, no. 2, pp. 257-264, 1984. doi: 10.1080/00207178408933271
    [28]
    R. D. Johnston, G. W. Barton, and M. L. Brisk, "Control objective reduction in single-input single-output control schemes, " Int. J. Control, vol. 40, no. 2, pp. 265-270, 1984. doi: 10.1080/00207178408933272
    [29]
    C. Pillou and C. Rech, "Simple algebraic algorithm for determination of the generic-rank of structured systems, " Int. J. Control, vol. 50, no. 4, pp. 1533-1539, 1989. doi: 10.1080/00207178908953445
    [30]
    A. Georgiou and C. A. Floudas, "Optimization model for generic rank determination of structural matrices, " Int. J. Control, vol. 49, no. 5, pp. 1633-1644, 1989. doi: 10.1080/00207178908559730
    [31]
    C. Commault and J. M. Dion, "Sensor location for diagnosis in linear systems: a structural analysis, " IEEE Trans. Autom. Control, vol. 52, no. 2, pp. 155-169, Feb 2007.
    [32]
    C. Commault, J. M. Dion, V. D. J. W. Woude, et al., "Characterization of generic properties of linear structured systems for efficient computations, " Kybernetika -Praha-, vol. 38, no. 5, pp. 503-520, Jan. 2002.
    [33]
    T. Jia and A. L. Barabasi, "Control capacity and a random sampling method in exploring controllability of complex networks, " Sci. Rep, vol. 3, no. 2354, Aug. 2013.
    [34]
    J. Ruths and D. Ruths, "Control profiles of complex networks, " Science, vol. 343, no. 6177, pp. 1373-1376, Mar. 2014.
    [35]
    A. Olshevsky, "Minimal controllability problems, " IEEE Trans. Control Netw. Syst., vol. 1, no. 3, pp. 249-258, Jul. 2014.
    [36]
    D V. Steward, "On an approach to techniques for the analysis of the structure of large systems of equations, " SIAM Rev., vol. 4, no. 4, pp. 321-342, Oct. 1962.
    [37]
    T. Jia, Y. Y. Liu, E. Csoka, M. Posfai, J. J. Slotine, and A. L. Barabasi, "Emergence of bimodality in controlling complex networks, " Nat. Commun., vol. 4, no. 2002, Jun. 2013.
    [38]
    R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, "Network motifs: simple building blocks of complex networks, " Science, vol. 298, no. 5594, pp. 824-827, Oct. 2002.
    [39]
    X. Zhang, J. Han, and W. Zhang, "An efficient algorithm for finding all possible input nodes for controlling complex networks, " Scientific Reports, vol. 7, no. 10677, Sept. 2017.
    [40]
    J. Ding, C. Wen, G. Li, and Z. Chen, "Key nodes selection in controlling complex networks via convex optimization, " IEEE Transactions on Cybernetics, DOI: 10.1109/TCYB.2018.2888953.
    [41]
    W. F. Guo, S. W. Zhang, Q. Q. Shi, et al, "A novel algorithm for finding optimal driver nodes to target control complex networks and its applications for drug targets identification, " BMC Genomics, vol. 19, no. 924, Jan. 2018.
    • Related Articles
    • Supplements(0)

Catalog

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

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

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

    Figures(7)  / Tables(14)

    Get Citation
    PDF
    XML

    Article Metrics

    Article views (1036) PDF downloads(41) Cited by()

    Highlights

    • Control design needs more selections of driver nodes with structural controllability.
    • Complete selection rule set gives an intuitive solution space and is easy to use.
    • A general procedure to deduce the complete selection rule set is proposed.
    • Four algorithms are developed to improve the computational efficiency.
    • The derived selection rule set is proved complete based on theoretical analysis.

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return