第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·
·594· 智能系统学报 第14卷 2)和3)均为减边操作，这个过程可能会出现孤立 100甲 节点，因此2)和3)中进行减边操作后均跳转1)， 呢 &c0) 且对特征结构的判断顺序按照上述步骤进行。 oc-1) 60 d(0)+c(-1) 当经过3)完成优化时，则说明此时的网络中不存 在独立共连结构和互连共连结构这两种特征结 构，0/一1特征值对应入一A矩阵的行相关性极大 地减小，最小控制输入也随之减小，整个网络的 可控性将得到提高。在优化过程中，由于会消除 0.0450.0900.9100.9551.00 独立共连结构，优化结果可以保证网络中不存在 (a)ER 孤立节点这一特殊的独立共连结构，因此可以使 100 -Na 网络结构具有一定的连通性，维持网络的基本通 4c0) 80 信功能。 0 c-1) c(0+c(-1) 60 4验证分析 % 为了说明0/-1特征值与网络可控性的关系 20 以及本文可控性优化的有效性，进行3组验证 实验。 0 0.0600.7800.8200.8800.9401.00 4.10/-1特征值的验证 (b)NW 本组实验通过对比0/-1特征值的几何重数 100 和基于PBH求解的最小控制输入个数Na,来说 -N 明0/-1特征值对网络可控性的影响。 c0) 0 c-1) 特征值0所对应0-A矩阵的行相关性可由 60 c0+c-1) 特征值0的几何重数c(0)量化求得： 40 c(0)=N-rank(A) (6) 特征值-1所对应-1-A矩阵的行相关性可 20 由特征值-1的几何重数c(-1)量化求得： c(-1)=N-rank(A+I) (7) 12345678910111213141516 2，每个参数均独立生成了 控制输入个数分别为50、51、50。对3个网络分 20个网络，求出的实验数值均为20个网络的平 别实施3.3节的优化步骤，计算每个步长下经过 均值。实验结果如图3所示。 结构控制后网络的可控性。网络可控性的度量指 从图3可以看出，0/-1特征值的几何重数之 标为根据式(1)计算的n,实验结果如图4所示。 从图4可以看出，虽然在经过某些步长后， 和，基于PBH求得的最小控制输入个数，二者几 n。没有发生变化或者升高，但从整体来看3个网 乎是一致的。这就说明了在所有-A矩阵的行 络的可控性指标na均呈现了降低趋势。na没有 相关情况中，即便有非重复相关也是占极少数， 发生变化或者升高是由于在消除两种典型结构的 而0/-1特征值对应的相关情况基本决定了网络 过程中，可能会产生新的结构，出现新的行相关 的最小控制输入，极大地影响着网络可控性。 情况，尤其是在消除互连共连结构时，其实很容
2）和 3）均为减边操作，这个过程可能会出现孤立 节点，因此 2）和 3）中进行减边操作后均跳转 1）， 且对特征结构的判断顺序按照上述步骤进行。 当经过 3）完成优化时，则说明此时的网络中不存 在独立共连结构和互连共连结构这两种特征结 构，0/−1 特征值对应 λkI−A 矩阵的行相关性极大 地减小，最小控制输入也随之减小，整个网络的 可控性将得到提高。在优化过程中，由于会消除 独立共连结构，优化结果可以保证网络中不存在 孤立节点这一特殊的独立共连结构，因此可以使 网络结构具有一定的连通性，维持网络的基本通 信功能。 4 验证分析 为了说明 0/−1 特征值与网络可控性的关系 以及本文可控性优化的有效性，进行 3 组验证 实验。 4.1 0/−1 特征值的验证 本组实验通过对比 0/−1 特征值的几何重数 和基于 PBH 求解的最小控制输入个数 Nd，来说 明 0/−1 特征值对网络可控性的影响。 特征值 0 所对应 0·I−A 矩阵的行相关性可由 特征值 0 的几何重数 c(0) 量化求得： c (0) = N −rank(A) (6) 特征值−1 所对应−1·I−A 矩阵的行相关性可 由特征值−1 的几何重数 c(−1) 量化求得： c (−1) = N −rank(A+ I) (7) 实验中的网络对象为 ER、NW、BA 3 种典型 的复杂网络，且均为无向网络。由于本文旨在研 究优化步骤对网络可控性的影响，暂不考虑网络 规模，因此为了提高计算速度，所有网络均为 100 个节点，即 N=100。生成不同参数下的 ER、 NW、BA 3 种典型复杂网络，其中，ER 网络、NW 网络的变化参数为连接概率 p，BA 网络的变化参 数为平均度的半值/2，每个参数均独立生成了 20 个网络，求出的实验数值均为 20 个网络的平 均值。实验结果如图 3 所示。 从图 3 可以看出，0/−1 特征值的几何重数之 和，基于 PBH 求得的最小控制输入个数，二者几 乎是一致的。这就说明了在所有 λkI−A 矩阵的行 相关情况中，即便有非重复相关也是占极少数， 而 0/−1 特征值对应的相关情况基本决定了网络 的最小控制输入，极大地影响着网络可控性。 0 20 40 60 80 100 Nd c(0) c(−1) c(0)+c(−1) Nd c(0) c(−1) c(0)+c(−1) Nd c(0) c(−1) c(0)+c(−1) 0 0.060 0.780 0.820 0.880 0.940 1.00 20 40 60 80 100 p (b) NW 1 2 3 4 5 6 7 8 9 10111213141516 0 20 40 60 80 100 /2 (c) BA 0.045 0.090 0.910 0.955 1.00 p (a) ER 图 3 3 种复杂网络的几何重数和最小控制输入 Fig. 3 Geometric multiplicity and minimum control input of three kinds of complex networks 4.2 可控性优化的验证 本组实验从 4.1 节生成的网络中，挑选 ER、 NW、BA 3 个不同类型的网络，挑选网络的最小 控制输入个数分别为 50、51、50。对 3 个网络分 别实施 3.3 节的优化步骤，计算每个步长下经过 结构控制后网络的可控性。网络可控性的度量指 标为根据式 (1) 计算的 nd，实验结果如图 4 所示。 从图 4 可以看出，虽然在经过某些步长后， nd 没有发生变化或者升高，但从整体来看 3 个网 络的可控性指标 nd 均呈现了降低趋势。nd 没有 发生变化或者升高是由于在消除两种典型结构的 过程中，可能会产生新的结构，出现新的行相关 情况，尤其是在消除互连共连结构时，其实很容 ·594· 智 能 系 统 学 报 第 14 卷
第3期 陈兴凯，等：基于0/-1特征值的网络可控性优化研究 ·595· 易就转换成了独立共连结构。但随着2种典型结 表1两个无线网络的信息统计 构的逐渐消除，：逐渐降低，最小控制输人节点 Table 1 The information of two kinds of wireless networks 的个数逐渐减小，即网络的可控性逐渐增强。说 N L Ladd Lsel na n 明经过本文的优化操作后，网络的可控性得到了 网络I 73 53 24190.4110.068 提高。 网络Ⅱ 24636673101360.5930.146 0.50 0.45 从表1中优化前后的可控性度量指标可以看 0.40 出，经过可控性优化后，2个网络的可控性度量指 0.35 标均降低，说明了网络可控性得到了提高。同 0.30 时，通过2个网络的对比可以看出，对于连边较少 0.25 的稀疏网络，优化过程中实施增边操作较多，这 0.20 是由于减边操作极易造成孤立节点，需要通过增 0.15 边进行弥补消除；而对于连边较多的稠密网 0.10 0 10 20 30 40 络，优化过程中实施减边操作较多，这是由于减 步长 边操作不易造成孤立节点，出现增边的情况就相 (a)ER 对较少。 0.50 0.45 5结束语 0.40 0.35 本文为了确定网络可控性度量指标，阐述了 0.30 基于PBH的最小控制输入求解方法；通过分析研 0.25 究0/-1特征值与矩阵-A中行相关性的关系， 0.20 明确了0/-1特征值对网络可控性的影响，提出了 0.15 针对0/-1特征结构的可控性优化方法；通过验证 0.10 0 10 20 30 40 50 分析，证明了0/-1特征值极大地影响着网络可控 步长 (b)NW 性，并且经过本文的可控性优化，网络可控性能 够得到有效地提高。在下一步的研究中，一方面 将对非0/-1特征值，尤其是整数特征值，对应的 网络结构进行分析研究，探究减小非重复相关的 可控性优化方法；另一方面，将考虑网络结构对 03 通信传输的影响，以通信延迟、传输带宽等网络 0.2 性能指标为约束条件，对可控性优化方法中的增 0.1 边或减边操作进一步完善，形成不同的结构调整 策略，提高实际中的应用价值。 10 2030405060 70 步长 参考文献： (c)BA [1]LIU Yangyu,SLOTINE J J,BARABASI A L.Controllab- 图43个网络的网络可控性 ility of complex networks[J].Nature,2011,473(7346): Fig.4 Network controllability of three networks 167-173 4.3实际网络的验证 [2]YUAN Zhengzhong,ZHAO Chen,DI Zengru,et al.Exact 本组实验主要对2个实际的无线网络进行可 controllability of complex networks[J].Nature communic- 控性优化。其中，网络I为无线传感器网络，受 ations,.2013,4:2447. 传感器功耗的限制，其特点是网络连边较少，属 [3]侯绿林，老松杨，肖延东，等.复杂网络可控性研究现状 于稀疏网络。网络Ⅱ为无线通信网络，为满足通 综述J.物理学报，2015,6418)：188901. 信链路需求，其特点是网络连边较多，属于稠密 HOU Lulin,LAO Songyang,XIAO Yandong,et al.Re- 网络。两个网络的节点数量N和连边数量L、优 cent progress in controllability of complex network[J] 化过程中增边数量La和减边数量Le1、优化前可 Acta physica sinica,2015,64(18):188901. 控性度量指标n:和优化后指标m如表1所示。 [4]LIN C T.Structural controllability[J].IEEE transactions on
易就转换成了独立共连结构。但随着 2 种典型结 构的逐渐消除，nd 逐渐降低，最小控制输入节点 的个数逐渐减小，即网络的可控性逐渐增强。说 明经过本文的优化操作后，网络的可控性得到了 提高。 0 10 20 30 40 50 0.10 0.15 0.20 0.25 0.30 0.35 0.40 0.45 0.50 步长 nd (a) ER 0 10 20 30 40 50 0.10 0.15 0.20 0.25 0.30 0.35 0.40 0.45 0.50 步长 nd (b) NW 0 10 20 30 40 50 60 70 0.1 0.2 0.3 0.4 0.5 步长 nd (c) BA 图 4 3 个网络的网络可控性 Fig. 4 Network controllability of three networks 4.3 实际网络的验证 n ′ d 本组实验主要对 2 个实际的无线网络进行可 控性优化。其中，网络Ⅰ为无线传感器网络，受 传感器功耗的限制，其特点是网络连边较少，属 于稀疏网络。网络Ⅱ为无线通信网络，为满足通 信链路需求，其特点是网络连边较多，属于稠密 网络。两个网络的节点数量 N 和连边数量 L、优 化过程中增边数量 Ladd 和减边数量 Ldel、优化前可 控性度量指标 nd 和优化后指标 如表 1 所示。 表 1 两个无线网络的信息统计 Table 1 The information of two kinds of wireless networks N L Ladd Ldel nd n ′ d 网络Ⅰ 73 53 24 19 0.411 0.068 网络Ⅱ 246 36673 10 136 0.593 0.146 从表 1 中优化前后的可控性度量指标可以看 出，经过可控性优化后，2 个网络的可控性度量指 标均降低，说明了网络可控性得到了提高。同 时，通过 2 个网络的对比可以看出，对于连边较少 的稀疏网络，优化过程中实施增边操作较多，这 是由于减边操作极易造成孤立节点，需要通过增 边进行弥补消除；而对于连边较多的稠密网 络，优化过程中实施减边操作较多，这是由于减 边操作不易造成孤立节点，出现增边的情况就相 对较少。 5 结束语 本文为了确定网络可控性度量指标，阐述了 基于 PBH 的最小控制输入求解方法；通过分析研 究 0/−1 特征值与矩阵 λkI-A 中行相关性的关系， 明确了 0/−1 特征值对网络可控性的影响，提出了 针对 0/−1 特征结构的可控性优化方法；通过验证 分析，证明了 0/−1 特征值极大地影响着网络可控 性，并且经过本文的可控性优化，网络可控性能 够得到有效地提高。在下一步的研究中，一方面 将对非 0/−1 特征值，尤其是整数特征值，对应的 网络结构进行分析研究，探究减小非重复相关的 可控性优化方法；另一方面，将考虑网络结构对 通信传输的影响，以通信延迟、传输带宽等网络 性能指标为约束条件，对可控性优化方法中的增 边或减边操作进一步完善，形成不同的结构调整 策略，提高实际中的应用价值。 参考文献： LIU Yangyu, SLOTINE J J, BARABÁSI A L. Controllability of complex networks[J]. Nature, 2011, 473(7346): 167–173. [1] YUAN Zhengzhong, ZHAO Chen, DI Zengru, et al. Exact controllability of complex networks[J]. Nature communications, 2013, 4: 2447. [2] 侯绿林, 老松杨, 肖延东, 等. 复杂网络可控性研究现状 综述[J]. 物理学报, 2015, 64(18): 188901. HOU Lülin, LAO Songyang, XIAO Yandong, et al. Recent progress in controllability of complex network[J]. Acta physica sinica, 2015, 64(18): 188901. [3] [4] LIN C T. Structural controllability[J]. IEEE transactions on 第 3 期 陈兴凯，等：基于 0/-1 特征值的网络可控性优化研究 ·595·
·596· 智能系统学报 第14卷 automatic control,1974,19(3):201-208. Exact controllability of a star-type network[C]//Proceed- [5]POSFAI M,LIU Yangyu,SLOTINE JJ,et al.Effect of ings of the 27th Chinese Control and Decision Confer- correlations on network controllability[J].Scientific re- ence.Qingdao,China,2015:5187-5191. p0rts,2013,3:1067. [14]晁永翠，纪志坚，王耀威，等.复杂网络在路形拓扑结构 [6]徐明，徐传云，曹克非.度相关性对无向网铬可控性的影 下可控的充要条件[J刀.智能系统学报，2015,10(4)： 响.物理学报，2017,66(2)：028901. 577-582. XU Ming,XU Chuanyun,CAO Kefei.Effect of degree CHAO Yongcui,JI Zhijian,WANG Yaowei,et al.Neces- correlations on controllability of undirected networks[J]. sary and sufficient conditions for the controllability of Acta physica sinica,2017,66(2):028901. complex networks with path topology[J].CAAI transac- [7]WANG Wenxu,NI Xuan,LAI Yingcheng,et al.Optimiz- tions on intelligent systems,2015,10(4):577-582. ing controllability of complex networks by minimum struc- [15]胡寿松.自动控制原理M.6版.北京：科学出版社 tural perturbations[J].Physical review E,2012,85(2): 2013:445-456 026115. 作者简介： [8]XIAO Yandong,LAO Songyang,HOU Lulin,et al.Edge 陈兴凯，男，1988年生，博士研究 orientation for optimizing controllability of complex net- 生，主要研究方向为信息安全保障。 works[J].Physical review.E,statistical,nonlinear,and soft 发表学术论文10余篇。 matter physics,2014,90(4):042804. [9]XU Jiuqiang,WANG Jinfa,ZHAO Hai,et al.Improving controllability of complex networks by rewiring links regu- larly[C]//Proceedings of the 26th Chinese Control and De- cision Conference.Changsha,China,2014:642-645. 卢昱.男，1960年生，教授，博士 [10]HOU Lulin,LAO Songyang,SMALL M.et al.Enhan- 生导师，主要研究方向为信息网络安 cing complex network controllability by minimum link 全控制。参与科研项目40余项。发 表学术论文100余篇。 direction reversal[J].Physics letters A,2015,379(20/21): 1321-1325. [11]LI Jingwen,YUAN Zhengzhong,FAN Ying,et al.Con- trollability of fractal networks:an analytical approach[J]. Europhysics letters,2014,105(5):58001. 王凯，男，1993年生，硕士研究 生，主要研究方向为网络安全与人工 [12]XU Ming,XU Chuanyun,WANG Huan,et al.Analytical 智能。发表学术论文5篇。 controllability of deterministic scale-free networks and Cayley trees[J].European physical journal B,2015,88(7): 168. [13]WU Lanping,ZHOU Jikun,YUAN Zhengzhong,et al
automatic control, 1974, 19(3): 201–208. PÓSFAI M, LIU Yangyu, SLOTINE J J, et al. Effect of correlations on network controllability[J]. Scientific reports, 2013, 3: 1067. [5] 徐明, 徐传云, 曹克非. 度相关性对无向网络可控性的影 响[J]. 物理学报, 2017, 66(2): 028901. XU Ming, XU Chuanyun, CAO Kefei. Effect of degree correlations on controllability of undirected networks[J]. Acta physica sinica, 2017, 66(2): 028901. [6] WANG Wenxu, NI Xuan, LAI Yingcheng, et al. Optimizing controllability of complex networks by minimum structural perturbations[J]. Physical review E, 2012, 85(2): 026115. [7] XIAO Yandong, LAO Songyang, HOU Lülin, et al. Edge orientation for optimizing controllability of complex networks[J]. Physical review. E, statistical, nonlinear, and soft matter physics, 2014, 90(4): 042804. [8] XU Jiuqiang, WANG Jinfa, ZHAO Hai, et al. Improving controllability of complex networks by rewiring links regularly[C]//Proceedings of the 26th Chinese Control and Decision Conference. Changsha, China, 2014: 642–645. [9] HOU Lülin, LAO Songyang, SMALL M, et al. Enhancing complex network controllability by minimum link direction reversal[J]. Physics letters A, 2015, 379(20/21): 1321–1325. [10] LI Jingwen, YUAN Zhengzhong, FAN Ying, et al. Controllability of fractal networks: an analytical approach[J]. Europhysics letters, 2014, 105(5): 58001. [11] XU Ming, XU Chuanyun, WANG Huan, et al. Analytical controllability of deterministic scale-free networks and Cayley trees[J]. European physical journal B, 2015, 88(7): 168. [12] [13] WU Lanping, ZHOU Jikun, YUAN Zhengzhong, et al. Exact controllability of a star-type network[C]//Proceedings of the 27th Chinese Control and Decision Conference. Qingdao, China, 2015: 5187–5191. 晁永翠, 纪志坚, 王耀威, 等. 复杂网络在路形拓扑结构 下可控的充要条件[J]. 智能系统学报, 2015, 10(4): 577–582. CHAO Yongcui, JI Zhijian, WANG Yaowei, et al. Necessary and sufficient conditions for the controllability of complex networks with path topology[J]. CAAI transactions on intelligent systems, 2015, 10(4): 577–582. [14] 胡寿松. 自动控制原理[M]. 6 版. 北京: 科学出版社, 2013: 445–456. [15] 作者简介： 陈兴凯，男，1988 年生，博士研究 生，主要研究方向为信息安全保障。 发表学术论文 10 余篇。 卢昱，男，1960 年生，教授，博士 生导师，主要研究方向为信息网络安 全控制。参与科研项目 40 余项。发 表学术论文 100 余篇。 王凯，男，1993 年生，硕士研究 生，主要研究方向为网络安全与人工 智能。发表学术论文 5 篇。 ·596· 智 能 系 统 学 报 第 14 卷