复杂网络中最小驱动边的选取研究

陈志昂 纪志坚

摘要：  针对复杂网络中边动态的能控性问题，本文主要对有向复杂网络下维持系统边能控的最小驱动边的选取问题进行研究。建立了复杂网络中边动态的系统模型，从结构能控性和精确能控性两个方面研究边动态能控性，提出了边控制力的概念。同时，对有向复杂网络中最小驱动边的选取提出了新的算法，并通过实例，对所提出的理论结果进行验证。验证结果表明，与以往驱动边的选取方法相比，新算法建立在Kalman秩判据基础之上，通过引入边控制力的概念，可有效避免干扰，从而更加精准高效地寻找维持网络边动态能控所需的最小驱动边，且该算法适用于任意结构的有向复杂网络。该研究为解决具有任意结构复杂网络的边能控性问题和最小驱动边的选取问题提供了理论基础。

关键词：  复杂网络;  最小驱动边;  边能控;  边动态

中图分类号： TP273; TP393 文献标识码： A

自然界中存在着各种复杂网络，不仅包括城市交通网络和电力网络等有形网络，而且还包括人际关系网络、代谢网络和生态网络等无形网络[12]。因此，对复杂网络可控性的研究已成为近10年来的热点问题。为理解复杂网络的演化及网络结构和动态过程之间的相互关系[34]，国内外学者做了很多研究，但复杂网络的可控性问题仍然没有得到解决。R.E.Kalman[5]最先提出了动态系统可控性的概念，即用一组代数矩阵来检验给定系统是否可控，然而由于网络中权重测量的困难性，使用固定权重很难在数值上验证Kalman能控性。因此，Lin C T[6]从图论的角度分析了复杂网络的可控性，提出了结构能控性的概念，并给出了代表该系统可控的关键结构——仙人掌，这为复杂网络的结构化系统理论奠定了基础。与Kalman能控性相比，结构能控性具有简洁直接的优点，而且它还可以避免复杂繁琐的代数运算。近年来，由于复杂网络控制问题的重要性，国内外学者对复杂网络可控性的研究越来越多[710]。Liu Y Y等人[11]研究了复杂网络结构能控性的最小输入定理。尽管结构能控性理论为解决有向网络的可控性问题提供了有效工具，但当网络中的边为无向边或有链接权重时，便违反了结构能控性理论中参数自由的条件。为解决该问题，Yuan Z Z等人[12]提出了精确能控性的概念，并证明了网络完全能控所需的最小驱动节点数等于系统矩阵中特征值的最大幾何重数。大多数关于网络可控性的研究都集中在节点动力学系统上，而在许多现实世界的网络中，边动态系统的研究具有非常重要的意义。例如，在具有路由器（定向网络）的互联网中，边表示物理连接，譬如无线连接。因此，研究边动态比研究点动态更有意义。2011年，T.Nepusz等人[13]首次提出了复杂网络边动态的概念，并构造了边动态系统的数学模型，分析了网络节点的度对动态系统边能控性的影响，证明了网络G边动态系统完全能控所需的驱动边的最小数目等于其线图L（G）所对应的邻接矩阵W的秩亏的数目;Pang S P等人[14]研究了边动态系统特性，通过引入精确能控性理论，提出了研究复杂网络边能控性的框架。目前，关于边动态的研究取得了一定进展[1516]，但对于任意网络结构和任意链接权重下的复杂网络，仍然缺少一个通用的边能控性框架。基于此，本文主要对无权重的有向复杂网络的边能控性进行深入研究，提出了边控制力的概念，并在边控制力的基础上设计了一种新的算法，该算法可以准确高效地找到一组能使网络边动态能控的最小驱动边。该研究为复杂网络边动态中最小驱动边的选取提供了理论基础。

1 预备知识

1.2 边动态能控性分析

经典Kalman能控性判据表明，对于由式（2）描述的动态系统，如果在有限时间内，可以驱使系统从任意初始状态到达任意最终状态，则称该系统是完全能控。当系统完全能控时，可控性矩阵C满秩，即rank＼[C=H，WH，…，WM-1H＼]=M，其中M表示网络中状态边的数量;当系统不完全能控时，此时rank（C）

在计算可控性矩阵的秩rank（C）时，需要状态矩阵W-T和输入矩阵H中的元素参数。然而对于大多数复杂网络系统，矩阵中的元素参数通常并不可得知，因此矩阵W-T和矩阵H通常被视为结构矩阵[6]，即矩阵中的元素为0，或者是独立的自由参数。如果存在一组非零元素赋给状态矩阵W-T和输入矩阵H后，系统满足Kalman能控性判据，即此时可控性矩阵C满秩，则称该系统在结构上是可控的。

基于以上分析，对于由式（2）描述的动态系统，其系统可控性可依据结构能控性理论进行研究。假定矩阵W-T和矩阵H是结构矩阵，即其元素是零或独立的自由参数，由线图的性质可知，线图L（G）中的节点对应原始图G中的边。因此，在结构能控性理论中，可以通过计算线图L（G）中节点的最大匹配数来确定原始网络G中的最小驱动边数。根据精确能控性理论，具有相同对角元素的阻尼矩阵T，对式（2）所确定的系统可控性并没有影响，这是被严格证明的[13]。阻尼矩阵T映射到拓扑图中为自环，因此由阻尼矩阵T产生的所有自环，在分析边动态系统能控性时可以被忽略。基于以上分析，边动态系统能控性的关键是确定线图L（G）中驱动边的最小数目MD（原始图G中驱动节点的最小数目ND）及最小驱动边（驱动节点）的位置。

当输入矩阵H未知时，找到一组能使系统完全能控的驱动边尤为重要。Pang S P等人[15]通过将精确能控性理论引入边动态系统，提出了一个边动态的理论框架，即复杂网络边动态中任意节点的可控性完全由其对应的局部加权结构决定。虽然该框架为复杂网络边动态中驱动边最小数目的确定提供了理论基础，但该理论框架并不是对任意结构的网络都适用。对于任意结构的复杂网络，仍然缺乏一个广泛通用的框架对其边动态能控性进行分析。

2 主要结论

2.1 相关概念

虽然边动态系统的能控性对复杂网络能控性的研究非常重要，但对于边动态中最小驱动边的选取问题却少有研究。受点动态系统中控制集中性[18]概念的启发，为更深入的研究边动态系统的能控性，本文引入边控制力概念。

定义1 边控制力。对于系统（2），C（xi）的值等于当仅有输入信号ui被添加到边缘xi时可控性矩阵C的秩。C（xi）的值表示边xi对系统（2）的控制能力，称为边控制力。其中可控性矩阵C=＼[H，WH，…，WM-1H＼]，输入矩阵H=＼[ui＼]。根据定义1，边xi的控制力C（xi）的值越大，表明边xi在系统能控性中起的作用越大。

定义2 被控边。由输入信号ui直接作用的状态边称被控边。

定义3 最小驱动边和最小驱动边集。在所有被控边中选择一个最大的集合，如果集合中的所有边都不与其它边共享相同的输入，则该集合称为最小驱动边集，用MODS表示。该集合中的边称为最小驱动边，驱动边的数目记为MD。

定义4 无效边。被控边中，不能维持系统完全能控的边称为无效边。

引理1[15] 网络G中，驱动边的最小数量MD为M-rank（W），矩阵W中的线性相关行所对应的边，是系统完全可控所需的最小数目的驱动边。外部输入信号ui应该施加在驱动边尾部节点上。

基于精确能控性理论和线图性质，可以证明线图L（G）中驱动节点（原图G中的驱动边）的最小数目为M-rank（W），其中M为网络G中的边数，最小驱动边的数目MD等于矩阵W的秩亏，即MD=M-rank（W）。对于任意结构的有向网络G，最小驱动边数MD由系统矩阵中零特征值[19]对应的最大几何重数决定，可用下式计算

MD=max{1，M-rank（W）}（3）

当M=rank（W）时，最小驱动边的数量MD=1，此时至少需要一个输入来控制网络，在这种情况下，任意一条边都可以被选为驱动边。

利用引理1和式（3）可以求取维持系统能控的最小驱动边的数量，并判断系统（2）边能控所需的所有驱动边，但需要强调的是，引理1提到的最小驱动边的选取方式不严格，并且只对大型稀疏网络有效[19]。在研究复杂网络边动态能控性的过程中存在两个关键问题，一是维持系统能控的驱动边的最小数目，二是最小驱动边的位置。事实上，后者比前者更复杂。关于第2个问题，现有理论（如引理1）并没有提供一个有效的方法，因为在一些特殊的网络中，引理1提到的方法不足以确保网络完全能控。因此，确定具有任意结构的边动态系统，完全可控所需的最小驱动边非常重要。

2.2 最小驱动边的算法实现

最小驱动边的选取方法是从邻接矩阵W中的线性相关行中进行选取，矩阵W中的线性相关行所对应的边是维持系统边动态能控所需的最小驱动边。然而在有些网络中，并非所有线性相关行所对应的边都适合选作驱动边，因为即使在有些边上添加独立的输入信号后，系统依然不满足Kalman能控性条件[20]。考虑到该问题，本文提出以下算法来选取能使系统边能控的最小驱动边。该算法根据边控制力的大小来选取一组满足Kalman秩判据的驱动边，为有向复杂网络最小驱动边的选取提供有效工具。最小驱动边的选取步骤如下：

與以往驱动边的选取方法不同，新算法建立在Kalman秩判据的基础上，使得该算法能避免无效边的干扰，更加精确的找到一组满足边动态系统能控的最小数目的驱动边，而且该算法对任意结构的有向复杂网络都适用。

2.3 实例分析

本文给出实例，对所提出的理论结果进行验证。考虑一个由6个状态节点组成的有向无权重复杂网络，6节点有向无权重网络如图1所示。

由以上步骤可知，满足系统边能控所需的最小驱动边集为MODS={x1，x5}。即分别对边x1和边x5添加独立的外部输入，可使图1所示网络满足边动态能控。

由以上例子可以看出，与以往方法相比，新算法在Kalman秩判据基础上引入边控制力的概念，在边动态中最小驱动边的选取上更精确，能够有效避免无效边;同时，通过边控制力的大小可以分析每条边在系统能控性中占据的作用，从而有针对性的改善系统能控性。

3 结束语

本文从结构能控性和精确能控性两方面，对有向无权重复杂网络中的边动态能控性进行分析，提出了边控制力的概念，并对边动态中最小驱动边的选取问题设计了新算法。与以往最小驱动边的选取方法相比，新算法可以更精确高效的实现有向复杂网络的边动态可控，但对于更为复杂的网络，尤其是无向网络，本文设计的算法在实现此类网络最小驱动边的选取上还存在一定的困难，需要后续研究来解决此问题。本文研究的边动态中最小驱动边的选取算法，为以后解决更复杂的边动态能控性问题提供了新的方法和方向。

参考文献：

[1] 汪小帆， 李翔， 陈关荣.网络科学导论[M]. 北京： 高等教育出版社， 2012.

[2] 汪小帆， 李翔， 陈关荣. 复杂网络理论及其应用[M]. 北京： 清华大学出版社， 2006.

[3] Newman M E J. The structure and function of complex networks[J]. SIAM Review， 2003， 45（2）： 167256.

[4] Albert R， Barabasi A L. Statistical mechanics of complex networks[J]. Reviews of Modern Physics， 2002， 74（1）： 4797.

[5] Kalman R E. Mathematical description of linear dynamical systems[J]. SIAM J Control， 1963， 1（2）： 152192.

[6] Lin C T. Structural controllability[J]. IEEE Transactions on Automatic Control， 1974， 19（3）： 201208.

[7] Qi Y Q， Zhang H S. Output feedback control and stabilization for multiplicative noise systems with intermittentobservations[J]. IEEE Transactions on Cybernetics， 2017， 48（8）： 21282138.

[8] Commault C， Jacob W， Boukhobza T. On the fixed controllable subspace in linear structured systems[J]. Systems & Control Letters， 2017， 102（7）： 4247.

[9] Ji Z J， Yu H S. A new perspective to graphical characterization of multiagent controllability[J]. IEEE Transactions on Cybernetics， 2016， 47（6）： 14711483.

[10] Shields R W， Pearson J B. Structural controllability of multiinputlinear systems[J]. IEEE Transactions on Automatic Control， 1976， 21（2）： 203212.

[11] Liu Y Y， Slotine J J， Barabsi A L. Controllability of complex networks[J]. Nature， 2011， 473（7346）：  167173.

[12] Yuan Z Z， Zhao C， Di Z R， et al. Exact controllability of complex networks[J]. Nature Communications， 2013（4）： 24472455.

[13] Nepusz T， Vicsek T. Controlling edge dynamics in complex networks[J]. Nature Physics， 2012， 8（7）： 568573.

[14] Pang S P， Hao F. Controllable subspace of edge dynamics in complex networks[J]. Physica A： Statistical Mechanics and its Applications， 2017， 481：  209223.

[15] Pang S P， Wang W X， Hao F， et al. Universal framework for edge controllability of complex networks[J]. Science Reports， 2017， 7（1）： 42244235.

[16] Gao J X， Liu Y Y， Souza D， et al. Target control of complex networks[J]. Nature Communications， 2014， 12（5）： 54155422.

[17] Hosoe S. Determination of Ggenericdimensions of controllable subspaces and its application[J]. IEEE Transactions on Automatic Control， 1980， 25（6）： 11921196.

[18] Liu Y Y， Slotine J J， Barabási A L. Control centrality and hierarchical structure in complex networks[J]. PLos One， 2012， 7（9）： e44459.

[19] Miller I. Probability， random variables， and stochastic processes[J]. IEEE Transactions on Acoustics Speech， 2003， 33（6）： 16371637.

[20] Poljak S. On the generic dimension of controllable subspaces[J]. IEEE Transactions on Automatic Control， 1990， 35（3）： 367369.