admin 管理员组文章数量: 887021
2023年12月23日发(作者：qq群特效代码)
第40卷 第2期2022年 2月
数字技术与应用Digital Technology &ApplicationVol.40 No.2February 2022中图分类号:O231.1 文献标识码:A 文章编号:1007-9416(2022)02-0019-04DOI:10.19695/12-1369.2022.02.07基于大规模网络的结构能控性指数算法*东华大学信息科学与技术学院 曾涛 李晓丽传统的网络能控性是在给定输入下通过能控性判据来判断该网络是否可控，或是寻找使有向网络达到可控时的最少驱动节点集。为了研究网络达到可控时的链路长度，对于一个没有给定输入的有向网络，本文通过对节点度的研究和删除边等操作将有向网络分解成多条控制链，将控制链的根节点作为整个网络的驱动节点集。同时引入能控性指数的概念，对控制链长度进行研究。最后基于节点的度提出了一个算法将有向网络分解成独立可控的控制链,得出网络的驱动节点集和结构能控性指数，通过对大规模随机网络和真实网络的仿真，验证了算法的有效性。现代网络科学中最具挑战性的问题之一是对复杂网络的控制。由于复杂网络具有高维度、非线性等特征，许多研究人员致力于了解复杂网络的结构以及节点间的相互作用[1-2]，但是目前还有特定的框架来解决网络拓扑结构和非线性动力学之间的极其复杂的相互作用问题，因此复杂网络的控制依旧是一个复杂的问题。Liu[3]等人作出了开创性的贡献。提出了最小输入定理来有效地表征有向网络的结构可控性，通过识别最少驱动节点集以实现网络的完全控制。在此基础上将有向网络的结构可控性映射到最大匹配的问题上[4-5]，通过给不匹配的控制节点施加控制使网络可控。但是，最大匹配并不是唯一的，所以在最大匹配的基础上提出了一个算法用于查找所有可能的输入节点使复杂网络可控[6]。开发了一个精确的可控制性框架以替代结构可控制性框架[7]，它提供了一种通用工具来处理具有任意结构和链收稿日期:2021-11-29*基金项目:上海市自然科学基金资助项目(16ZR1446700);上海市浦江人才计划资助项目(18PJ1400100);2020中央高校基本科研业务费专项基金支持资助项目(20D110425)作者简介:曾涛(1996—),男,四川泸州人,硕士研究生,研究方向:复杂网络的控制与研究。通讯作者:李晓丽(1980—),女,上海人,博士,副教授,硕士生导师,研究方向:分布式控制与优化、多自主体系统、复杂网络等理论研究和网络测控系统、物联网技术、图像处理等。19接权重的复杂网络的可控制性，包括有向，无向，加权和无权网络自循环。结构可控性可以通过精确的结构矩阵框架来再现。通过为定向链接分配随机权重来确保结构可控性，证明了独立的驱动节点或外部控制器的最小数量等于网络矩阵所有特征值的最大几何重数。在复杂网络中，节点也是至关重要的存在，很多研究表明驱动节点的选取与度的分布存在关系。发现驱动节点的数量主要由网络的度分布决定，对于密集的网络往往只需要几个控制节点，相反最难控制的是稀疏的不均匀网络，并且驱动节点的选取往往都避开高阶节点[8]。根据每个节点在网络中的作用对节点进行了分类，将节点分为了关键节点，间歇性节点和冗余节点并开发了一个分析框架来识别每个节点的类别，从而发现复杂系统中两种不同的控制模式：集中控制与分布式控制。早在1974年，lin[9]提出了“仙人掌”结构模型，并且提出“扩张”这一概念，指出节点和边的扩张会使网络变得不可控。网络中最重要的结构是连接节点和边的位置，它们确定系统的哪些部分在受到外部控制信号的影响时可以最终控制整个网络的行为，扩张是网络中产生控制输入需求的扩展点，通过扩张能够清楚地了解哪些节点是替代选择以及这些替代选择如何在整个网络中相互关联[10]。研究复杂网络时，对节点和边的思考是非常重要的，本文研究的重点是，对于一个给定的有向网络，由于密集网络不容易控制，稀疏的网络更容易控制。因此，通过对节点度的选取和边的删除将网络分解成多条
第 40 卷数字技术与应用 控制链，通过选取控制链的根节点得出驱动节点集。同时结合结构能控性指数K的概念，对控制链的长度进行研究。1 理论基础1.1 能控性指数K(A,B)是一个拥有N个状态节点和M个控制输入的时不变网络系统：x(t)=Ax(t)+Bu(t)
(1)其中x(t)=(x1(t),x2(t),...,xN(t))T表示t时间下的状态向量，A是N×N维系统矩阵，用来描述各个节点之间的连接关系和连接强度。B是N×M维输入矩阵，用于描述N个状态节点和M个控制输入之间的连接关系。若忽略网络边的权值，用“×”代表非零向量，此时的矩阵称为该系统的结构矩阵。引理:（Kalman秩判据[11]）：系统（1）完全可控的充分必要条件为系统的能控性判别矩阵：C=[B,AB,...,AK-1B,AKB,...,AN-1B]满足：rank(C)=N但是，由于能控性判别矩阵C不是每列都是线性无关的，可能存在某些列线性相关，使得能控性判别矩阵C在(K+1)M列时就已经满秩了。因此我们可以得到一个N×(K+1)M矩阵Q，并且Q满足：Q=[B,AB,...,AKB]。由此我们可以推导出能控性指数的概念。定义：若系统(1)满足(2)和(3)这两种情况时，这里的K称为该系统的能控性指数。rank([B,AB,...,AKB])=N
（2）
rank([B,AB,...,AK-1B])＜N
（3）1.2 结构能控性指数K根据结构可控性可知，系统(A,B)对应的结构矩阵
( )可控且满足(4)和(5)，此时的K称为系统的结构能A，B控性指数。rank (4)（[B,AB,...,AKB]）=Nrank（[BK−1 (5)
,AB,...,AB]）＜N显然，这里的K≤N，表示结构能控性指数K不超过N。结构能控性指数K的物理意义表示从网络系统的控制节点出发通过K次的信息传递可以影响到所有节点，即网络达到可控状态。 2 基于控制链的结构能控性指数如图1所示的结构我们称为控制链，也称之为路20径，控制链是可控的，且从控制链的结构很容易看出控制链的结构能控性指数K为控制链总节点的数量减1。如图1所示的控制链有4个状态节点，所以其结构能控性指数为3[12]。图1 控制链Fig.1 Control chain若一个有N个节点的系统(A,B)对应的结构为控制链且控制链可控，那么该控制链的系统矩阵A和控制矩阵B可以表示为：矩阵中非零元素“×”表示节点之间的连接关系和强度。显然，系统(A,B)的能控性指数为N-1，且满足式子：rank([B,AB,...,AN-1B])=N
rank([B,AB,...,AN-2B])＜N3 Knode算法由上文可知控制链是可控的且结构能控性指数为N-1，同时，稀疏网络和稀疏的节点是容易控制的，对于一个密集网络或者复杂网络，可以考虑将其不断的简化。因此该算法的最终目的是将复杂的有向网络分解成若干条控制链，网络的驱动节点集为所有控制链根节点的集合，整个网络的结构能控性指数为最长控制链的能控性指数。对控制链结构来说，根节点的入度为0，出度为1，我们将所有入度为0的节点作为驱动节点；控制链末端的节点入度为1，出度为0，所以，出度为0的节点当做末端节点；其余节点的入度和出度都为1，且控制链所有节点的入度和出度都不超过1。因此，对复杂网络进行分解时可以参考这个规律，对入度或者出度大于1的
曾涛 李晓丽：基于大规模网络的结构能控性指数算法2022年第 2 期节点进行边删除，在此基础上通过寻找最短路径来限制控制链的长短，使得网络的结构能控性指数不至于过大。本文提出基于节点度的网络分解算法步骤如下：步骤1：初始化集合S1={}，将网络中节点入度大于等于2的节点记为vi(0≤i≤N)，将vi存入集合S1。步骤2：随机选取S1中节点vi进行回溯，回溯至入度为零的节点为止，选取其中路径最短的一条链路，记为LMIN。若最短的链路不止一条，则随机选取一条。步骤3：将步骤2中找出的最短链路LMIN进行保留，删除其他一步可达LMIN的链路和LMIN（除节点vi外）可达其他节点的链路。步骤4：遍历集合S1中所有入度大于等于2的节点直到不存在入度大于2的节点为止。步骤5：初始化集合S2={}，将网络中节点出度大于等于2的节点记为oi(0≤i≤N)，将oi存入集合S2。步骤6：随机选取S2中节点oi向下寻找至出度为零的节点为止，选取其中路径最短的一条链路同时删除与该链路无关的其他链路。步骤7：遍历集合S2中所有出度大于等于2的节点直到不存在出度大于2的节点为止。
Kmax是最大匹配算法下的结构能控性指数K值（控制链路的最大长度），Knode为本文算法下的结构能控性指数K值。真实网络数据集仿真结果如表2所示。通过表1可以看出，本文提供的算法和最大匹配算法拥有相同的最少驱动节点使得网络的结构能控性指数K，本文算法的优势在于，在相同网络和相同的驱动节点下，本文提供的算法拥有更小的结构能控性指数K值，即控制链路相对更短，控制速度更快。同时，针对不同规模的随机网络，当网络的平均度
DrawingNameKnowledge
NationThe crownGD02-C02Food WebChesapeakemangdryFloridaPajekCitationElectronic
CircuitsGlossGTSmallWorldS208aS420aS838aN2382396122252512L8723275419
第 40 卷数字技术与应用 本信息，其中Type表示网络的类型，Name为网络的名称，其他数据与表1保持一致。从表2可以看出，对于真实网络，算法拥有和最大匹配算法一样的最少驱动节点，网络可控时的结构能控性指数K值更小。同时可以看出网络平均度
networks[J].Reviews of Modern Physics,2002,74(1):47-97.[2] Newman structure and function of complex networks[J].
22Siam Review,2003,45(2):167-256.[3] Liu Y Y,Slotine J llability of complex networks[J].
Nature,2011,473(7346):167.[4] Hopcroft J E,Karp R M.A n^5/2 Algorithm for Maximum
Matchings in Bipartite Graphs[C].DBLP,2012:122-125.[5] L Zdeborová,M Mé number of matchings in
random graphs[J].Journal of Statistical Mechanics Theory and
Experiment, 2006,2006(5):2006.[6] Zhang X,Han J,Zhang efficient algorithmfor finding all
possible input nodes for controlling complex networks[J].Scientific
Reports,2017,7(1):10677.[7] Yuan Z,Zhao C,Di Z,et controllability of complex
networks[J].Nature Communications,2013,4(2447):2447.[8] Jia T,Liu Y Y,E Csóka,et nce of bimodality in
controlling complex networks[J].Nature Communications,2013(4).[9] Lin C ural of controllability[J].IEEE Transactions on
Automatic Control,1974,19(3):201-208.
[10] Chung L,Ruths D,ons and degeneracy in network
controllability[J].Scientific Reports,2021,11(1).[11] Dazhong system theoy[M].Beijing China Tsinghua
University press,2002.[12] Mortazavian k-Controllability and k-Observability of
linear systems[M].Springer Berlin Heidelberg,1982.
版权声明：本文标题：基于大规模网络的结构能控性指数算法★ 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/free/1703344472h447775.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论