复杂网络控制研究综述
2021-05-03
来源:独旅网
2014年第4期 闽南师范大学学报(自然科学版) No.4.2014年 (总第86期) Journal of Minnan Normal University(Nat.Sci.) General No.86 复杂网络控制研究综述 袁正中 (闽南师范大学数学与统计学院,福建漳州363000) 摘要:复杂网络的控制研究已经成为复杂网络领域的一个热点课题.本文简述了复杂网络控制的近期研究进 展,包括结构控制和严格控制的研究情况,并提出了复杂网络严格控制方面的后继研究内容,为复杂网络严格控 制研究指明了方向. 关键词:复杂网络;结构控制;严格控制;驱动节点 中图分类号:0231 文献标志码:A 文章编号:2095—7122(2014)04一-O031—04 A Review of Controlling Complex Networks YUAN Zheng——zhong (School of Mathematics and Statistics,Minnan Normal University,Zhangzhou,Fujian 363000,China) Abstract:Controlling complex networks is a popular topic of complex network.In this paper,a review of controlling complex networks is made include structural control and exact contro1.Moreover,it discusses some research item about exact control to give the right direction of exact contro1. Key words:complex network;structural control;exact control;driver nodes 在信息时代,复杂网络元处不在,与人们的生产生活息息相关,例如社交网络、互联网、交通网等.因 此,研究复杂网络上的动力学过程和其整体动力学行为有着重要的理论和实际价值,并且已经受到了各 领域研究人员的广泛关注【 .研究复杂网络的最终目标是控制复杂网络的动力学行为,我们需要结合复 杂网络和传统控制论中的理论和方法实现这一目标.由于复杂网络一般节点数目众多,复杂度高,于是就 不能像低维小系统一样通过遍历的方法来寻找控制输入位置,那样需要耗费巨大的计算量.因此,如何有 效的确定所需要独立控制的节点数目和控制输人的位置以满足复杂网络可控性的要求就成了网络控制 需要解决的首要问题. 1复杂网络控制问题 对于一般的连续线性时不变受控复杂网络系统 =Ax+Bu 其中向量 =( 1, 2,…, |Iv) 表示系统的状态,A∈R 代表系统的耦合矩阵,其中 表示状态 对状态 的影响力度(aij=0表示没有影响), 代表系统的m维(个)控制输入信号,而B∈R 则表 示系统的控制输入矩阵.系统的可控性定义为对于如上线性系统,如果初始状态 (t0)在控制输入 的 作用下,系统状态可以在时间t1到达任意的状态.为达到系统的可控性,可以通过计算可控性矩阵C= [B,AB,A ,…,AⅣ_ B]满秩与否(Kalman)或矩阵[ 厶广A,B]是否对任意 满秩(PBH)来进行判定, 收稿日期:2014—10—10 基金项目:福建省自然科学基金项目(2013J01260) 作者简介:袁正中(1980一),男,四川省乐山市人,讲师 ・31・ 闽南师范大学学报(自然科学版) 其中,Ⅳ为Ⅳ阶单位矩阵. 对于复杂网络的控制问题,就是要去寻找m个控制输入信号和具体的控制输入位置来达到对整个 网络的控制.所以如何确定网络最少需要多少个控制输入,是解决复杂网络控制问题的第一步;进而确定 这些控制输入需要直接作用的节点,即驱动节点为第二步;第三步则是考虑控制输入如何通过间接作用 完成对网络的完全控制. 2复杂网络的结构控制 复杂网络控制问题的研究始于2011年Liu等[61发表在Nature上的论文,该文首次从线性控制论思想 和方法上研究复杂网络动力系统 =Ax+Bu的结构控制问题,其中A为网络的结构矩阵(邻接矩阵的转 置).文献中作者引人图的匹配理论和方法,从理论上证明了为达到复杂网络的结构控制,网络需要独立 控制的节点(驱动节点,总数为%)为网络的最大匹配中的非匹配节点,于是根据匹配的定义,可以说明 驱动节点的选择要避开度大的节点;进一步,作者还利用计算图最大匹配的cavity方法给出了网络结构可 控能力( D=%/Ⅳ,Ⅳ为网络节点总数)与网络度分布之间的关系.这种关系充分说明网络的结构可控能 力完全由网络的度分布确定. 在这一研究的带动下.复杂网络的结构控制成为了网络科学的一个热点课题,大量关于复杂网络结 构控制的研究工作相继而出.特别是,Nepusz和VicsekIn通过点边互换的方式利用Liu的方法研究边的结 构可控性问题;Wang等圈通过对网络一组最大匹配边集进行相互连接的方式,给出了达到仅需一个驱动 节点的网络所需要添加的最少边数,提升和扩展了复杂网络结构控制的研究内容.之后,.关于复杂网络结 构可控性以及驱动节点与网络结构和功能的关系成了研究的热点课题 垌.同时,Liu等 还研究了与可控 性对偶的网络观测性问题.而科研工作者们还进一步指出,在实际的控制中,网络的自身动力学【1 8j、控制路 径㈣、控制能量 是网络控制中非常重要的研究内容. 2012年Uu等[2】】三位作者在PLos One发表文献研究了复杂网络结构控制中节点的控制范围问题.节 点的控制范围定义为只控制该节点后满足可控性的节点组(包含该节点),表征该节点的最大受控影响力. 对于结构可控而言,节点控制范围就是可控性矩阵的最大线性元关向量组所对应的节点组.对于特殊的 有向无圈网络(directed acyclic graph,DAG),文献[21]中利用简单的方法得到了每个节点的控制范围.而 Wang等在另一篇文献【221中同样研究了节点的控制范围问题,他们定义节点的控制范围是在所有最大匹 配构成的控制子图中以该节点为起点的最大可到达节点(包含该节点),发现网络节点的控制范围不与节 点度呈正相关关系.即度大的节点控制范围不都大于度小的节点. 之后.Jia等 】研究了复杂网络结构控制中驱动节点分类问题.基于节点在最小驱动节点集(minimum driver node set,MDS)中的出现情况分为:关键节点,间歇节点和冗余节点.通过对冗余节点的分析,发现 其在整个网络中的分布呈现双模状态,从而在网络的结构控制中存在两种控制方式:集中控制和分散控 制.在此工作的基础上,Jia等[241进一步研究了节点在MDS中出现的概率分布问题,即节点控制容度问题, 并提出一个有效的计算机随机采样的方法得到每个节点的控制容度. 3复杂网络的严格控制 虽然Liu等人提出的结构可控性理论首次给出了研究复杂网络可控性的一般理论方法,但是复杂网 络控制问题仍然处于起步阶段,已经解决的问题依然只是冰山一角,例如无法应用结构可控性理论研究 无向、权重和带自环网络的可控性.因此,研究人员迫切需要一种适用范围更广泛的可控性理论框架来研 究复杂网络控制领域的大量有价值的科学问题.基于这个认识,Yuan等人于2013年在著名的综合类期 刊Nature Communications上发表了文献[251,解决了复杂网络的严格可控性和控制输入等问题. 在文献[251中。作者首次从线性系统的另一个可控性判定定理一PBH秩定理人手,证明了一般复杂网 络严格可控需要的最少独立控制输入个数(驱动节点数ⅣD)由网络动力学耦合矩阵特征值的最大几何重 数决定.文献『251的方法对任意线性耦合情况下的复杂网络都有效,比如结构矩阵耦合的网络、拉普拉斯 ・32・ 袁正中:复杂网络控制研究综述 第4期 矩阵耦合的网络、转移概率矩阵耦合的网络等.进一步的研究还发现,对于以结构矩阵耦合的稀疏(无权 或有权)网络,只需要计算结构矩阵零特征值的几何重数(或代数重数)即可确定控制网络需要的最少控 制输入个数;而对于同权的同样以结构矩阵耦合的致密网络(权重为 ),则只需要计算结构矩阵特征值一 W的几何重数(或代数重数)即可.这样就解决了一般复杂网络的严格控制中最少控制输入的个数问题. 进一步。文献中还通过对系统带入最大几何重数对应特征值的一个矩阵进行列初等变换来确定网络需要 独立控制的节点(驱动节点),并且所有可能驱动节点组都可由变换后的矩阵求出.在后续研究中,作者还 分析和计算了理论模型网络和现实网络的严格可控能力,系统满足严格控制的一类控制输入矩阵设置以 及复杂网络的严格控制能量等问题. 在此基础上,文献f261研究了三类规则分形复杂网络的可控能力与网络部分结构的关系,给出了每一 类网络严格可控能力的理论表达式和极限表达式,进一步说明了网络结构对网络严格可控能力的影响. 并且从中还可以看出,网络平均度不是确定网络严格可控能力的唯一因素.而文献[271 ̄m]将文献[251的方 法推广应用到多重网络上。分别研究了多关系网和多层网的可控性问题.文献【271中不仅给出了多重网可 控需求控制输入数ⅣD的上下界,对多种特殊情形下的网络还给出了J7\7D_的近似简单计算公式.同时,由 于多关系网相当于高阶线性系统对应的复杂网络,所以严格控制已经突破了结构控制只能研究一阶系统 的限制.说明严格控制的理论和方法具有更加广阔的应用空间. 4复杂网络的严格控制研究展望 目前,复杂网络可控性方面的大部分研究工作仍然基于Liu等人提出的结构可控性理论,而结构可控 性理论的应用范围有限,使得相关研究工作受到了一定的制约.严格可控理论不仅弥补了结构可控理论 的不足,而且完善了复杂网络可控性方面的基础理论框架,有广阔的理论和实际应用前景。特别是在输入 矩阵设置。优化控制能量和可控性受节点自身动力学的影响等方面有不可替代的作用.严格可控性理论 一方面可以用来重新检验应用结构可控性理论的研究结果的准确性。另一方面也可以研究结构可控性无 法涉及的很多重要问题.复杂网络严格可控性方面的研究工作还处于起步阶段。有很多重要问题有待研 究,可以归纳为以下几个方向: (1)严格可控性受网络结构特征的影响.与结构可控性理论不同,严格可控性由网络矩阵的特征值和 几何重数决定,无法直观对应到网络结构特征.因此,目前仍然欠缺各种结构特征与严格可控性之间的整 体认识和定量刻画.关键点在于给出结构特征量与特征值、几何重数和矩阵的秩之间的理论表达式.我们 可以借助已有的复杂网络特征值谱方面的研究结论深入探讨这一问题.回答这一问题对于理解复杂网络 的可控性有着至关重要的作用. (2)节点动力学与网络结构的耦合.几乎所有研究复杂网络可控性的工作都在讨论网络结构对于结 构可控性的影响.但是,复杂系统由复杂个体之间的相互作用和个体自身动力学共同构成.因此,个体自 身动力学对系统可控性的影响不可或缺.结构可控性显然无法处理节点自身动力学,因此.严格可控性是 目前唯一的选择.考虑节点自身动力学的影响必然会得到与纯粹基于网络结构的可控性不同的结果.能 够使人们对于复杂网络系统的可控性有更加全面和真实的认识. (3)节点的控制范围.虽然Liu等人提出了基于结构可控性理论的有向无圈网络DAG中单一节点控 制范围的理论,但是对于任意网络中节点的控制范围,特别是节点的严格控制范围仍然缺少有效的研究 方法和工具.而且,多节点的组合控制范围问题还没有任何明确的结论.节点的控制范围一方面表征节点 对于实现控制的重要性,另一方面对于驱动节点的选择,优化控制能量和研究动态网络的控制问题有重 要价值. (4)复杂动力系统的控制.现有的方法和结论,无论是结构控制还是严格控制,都仅针对线性耦合的 复杂网络动力系统.然而,现实中存在各种各样的网络动力系统,比如切换网络动力系统、双线性网络动 力系统、非线性网络动力系统和布尔网络动力系统等.这些网络动力系统所具有的更加丰富和复杂的动 ・33・ 2014卑 闽南师范大学学报(自然科学版) 力学行为,造就控制这些复杂系统更加困难,给复杂网络可控性领域的研究人员提出了更加艰巨的挑战, 需要发展和进一步完善已有的复杂网络系统的控制理论和方法. 参考文献: 【1]汪小帆,李翔,陈关荣.复杂网络理论及其应用【M】.北京:清华大学出版社,2006. [2]何大韧,刘宗华,汪秉宏.复杂系统与复杂网络[M].北京:高等教育出版社,2009. 【3]郭 雷,许晓鸣.复杂网络[M】.上海:上海科技教育出版社,2006. [4]汪小帆,李 翔,陈关荣.网络科学导论[M].北京:高等教育出版社,2012. 【5]郭世泽,陆哲明.复杂网络基础理论【M].北京:科学出版社,2012. 【6】“u Y Y,Slotine J J,Barabdsi A L.Controllability of complex networks[J].Nature,201 l,473:167—173. [7】Nepusz T,Vicsek T.Controlling edge dynamics in complex networks【J】.Nature Physics,2012,8:568—573. [8】Wang W X,Ni X,Lai Y C,et a1.Optimizing controllability of complex networks by minimum structural perturbations[J/OL]. Physical Review E,2012,85:0261 15【2014—10—10].http:#dx.doi.org10.1 103/PhysRevE.85.0261 15. [99] P6sfM M,“u Y Y,Slotine J J,et a1.Effect of correlations on network controllability[J/OLJ.Scientiifc Reports,2013,3:1067 【2014—10—10].http://dx.doi.or/10.s1038/srep01067. [10]“u Y Y,Cs6ka E,Zhou H,et a1.Core percolation on complex networks[J/OL].Physical Review Letters,2012,109:205703 [2014—10—10].http://dx.doi.or/1s0.1 103/PhysRevLett.109.205703. 【1 1]Pu C L,Pei W J,Michaelson A.Robustness analysis of network contorlability[J].Physica A,2012,391(24):4420—4425. [12]Ding J,Lu Y Z,Chu J.Studies on controllbiality of directed networks with extremal optimization【J].Physica A,2013,392(24): 6603—6615. 【13]Wang B,Gao L,Gao Y,et a1.Maintain the structurla controllability under malicious attacks on directed networks[J/OL]. Eumphysics Letters,2013,101(5):58003【2014-10—10].http:,/dx.doi.org/10.1209/0295—5075,1O1,58003. [14】Hou Lj Lao S,Liu G,et 1a.Controllability and Directionality in Complex Networks[J/OL].Chinese Physics Letters,2012,29 f1 o1:108901 f2014—10—1 o].http://dx.doi.org/10.1088,0256—307X/29/1O/108901. [15】Tang Y,Gao H,Zou W,et a1.Identifying controlling nodes in neuronal networks in diferent scales[J/OL].PloS one,2012,7: e41375[2014—10-101.http://dx.doi.org/10.1371 ̄ourna1.pone.0041375. 【16】Guti6rrez R,Sendi?a-Nadal I,Zanin M,et a1.Targeting het dynamics of complex networks[J/OL].Scientiifc Repots,2012,2: 396[2014—10一lO].http://dx.doi.ors/10.1038/srep00396. [17】“u Y Y,Slotine J J,Barab6si A L.Observability of complex systems[J].Proc Nat/Acad Sci USA,2013,1 10:2460-2465. [1 8】Cowan N J,Chastain E J,Vilhena D A,et a1.Nodal dynamics,not degree distributions,determine the structural contolrlability of complex networks[J/OLI.PloS one,2012,7:e38398[2014-10-1 o].http://dx.doi.org/lO.1371/journa1.pone.0038398. 【19]Sun J,Motter A E.Controllbiality transiiton and nonlocality in network control[J/oLI.Physical Review Letters,2013,1 10: 208701[2014-10-10].http://dx.doi.or/lsO.1 103/PhysRevLett.1 10.208701. 【20】Yan G,Ren J,Lai Y C,et a1.Controlling complex networks:How much energy is needed?Physical Review Letters[J/OL]. 2012,108:218703 f2014—10一l .http://dx.doi.org/10.1】03/P=IlysRevLett.108.218703. [21]uu Y Y,Slotine J J,Barabrsi A L.Contolr centrality and hierarchical structure in complex networks[J/OL].Plos one,2012,7: e44459[2014—10-10].http://dx.doi.ors/10.1371 ̄ourna1.pone.0044459. [22】Wang B,Gao L,Gao Y.Control range:a controllability—based index for node signiifcance in directed networks[J/OL].Journal of Statisitcal Mechanics,2012,4:PO4011『2014—10—1 o].http:#dx.doi.or/1s0.1088/1742—5468/2012/04,PO4011. [23]Jia T,Liu Y Y,Cs6ka E,et a1.Emergence of bimodality in controlling complex networks[J/OL].Nature Communicaitons,2013, 4:2002[2014—10-10].http://dx.doi.or/10.s1038/ncomms3002. [24]Jia T,BarabOsi A L.Control Capacity and A Random Sampling Method in Exploring Controllability of Complex Networks [J/0L].Scientiifc Reports,2013,3:2354【2014-10—10].http://dx.doi.or/10.s1038/srep02354. [25]Yuan Z Z,Zhao C,Di Z R,et a1.Exact controllability of complex networks[J/OL].Nature Communications,2013,4:2447 【2014-10-1 o].http://dx.doi.or/10.s1038/ncomms3447. 【26】“J W,Yuan Z Z,Fan Y,et 1.Contaorllability of Fractla Networks:An analytical Approach[J/0L].Europhysics etLters, 20141,05:5800l『2014—10—101.http://dx.doi.or/lsO.1209/0295—5075/105/58001. 【27】Yuan Z Z,Zhao C,Wang W X,et a1.Exact contolrability of mulitplex networks[J/OL].New Journal of Physics,2014,1 6: 1010362014.【2014—10—10].http://dx.doi.ors/10.1088/1367—2630,16,10/103O36. [责任编辑:钟国翔] 34・ ・