第14卷第3期 智能系统学报 Vol.14 No.3 2019年5月 CAAI Transactions on Intelligent Systems May 2019 D0:10.11992/tis.201801007 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20180926.1131.002.html 基于0/-1特征值的网络可控性优化研究 陈兴凯'，卢昱，王凯2，杨文兵3 (1.陆军工程大学装备指挥与管理系，河北石家庄050003；2.陆军工程大学装备模拟训练中心，河北石家庄 050003:3.9804厂军代室，云南曲靖655000) 摘要：针对网络可控性的优化问题，本文以PBH判据为基础，介绍了最小控制输入的求解方法以及网络可控 性的定量分析指标：对入-A矩阵的行相关情况进行分类，明确了0/-1特征值与行重复相关、入-A矩阵行相 关性的关系：闸述了0和-1特征值对应的独立共连和互连共连两种具有规律性的特征结构，以消除这两种结 构为基本思路，给出了结构优化的基本步骤。通过实验分析，验证了0/-1特征值能够极大地影响网络的可控 性，结构优化能够提高网络的可控性。研究结果表明：0/-1特征值具有重要性和可控性优化的有效性，可以为 可控性的相关研究提供新方法、新思路。 关键词：网络可控性；最小控制输入：特征值：特征结构：结构优化 中图分类号：TP273文献标志码：A文章编号：1673-4785(2019)03-0589-08 中文引用格式：陈兴凯，卢昱，王凯，等.基于0/-1特征值的网络可控性优化研究J.智能系统学报，2019,14(3)：589-596. 英文引用格式：CHEN Xingkai,,LUYu,WANG Kai,etal.Optimizing network controllability based on eigenvalue 0/-lJl.CAAI transactions on intelligent systems,2019,14(3):589-596. Optimizing network controllability based on eigenvalue 0/-1 CHEN Xingkai',LU Yu',WANG Kai,YANG Wenbing' (1.Equipment Command and Management Department,Army Engineering University,Shijiazhuang 050003,China;2.Equipment Simulation Training Center,Army Engineering University,Shijiazhuang 050003,China;3.9804 Military Representative Office, Qujing 655000,China) Abstract:Optimizing network controllability continues to be a research hotspot in network science.Based on the PBH criterion,in this paper,we introduce the computation method of minimum control input and the quantitative analysis in- dex of network controllability.We classify the row correlations of the matrix and confirm the relationship between eigenvalue 0/-1 and the row repetition correlation as well as the row correlation of matrix -4.We describe two kinds of 0/-1 regularity structures,isolated and connected link structures.Using the method for eliminating these two kinds of regularity structures,we then propose the basic step of structure optimization.Through experimental analysis,we verify that the eigenvalue 0/-1 could greatly influence network controllability,and that structural optimization could improve network controllability.These results not only demonstrate the importance of eigenvalue 0/-1 and the effectiveness of optimizing controllability,but also provide a new method and concept for network controllability research Keywords:network controllability;minimum control input,eigenvalue;feature structure;structure optimization 在当前学科融合的大背景下，网络可控性) 整体的角度去研究如何去控制网络，使网络达到 逐渐受到了人们的广泛关注，它是网络科学借鉴 预期状态。在目前的研究中，影响可控性的因素 了控制科学的思想，将网络看作是一个系统，从 是什么、如何提高可控性一直以来都是网络可控 收稿日期：2018-01-04.网络出版日期：2018-09-28. 性研究中的热点问题。 基金项目：国家自然科学基金项目(61271152)：国家社会科学 基金军事学资助项目(15GJ003-184). 近年来，网络可控性的研究基本上都是围绕 通信作者：陈兴凯.E-mail:chen xingkai@l26.com. 文献[1-2]展开的。文献[1]将Lin的结构可控性定
DOI: 10.11992/tis.201801007 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20180926.1131.002.html 基于 0/-1 特征值的网络可控性优化研究 陈兴凯1 ，卢昱1 ，王凯2 ，杨文兵3 （1. 陆军工程大学 装备指挥与管理系，河北 石家庄 050003; 2. 陆军工程大学 装备模拟训练中心，河北 石家庄 050003; 3. 9804 厂军代室，云南 曲靖 655000） 摘 要：针对网络可控性的优化问题，本文以 PBH 判据为基础，介绍了最小控制输入的求解方法以及网络可控 性的定量分析指标；对 λk I−A 矩阵的行相关情况进行分类，明确了 0/−1 特征值与行重复相关、λk I−A 矩阵行相 关性的关系；阐述了 0 和−1 特征值对应的独立共连和互连共连两种具有规律性的特征结构，以消除这两种结 构为基本思路，给出了结构优化的基本步骤。通过实验分析，验证了 0/−1 特征值能够极大地影响网络的可控 性，结构优化能够提高网络的可控性。研究结果表明：0/−1 特征值具有重要性和可控性优化的有效性，可以为 可控性的相关研究提供新方法、新思路。 关键词：网络可控性；最小控制输入；特征值；特征结构；结构优化 中图分类号：TP273 文献标志码：A 文章编号：1673−4785(2019)03−0589−08 中文引用格式：陈兴凯, 卢昱, 王凯, 等. 基于 0/-1 特征值的网络可控性优化研究[J]. 智能系统学报, 2019, 14(3): 589–596. 英文引用格式：CHEN Xingkai, LU Yu, WANG Kai, et al. Optimizing network controllability based on eigenvalue 0/-1[J]. CAAI transactions on intelligent systems, 2019, 14(3): 589–596. Optimizing network controllability based on eigenvalue 0/-1 CHEN Xingkai1 ，LU Yu1 ，WANG Kai2 ，YANG Wenbing3 (1. Equipment Command and Management Department, Army Engineering University, Shijiazhuang 050003, China; 2. Equipment Simulation Training Center, Army Engineering University, Shijiazhuang 050003, China; 3. 9804 Military Representative Office, Qujing 655000, China) Abstract: Optimizing network controllability continues to be a research hotspot in network science. Based on the PBH criterion, in this paper, we introduce the computation method of minimum control input and the quantitative analysis index of network controllability. We classify the row correlations of the matrix λkI−A and confirm the relationship between eigenvalue 0/−1 and the row repetition correlation as well as the row correlation of matrix λkI−A. We describe two kinds of 0/−1 regularity structures, isolated and connected link structures. Using the method for eliminating these two kinds of regularity structures, we then propose the basic step of structure optimization. Through experimental analysis, we verify that the eigenvalue 0/−1 could greatly influence network controllability, and that structural optimization could improve network controllability. These results not only demonstrate the importance of eigenvalue 0/−1 and the effectiveness of optimizing controllability, but also provide a new method and concept for network controllability research. Keywords: network controllability; minimum control input; eigenvalue; feature structure; structure optimization 在当前学科融合的大背景下，网络可控性[1-3] 逐渐受到了人们的广泛关注，它是网络科学借鉴 了控制科学的思想，将网络看作是一个系统，从 整体的角度去研究如何去控制网络，使网络达到 预期状态。在目前的研究中，影响可控性的因素 是什么、如何提高可控性一直以来都是网络可控 性研究中的热点问题。 近年来，网络可控性的研究基本上都是围绕 文献[1-2]展开的。文献[1]将 Lin 的结构可控性定 收稿日期：2018−01−04. 网络出版日期：2018−09−28. 基金项目：国家自然科学基金项目 (61271152)；国家社会科学 基金军事学资助项目 (15GJ003-184). 通信作者：陈兴凯. E-mail：chen_xingkai@126.com. 第 14 卷第 3 期 智 能 系 统 学 报 Vol.14 No.3 2019 年 5 月 CAAI Transactions on Intelligent Systems May 2019
·590· 智能系统学报 第14卷 理运用于有向、无权的复杂网络中，基于二部图 可以看出，某些关键特征值与某些具有特征规律 给出了最小控制输入节点（也称为最小驱动节 的网络结构之间存在着必然联系，这些特征值对 点)的求解方法，提出了网络可控性的最大匹配 应的特征结构从某种程度上决定了网络的可控 理论和最小输入定理。文献[2]则是将研究对象 性，如果能够找到关键的特征值，调整特征值对 扩充到无向、同权的复杂网络，提出了基于PBH 应的特征结构，则可以为网络可控性的优化提供 可控性判定的严格可控性理论，具有更广泛的适 新的思路。 用性。上述两篇文献奠定了近年来网络可控性研 综上所述，本文将从具有规律性特征结构的 究的基础，为后续诸多研究提供了理论支撑。对 特征值入手，探究0和-1这两个特殊特征值与网 于影响可控性因素的探索，从文献[1]就开始了， 络可控性之间的关系。通过消除网络中0/-1对 作者探讨了网络可控性与度分布的关系，并且结 应的规律性特征结构，实现网络可控性的提高， 合实际网络，发现稀疏异构网络比稠密同构网络 为网络可控性的优化提供新的方法和思路。 更加难以控制。在随后的研究中，文献[5]研究了 影响可控性的各种网络特性，发现模块性和聚集 1网络可控性 系数没有明显的影响，而出度与入度的对称性对 从定性分析的角度来看，网络可控性是指在 网络可控性有一定的影响。文献[6]则主要针对 某种拓扑结构和控制输入下，网络是否可以达到 无向网络的可控性，利用模拟退火算法改变网络 预期状态。这里的控制输入是指对网络中所有节 的度相关性，发现在度分布不变的情况下，网络 点的控制实施情况，即对网络中的哪些节点进行 可控性会随着度相关系数的增大而单调减小。上 了控制实施，哪些节点没有进行控制实施。 述文献虽然给出了影响网络可控性的某些因素， 从定量分析的角度来看，网络可控性是指在 但并没有给出具体的可控性优化方法。对于如何 某种拓扑结构下，网络运行状态达到预期状态的 提高网络可控性，目前已经开展了诸多研究，如 难易程度，其强弱通常是由量化指标n。表示，即 文献「7通过添边来轻微改动网络结构，从而提高 最小控制输入的节点个数N:与网络节点总数 网络的可控性，并且在同构、异构随机网络和不 N的比值： 同类型的真实网络中进行了验证。文献[8] n Na/N (1) 针对当前复杂网络中的可控性优化问题，从网络 这个指标是以网络可控性的定性判定为基 中边的方向性入手，将EOOC问题转换为交换网 础，求解网络可控下对应的最小控制输人，以最 络的最大独立集问题，最终通过实验表明了网络 小控制输人的节点个数作为可控性量化指标的主 结构可以决定可控性和优化效果。文献[9]提出 要因素，进而对网络可控性进行量化评估。 了一种提高网络可控性的新算法，通过重新连接 1.1定性分析 网络的边来改变网络结构，从而提高可控性，最 网络可控性的定性分析其实是对网络可控与 后在E和无标度网络模型中验证了算法的有效 否的判定，它借鉴了控制科学中可控性的思想， 性。文献[10]提出了一种提高有向网络可控性的 将网络看作是一个系统，以邻接矩阵作为系统矩 方法，该方法是在保持链路总数不变的情况下， 阵，控制输人矩阵作为输入矩阵，根据可控性的 通过改变一小部分链路的方向来实现的，通过数 判定条件对网络系统进行可控性判定。具体而 值模拟验证了方法的有效性，并且说明了该方法 言，对于有N个节点、M个控制输入(M≤WM的网 适用于一些仅知道局部结构信息的网络。从上述 络系统，其状态方程可表述为 文献可以看出，网络可控性的优化研究实质是根 =Ax+Bu (2) 据某一特征因素进行的网络结构调整。对于一些 式中：=[x1x2…wJ为N维网络状态变量；=[4 具有明显规律的网络结构，目前也已展开了可控 性方面的研究，如文献[11]中的分形网络、文献[12] h2…4为M维输入变量；A为NxN维网络拓 中的确定无标度网络和凯莱树，均通过特征值 扑结构的邻接矩阵，A中的元素对应了网络中两 0来确定最小控制输入的节点个数，进而获取网 点的连接情况，即a=0表示i点和j点之间没有 络的可控性。文献[13]中的星型网络则是通过特 连接，a=1表示i点和j点之间有连接，本文研究 征多项式给出了最小控制输入节点个数的计算表 的网络为更具一般性的无自环、无向网络，因此 达式；文献[14]针对路形拓扑结构，提出了不可控 有a0且a,Fam:B为WxM维控制输入矩阵，B中 特征值的概念并给出了具体表达式。从上述文献 的元素对应了网络中的控制实施情况，每一列和
理 [4]运用于有向、无权的复杂网络中，基于二部图 给出了最小控制输入节点 (也称为最小驱动节 点) 的求解方法，提出了网络可控性的最大匹配 理论和最小输入定理。文献[2]则是将研究对象 扩充到无向、同权的复杂网络，提出了基于 PBH 可控性判定的严格可控性理论，具有更广泛的适 用性。上述两篇文献奠定了近年来网络可控性研 究的基础，为后续诸多研究提供了理论支撑。对 于影响可控性因素的探索，从文献[1]就开始了， 作者探讨了网络可控性与度分布的关系，并且结 合实际网络，发现稀疏异构网络比稠密同构网络 更加难以控制。在随后的研究中，文献[5]研究了 影响可控性的各种网络特性，发现模块性和聚集 系数没有明显的影响，而出度与入度的对称性对 网络可控性有一定的影响。文献[6]则主要针对 无向网络的可控性，利用模拟退火算法改变网络 的度相关性，发现在度分布不变的情况下，网络 可控性会随着度相关系数的增大而单调减小。上 述文献虽然给出了影响网络可控性的某些因素， 但并没有给出具体的可控性优化方法。对于如何 提高网络可控性，目前已经开展了诸多研究，如 文献[7]通过添边来轻微改动网络结构，从而提高 网络的可控性，并且在同构、异构随机网络和不 同类型的真实网络中进行了验证。文献 [ 8 ] 针对当前复杂网络中的可控性优化问题，从网络 中边的方向性入手，将 EOOC 问题转换为交换网 络的最大独立集问题，最终通过实验表明了网络 结构可以决定可控性和优化效果。文献[9]提出 了一种提高网络可控性的新算法，通过重新连接 网络的边来改变网络结构，从而提高可控性，最 后在 ER 和无标度网络模型中验证了算法的有效 性。文献[10]提出了一种提高有向网络可控性的 方法，该方法是在保持链路总数不变的情况下， 通过改变一小部分链路的方向来实现的，通过数 值模拟验证了方法的有效性，并且说明了该方法 适用于一些仅知道局部结构信息的网络。从上述 文献可以看出，网络可控性的优化研究实质是根 据某一特征因素进行的网络结构调整。对于一些 具有明显规律的网络结构，目前也已展开了可控 性方面的研究，如文献[11]中的分形网络、文献[12] 中的确定无标度网络和凯莱树，均通过特征值 0 来确定最小控制输入的节点个数，进而获取网 络的可控性。文献[13]中的星型网络则是通过特 征多项式给出了最小控制输入节点个数的计算表 达式；文献[14]针对路形拓扑结构，提出了不可控 特征值的概念并给出了具体表达式。从上述文献 可以看出，某些关键特征值与某些具有特征规律 的网络结构之间存在着必然联系，这些特征值对 应的特征结构从某种程度上决定了网络的可控 性，如果能够找到关键的特征值，调整特征值对 应的特征结构，则可以为网络可控性的优化提供 新的思路。 综上所述，本文将从具有规律性特征结构的 特征值入手，探究 0 和−1 这两个特殊特征值与网 络可控性之间的关系。通过消除网络中 0/−1 对 应的规律性特征结构，实现网络可控性的提高， 为网络可控性的优化提供新的方法和思路。 1 网络可控性 从定性分析的角度来看，网络可控性是指在 某种拓扑结构和控制输入下，网络是否可以达到 预期状态。这里的控制输入是指对网络中所有节 点的控制实施情况，即对网络中的哪些节点进行 了控制实施，哪些节点没有进行控制实施。 从定量分析的角度来看，网络可控性是指在 某种拓扑结构下，网络运行状态达到预期状态的 难易程度，其强弱通常是由量化指标 nd [1]表示，即 最小控制输入的节点个数 Nd 与网络节点总数 N 的比值： nd = Nd/N (1) 这个指标是以网络可控性的定性判定为基 础，求解网络可控下对应的最小控制输入，以最 小控制输入的节点个数作为可控性量化指标的主 要因素，进而对网络可控性进行量化评估。 1.1 定性分析 网络可控性的定性分析其实是对网络可控与 否的判定，它借鉴了控制科学中可控性[15]的思想， 将网络看作是一个系统，以邻接矩阵作为系统矩 阵，控制输入矩阵作为输入矩阵，根据可控性的 判定条件对网络系统进行可控性判定。具体而 言，对于有 N 个节点、M 个控制输入 (M≤N) 的网 络系统，其状态方程可表述为 x˙ = Ax+ Bu (2) ··· ··· 式中：x=[x1 x2 xN] T 为 N 维网络状态变量；u=[u1 u2 uM] T 为 M 维输入变量；A 为 N×N 维网络拓 扑结构的邻接矩阵，A 中的元素对应了网络中两 点的连接情况，即 aij=0 表示 i 点和 j 点之间没有 连接，aij=1 表示 i 点和 j 点之间有连接，本文研究 的网络为更具一般性的无自环、无向网络，因此 有 aii=0 且 aij=aji；B 为 N×M 维控制输入矩阵，B 中 的元素对应了网络中的控制实施情况，每一列和 ·590· 智 能 系 统 学 报 第 14 卷
第3期 陈兴凯，等：基于0/-1特征值的网络可控性优化研究 ·591· 每一行最多仅有一个1元素，其他均为0元素，若 式(4)中的PBH判定矩阵[U-AB](以下简 第i行存在1元素则表示对i点有控制实施。 称PBH矩阵)可以写成以下模式： 针对式(2)的网络系统，常用的网络可控性判 -a12.-a1m b 定方法有2种：基本秩判据"和PBH秩判据。 -a21 b, 基本秩判据是根据式(3)进行可控性判据： rank[BABA2B.…A-B]=N (3) -an2 若网络系统满足式(3)，则网络系统是可控 不难看出，PBH矩阵在满秩的情况下，上式 的，否则不可控。 中的矩阵应该满足所有行向量线性不相关，而虚 PBH秩判据是根据式(4)进行可控性判据： 线右边的矩阵B可以消除虚线左边-A中行向 rank [AB]N.k=1,2,...,N (4) 量组的相关性，这就为求出矩阵B提供了实现方 式中：1k为邻接矩阵A所对应的所有特征值。若 法：首先计算出，-A,再将其进行初等列变换， 网络系统满足式(4)，则网络系统是可控的，否则 不改变行相关特性；根据行相关情况，通过设置 不可控。 最少的b,消除1-A的行相关性，使得PBH矩阵 从上述2种判定方法不难看出，网络可控性 中的所有行向量均不相关：最后将所有λ.对应的 的定性分析取决于邻接矩阵A和控制输入矩阵 b,设置情况进行整合，使得b,可以消除所有1对 B,即网络可控与否是由网络的拓扑结构和控制 应的PBH矩阵中行向量的相关性，即满足式 输人共同决定的。 (4)。此时，所对应的b,即组成最小控制输入对应 1.2定量分析 的矩阵B,最小控制输入的节点个数N:=rank(B)。 从网络可控性的定性分析不难看出，在某种 求出后，则可根据式(I)得到网络可控性 拓扑结构下，对网络所有节点实施控制（即M=W, 的度量指标n,完成定量分析。 则网络必定可以达到可控状态。然而，此时所实 20/-1特征值 施的控制不一定是最优的，因为对于任何一种网 络拓扑而言，最优的控制输人应该是使得网络达 从最小控制输入的求解可以看出，影响网络 到可控状态时，对网络中最少的节点实施控制。 可控性的直接因素是PBH矩阵中4I-A矩阵的 这种针对网络拓扑结构的最优控制即最小控制 行相关性。而行相关性不仅受到邻接矩阵A的 输入。最小控制输入的节点个数直接反映了在某 影响，还受到特征值的影响。虽然对于大部分 种拓扑结构下网络达到可控性的难易程度，即可 特征值而言，它们与行相关之间的联系并没有明 用于可控性的定量分析。因此，对网络可控性进 显的规律性，但0和-1这两个特征值却比较特 行定量分析的关键是求解出最小控制输入的节点 殊，它们不仅与行相关之间存在着一定联系，更 个数。 是极大地影响着网络可控性。 根据式(3)或式(4)的可控性判据，可以为最 2.1行相关类型 小控制输入的求解提供基本思路：针对邻接矩阵 对于-A矩阵的行相关性可以分为3类：零 A,求出满足式(3)或式(4)的最简矩阵B。最直 向量相关、重复相关和非重复相关。 接的方法是代入法，即针对网络中的所有节点， 1)零向量相关即存在全0行的行向量。以 将可能的控制输入由少至多进行遍历组合，生成 A,表示A的第x行，则零向量相关表现为 Ai1=Ai2=…=Am=0 所有可能情况下的输入矩阵B,由简至繁逐一代 例如A2=A=0,如下所示： 入式(3)或式(4)进行验证，一旦出现判定为可 [100001 控，则可将此时的矩阵B确定最小控制输入。然 00000 而，对于n个节点的网络而言，求出所有矩阵 00000 01000 B的计算复杂程度为CW+C%++CN=2W-1,显 00100 然，代入法在n较大的情况下是不适用的。如果 2)重复相关即存在完全相同的相关行向量。 不通过代入法求最小控制输入，式(3)由于涉及 以A表示A的第x行，则重复相关表现为 矩阵相乘，求出矩阵B是十分困难的。因此，较 Ai1=A2=…=Aim 为可行的代数方法是基于式(4)的PBH秩判据。 例如A=A=A3,如下所示：
每一行最多仅有一个 1 元素，其他均为 0 元素，若 第 i 行存在 1 元素则表示对 i 点有控制实施。 针对式 (2) 的网络系统，常用的网络可控性判 定方法有 2 种：基本秩判据[1]和 PBH 秩判据[2]。 基本秩判据是根据式 (3) 进行可控性判据： rank[B AB A2B··· A N−1B] = N (3) 若网络系统满足式 (3)，则网络系统是可控 的，否则不可控。 PBH 秩判据是根据式 (4) 进行可控性判据： rank[λk I− AB] = N, k = 1,2,··· ,N (4) 式中：λk 为邻接矩阵 A 所对应的所有特征值。若 网络系统满足式 (4)，则网络系统是可控的，否则 不可控。 从上述 2 种判定方法不难看出，网络可控性 的定性分析取决于邻接矩阵 A 和控制输入矩阵 B，即网络可控与否是由网络的拓扑结构和控制 输入共同决定的。 1.2 定量分析 从网络可控性的定性分析不难看出，在某种 拓扑结构下，对网络所有节点实施控制 (即 M=N)， 则网络必定可以达到可控状态。然而，此时所实 施的控制不一定是最优的，因为对于任何一种网 络拓扑而言，最优的控制输入应该是使得网络达 到可控状态时，对网络中最少的节点实施控制。 这种针对网络拓扑结构的最优控制即最小控制 输入。最小控制输入的节点个数直接反映了在某 种拓扑结构下网络达到可控性的难易程度，即可 用于可控性的定量分析。因此，对网络可控性进 行定量分析的关键是求解出最小控制输入的节点 个数。 C 1 N C 2 N ··· C N N 2 N −1 根据式 (3) 或式 (4) 的可控性判据，可以为最 小控制输入的求解提供基本思路：针对邻接矩阵 A，求出满足式 (3) 或式 (4) 的最简矩阵 B。最直 接的方法是代入法，即针对网络中的所有节点， 将可能的控制输入由少至多进行遍历组合，生成 所有可能情况下的输入矩阵 B，由简至繁逐一代 入式 (3) 或式 (4) 进行验证，一旦出现判定为可 控，则可将此时的矩阵 B 确定最小控制输入。然 而，对于 n 个节点的网络而言，求出所有矩阵 B 的计算复杂程度为 + + + = ，显 然，代入法在 n 较大的情况下是不适用的。如果 不通过代入法求最小控制输入，式 (3) 由于涉及 矩阵相乘，求出矩阵 B 是十分困难的。因此，较 为可行的代数方法是基于式 (4) 的 PBH 秩判据。 式 (4) 中的 PBH 判定矩阵[λkI−A B](以下简 称 PBH 矩阵) 可以写成以下模式： λk −a12 ··· −a1n −a21 λk ··· −a2n . . . . . . −an1 −an2 ··· λk b1 b2 . . . bn 不难看出，PBH 矩阵在满秩的情况下，上式 中的矩阵应该满足所有行向量线性不相关，而虚 线右边的矩阵 B 可以消除虚线左边 λkI−A 中行向 量组的相关性，这就为求出矩阵 B 提供了实现方 法：首先计算出 λkI−A，再将其进行初等列变换， 不改变行相关特性；根据行相关情况，通过设置 最少的 bi 消除 λkI−A 的行相关性，使得 PBH 矩阵 中的所有行向量均不相关；最后将所有 λk 对应的 bi 设置情况进行整合，使得 bi 可以消除所有 λk 对 应的 PBH 矩阵中行向量的相关性，即满足式 (4)。此时，所对应的 bi 即组成最小控制输入对应 的矩阵 B，最小控制输入的节点个数 Nd=rank(B)。 求出 Nd 后，则可根据式 (1) 得到网络可控性 的度量指标 nd，完成定量分析。 2 0/−1 特征值 从最小控制输入的求解可以看出，影响网络 可控性的直接因素是 PBH 矩阵中 λk I−A 矩阵的 行相关性。而行相关性不仅受到邻接矩阵 A 的 影响，还受到特征值 λk 的影响。虽然对于大部分 特征值而言，它们与行相关之间的联系并没有明 显的规律性，但 0 和−1 这两个特征值却比较特 殊，它们不仅与行相关之间存在着一定联系，更 是极大地影响着网络可控性。 2.1 行相关类型 对于 λkI-A 矩阵的行相关性可以分为 3 类：零 向量相关、重复相关和非重复相关。 1) 零向量相关即存在全 0 行的行向量。以 Ax 表示 A 的第 x 行，则零向量相关表现为 Ai1 = Ai2 = ··· = Aim = 0 例如 A2=A3=0，如下所示： 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 2) 重复相关即存在完全相同的相关行向量。 以 Ax 表示 A 的第 x 行，则重复相关表现为 Ai1 = Ai2 = ··· = Aim 例如 A1=A2=A3，如下所示： 第 3 期 陈兴凯，等：基于 0/-1 特征值的网络可控性优化研究 ·591·
·592· 智能系统学报 第14卷 10000 于-A矩阵为对角线均为的实对称矩阵，且 10000 其中的元素仅有0和-1两种，因此从形成的难易 1 0000 01000 程度上来看，在入-A矩阵中形成零向量相关、重 00100 复相关比非重复相关要容易很多，即所有 3)非重复相关即存在不同的行向量，它们之 入-A矩阵的行相关中绝大部分都是零向量相关 间存在相关性。以A.表示A的第x行，则非重复 和重复相关。由定理1和定理2可知，零相关均 相关表现为 由特征值0决定，重复相关均由特征值0/-1决 Aio=kAi+kA++kmAim 定，不难得出，相对于其他特征值，特征值0/-1极 例如A,=A+A2,如下所示： 大地影响着-A矩阵的相关性，即网络中绝大 「100001 部分的最小控制输入节点是由特征值0/-1所决 01000 11000 定的。 00100 00010 3可控性优化 2.20/-1特征值与行相关性的关系 在上述3种相关情况中，非重复相关与特征 相对于0/-1特征值而言，非0-1特征值对可 值之间的联系很难找到：而零向量相关与0特征 控性的影响相对较小，并且难以找到具有明显规 律性的特征结构。而0/-1特征值对可控性的影 值、重复相关与0/-1特征值之间存在着明显的联 响相对较大，并且具有明显的对应特征结构。因 系，具体联系可由下述两个定理描述： 此，可以通过消除0/-1的特征结构，从而减小 定理1如果矩阵-A中存在着零向量相 关，则对应特征值一定为0。 0/-1对应1-A矩阵中的行相关性，最终达到提 证明设矩阵-A中零向量行为第i行，即 高网络可控性的目的，实现网络的可控性优化。 [-a1-a2…-ai-k-aG+y…-aw]=0 3.10特征结构 则有 在特征值0对应的特征结构中，存在着一种 aa=0,x=l,2…,N且x≠i。证毕 具有明显规律性的特征结构，其具体定义如下： 1=0 定义1独立共连结构。独立共连结构是指 定理2如果矩阵-A中存在着行重复相 网络中存在若干节点（称为对象节点），这些节点 关，则对应特征值，一定为0或-1。 之间是独立不相连的，且它们与网络中其他节点 证明设矩阵1I-A中重复相关的行为第 的连接状况完全相同。如图1中的对象节点1、 i行和第j行，即 2、3构成了独立共连结构。 [-aa-az.-aai-1-aait)-anj-)-aij-aaj).-aiN]= -a1-a2-at-)-at-a+).-a-1)k-aj+1)-aw 则有 ∫ax=ax,x=1,2,…,N,x≠i,j ay=an=-hk 因为A中的元素仅有0或1，即a=0或a1, 所以40或-1。证毕 由定理1和定理2可知，在-A矩阵的所有 图1独立共连结构 行相关中，如果存在零向量相关，那么一定是0特 Fig.1 The isolated link structure 征值决定的：如果存在重复相关，那么一定是 对于上述的独立共连结构，存在着一种特殊 0/-1特征值决定的。其他非0/-1特征值所对应 情况：当对象节点与网络中其他节点的连接情况 的-A矩阵不可能出现零向量相关和重复相关。 均为不相连时，对象节点均为孤立节点。 对于零向量相关、重复相关和非重复相关这 独立共连结构与特征0的关系可由下述定理 3种-A矩阵的行相关性而言，形成零向量相关 描述： 至少需要有一行为全零行，形成重复相关至少需 定理3如果一个网络中存在独立共连结 要有两行完全相同，形成非重复相关至少需要有 构，则该网络的邻接矩阵A具有特征值0。 三行并且通过合适的系数组成相关组。而且由 证明邻接矩阵A的特征值λ，满足：
1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 3) 非重复相关即存在不同的行向量，它们之 间存在相关性。以 Ax 表示 A 的第 x 行，则非重复 相关表现为 Ai0 = k1Ai1 +k2Ai2 +···+km Aim 例如 A3=A1+A2，如下所示： 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 2.2 0/−1 特征值与行相关性的关系 在上述 3 种相关情况中，非重复相关与特征 值之间的联系很难找到；而零向量相关与 0 特征 值、重复相关与 0/−1 特征值之间存在着明显的联 系，具体联系可由下述两个定理描述： 定理 1 如果矩阵 λkI−A 中存在着零向量相 关，则对应特征值 λk 一定为 0。 证明 设矩阵 λkI−A 中零向量行为第 i 行，即 [ −ai1 −ai2 ··· −ai(i−1)λk −ai(i+1) ··· −aiN] = 0 则有 { aix = 0, x=1,2,··· ,N且x , i λk= 0 。 证毕 定理 2 如果矩阵 λkI−A 中存在着行重复相 关，则对应特征值 λk 一定为 0 或 −1。 证明 设矩阵 λ k I−A 中重复相关的行为第 i 行和第 j 行，即 [ −ai1−ai2···−ai(i−1)λk−ai(i+1)···−ai(j−1)−ai j−ai(j+1) ··· −aiN] = [ −aj1−aj2···−aj(i−1)−aji−aj(i+1) ··· −aj(j−1)λk−aj(j+1) ···−ajN] 则有 { aix = ajx, x=1,2,··· ,N,x , i, j ai j = aji = −λk 因为 A 中的元素仅有 0 或 1，即 aij=0 或 aij=1， 所以 λk=0 或 λk=−1。证毕 由定理 1 和定理 2 可知，在 λkI−A 矩阵的所有 行相关中，如果存在零向量相关，那么一定是 0 特 征值决定的；如果存在重复相关，那么一定是 0/−1 特征值决定的。其他非 0/−1 特征值所对应 的 λkI−A 矩阵不可能出现零向量相关和重复相关。 对于零向量相关、重复相关和非重复相关这 3 种 λkI−A 矩阵的行相关性而言，形成零向量相关 至少需要有一行为全零行，形成重复相关至少需 要有两行完全相同，形成非重复相关至少需要有 三行并且通过合适的系数组成相关组。而且由 于 λkI−A 矩阵为对角线均为 λk 的实对称矩阵，且 其中的元素仅有 0 和 −1 两种，因此从形成的难易 程度上来看，在 λkI−A 矩阵中形成零向量相关、重 复相关比非重复相关要容易很多，即所 有 λkI−A 矩阵的行相关中绝大部分都是零向量相关 和重复相关。由定理 1 和定理 2 可知，零相关均 由特征值 0 决定，重复相关均由特征值 0/−1 决 定，不难得出，相对于其他特征值，特征值 0/−1 极 大地影响着 λkI−A 矩阵的相关性，即网络中绝大 部分的最小控制输入节点是由特征值 0/−1 所决 定的。 3 可控性优化 相对于 0/−1 特征值而言，非 0/−1 特征值对可 控性的影响相对较小，并且难以找到具有明显规 律性的特征结构。而 0/−1 特征值对可控性的影 响相对较大，并且具有明显的对应特征结构。因 此，可以通过消除 0/−1 的特征结构，从而减小 0/−1 对应 λkI−A 矩阵中的行相关性，最终达到提 高网络可控性的目的，实现网络的可控性优化。 3.1 0 特征结构 在特征值 0 对应的特征结构中，存在着一种 具有明显规律性的特征结构，其具体定义如下： 定义 1 独立共连结构。独立共连结构是指 网络中存在若干节点 (称为对象节点)，这些节点 之间是独立不相连的，且它们与网络中其他节点 的连接状况完全相同。如图 1 中的对象节点 1、 2、3 构成了独立共连结构。 1 2 3 4 5 … … … … 图 1 独立共连结构 Fig. 1 The isolated link structure 对于上述的独立共连结构，存在着一种特殊 情况：当对象节点与网络中其他节点的连接情况 均为不相连时，对象节点均为孤立节点。 独立共连结构与特征 0 的关系可由下述定理 描述： 定理 3 如果一个网络中存在独立共连结 构，则该网络的邻接矩阵 A 具有特征值 0。 证明 邻接矩阵 A 的特征值 λk 满足： ·592· 智 能 系 统 学 报 第 14 卷
第3期 陈兴凯，等：基于0-1特征值的网络可控性优化研究 ·593· (g)=det(I-A)=0 (5) -1 -1 -01+1 … -dIN 当网络中存在孤立节点时，不妨设节点1为 -1 -1 一d1+1 -QIN 孤立节点，则det(-A)为 0 0 -1 -1 -01+l … 0 -dIN -a21 -a23 -d2N -ai+1.1-a+12 -a+1 -0+1,it2 -aNI 1 -dm -dn -aNN-1 -aN2 显然，当入=0时，dt2-A)中存在全0行，使 显然，当=-1时，det(-A)中的1到i行完 全相同，使得det(1-A)=0,因此o(-1)=0,即-1为 得det(-A)=0,因此p(O)=0,即0为A的特征值。 A的特征值。证毕。 当网络中存在不含孤立节点的独立共连结 3.3结构优化 构时，不妨设1到i点为独立共连结构，则 独立共连结构和互连共连结构是0/-1特征 detk【-A)为 结构中具有明显规律性的结构，为了提高网络的 0 -a1,+1 0 0 可控性，则可以通过消除网络中的这2种结构，减 -01+1 -41N 少0/-1特征值对应，-A矩阵的行相关性，即减 0 -01+1 -1N 少最小控制输人的节点个数，从而实现可控性的 -a+11-a41.2 -ai+l.i Ak -0i+1,i+2 -☑i+1N 优化。 本文中的优化方法主要是基于邻接矩阵A来 -aN -aN.N-1 找到两种典型的0/-1特征结构，通过对矩阵A中 显然，当=0时，det(-A)中的1到i行完全 对应元素的改变来实现节点之间的增边或减边， 相同，使得det(2-A)=0,因此o(0)=0,即0为A的 从而实现结构优化操作。由0-A=-A可知，消除 特征值。证毕。 独立共连结构的处理对象为矩阵-A(或A),消除 3.2-1特征结构 全0行则可消除孤立节点，消除相同行则可消除 在特征值一1对应的特征结构中，存在着一种 不含孤立节点的独立共连结构；由-1·-A=--A 具有明显规律性的特征结构，其具体定义如下： 可知，消除互连共连结构的处理对象为矩阵 定义2互连共连结构。互连共连结构是指 -I-A(或A+),消除相同行则可消除互连共连结 网络中存在若干节点（称为对象节点），这些节点 构。在整个结构优化过程中，设置每个步长只允 之间是互相连接的，且它们与网络中其他节点的 许对一条边进行一次增边或减边操作，则优化的 连接状况完全相同。如图2中的对象节点1、2、 主要步骤如下： 3构成了互连共连结构。 1)逐行判断矩阵A是否存在全0行。如果存 在且第i行为全0行，则随机生成一个整数，有 je(1,且j,令a=1,a=l,跳转1)继续运行；如 果不存在全0行，则跳转2)。 2)逐行对比矩阵A中的其他行是否存在相同 行。如果存在相同行，则获取对象点集CP、共连 点集SP,随机生成2个整数i和j,有i∈CP, 图2互连共连结构 j∈SP,令a=0,a,=0,跳转1)；如果不存在相同 Fig.2 The connected link structure 行，则跳转3)。 互连共连结构与特征-1的关系可由下述定 3)逐行对比矩阵A+I中的其他行是否存在相 理描述： 同行。如果存在相同行，则获取对象点集CP、共 定理4如果一个网络中存在互连共连结 连点集SP,随机生成两个整数i和j,有i∈CP, 构，则该网络的邻接矩阵A具有特征值-1。 j∈SP,令a,=0,a=0,跳转1)；如果不存在相同 证明邻接矩阵A的特征值4满足式（⑤），不 行，则完成网络可控性的优化。 妨设1到i点为互连共连结构，则det(2-A)为 上述主要步骤中，为了减小网络的复杂程度
φ(λk) = det(λk I− A) = 0 (5) 当网络中存在孤立节点时，不妨设节点 1 为 孤立节点，则 det(λkI−A) 为 λk 0 0 ··· 0 −a21 λk −a23 ··· −a2N . . . . . . . . . −aN1 −aN2 ··· λk 显然，当 λk=0 时，det(λkI−A) 中存在全 0 行，使 得 det(λkI−A)=0，因此 φ(0)=0，即 0 为 A 的特征值。 当网络中存在不含孤立节点的独立共连结 构时，不妨 设 1 到 i 点为独立共连结构，则 det(λk I−A) 为 λk 0 ··· 0 −a1,i+1 ··· −a1N 0 λk ··· 0 −a1,i+1 ··· −a1N . . . . . . . . . . . . . . . 0 0 ··· λk −a1,i+1 ··· −a1N −ai+1,1 −ai+1,2 ··· −ai+1, j λk −ai+1,i+2 −ai+1,N . . . . . . . . . . . . . . . −aN1 −aN2 −aN3 −aN4 ··· −aN,N−1 λk 显然，当 λk=0 时，det(λkI−A) 中的 1 到 i 行完全 相同，使得 det(λkI−A)=0，因此 φ(0)=0，即 0 为 A 的 特征值。证毕。 3.2 −1 特征结构 在特征值 −1 对应的特征结构中，存在着一种 具有明显规律性的特征结构，其具体定义如下： 定义 2 互连共连结构。互连共连结构是指 网络中存在若干节点 (称为对象节点)，这些节点 之间是互相连接的，且它们与网络中其他节点的 连接状况完全相同。如图 2 中的对象节点 1、2、 3 构成了互连共连结构。 1 3 2 4 5 … … … … 图 2 互连共连结构 Fig. 2 The connected link structure 互连共连结构与特征 −1 的关系可由下述定 理描述： 定理 4 如果一个网络中存在互连共连结 构，则该网络的邻接矩阵 A 具有特征值 −1。 证明 邻接矩阵 A 的特征值 λk 满足式 (5)，不 妨设 1 到 i 点为互连共连结构，则 det(λkI−A) 为 λk −1 ··· −1 −a1,i+1 ··· −a1N −1 λk ··· −1 −a1,i+1 ··· −a1N . . . . . . . . . . . . . . . . . . −1 −1 ··· λk −a1,i+1 ··· −a1N −ai+1,1 −ai+1,2 ··· −ai+1, j λk −ai+1,i+2 −ai+1,N . . . . . . . . . . . . . . . −aN1 −aN2 −aN3 −aN4 ··· −aN,N−1 λk 显然，当 λk=−1 时，det(λkI−A) 中的 1 到 i 行完 全相同，使得 det(λkI−A)=0，因此 φ(−1)=0，即−1 为 A 的特征值。证毕。 3.3 结构优化 独立共连结构和互连共连结构是 0/−1 特征 结构中具有明显规律性的结构，为了提高网络的 可控性，则可以通过消除网络中的这 2 种结构，减 少 0/−1 特征值对应 λkI−A 矩阵的行相关性，即减 少最小控制输入的节点个数，从而实现可控性的 优化。 本文中的优化方法主要是基于邻接矩阵 A 来 找到两种典型的 0/−1 特征结构，通过对矩阵 A 中 对应元素的改变来实现节点之间的增边或减边， 从而实现结构优化操作。由 0·I−A=−A 可知，消除 独立共连结构的处理对象为矩阵−A(或 A)，消除 全 0 行则可消除孤立节点，消除相同行则可消除 不含孤立节点的独立共连结构；由−1·I−A=−I−A 可知，消除互连共连结构的处理对象为矩阵 −I−A(或 A+I)，消除相同行则可消除互连共连结 构。在整个结构优化过程中，设置每个步长只允 许对一条边进行一次增边或减边操作，则优化的 主要步骤如下： 1）逐行判断矩阵 A 是否存在全 0 行。如果存 在且第 i 行为全 0 行，则随机生成一个整数 j，有 j∈(1,N) 且 j≠i，令 aij=1，aji=1，跳转 1）继续运行；如 果不存在全 0 行，则跳转 2）。 2）逐行对比矩阵 A 中的其他行是否存在相同 行。如果存在相同行，则获取对象点集 CP、共连 点 集 S P，随机生 成 2 个 整 数 i 和 j， 有 i∈C P， j∈SP，令 aij=0，aji=0，跳转 1）；如果不存在相同 行，则跳转 3）。 3）逐行对比矩阵 A+I 中的其他行是否存在相 同行。如果存在相同行，则获取对象点集 CP、共 连点集 SP，随机生成两个整数 i 和 j，有 i∈CP， j∈SP，令 aij=0，aji=0，跳转 1）；如果不存在相同 行，则完成网络可控性的优化。 上述主要步骤中，为了减小网络的复杂程度， 第 3 期 陈兴凯，等：基于 0/-1 特征值的网络可控性优化研究 ·593·