复杂网络控制核心的进一步分析.pdf
《复杂网络控制核心的进一步分析.pdf》由会员分享,可在线阅读,更多相关《复杂网络控制核心的进一步分析.pdf(8页珍藏版)》请在咨信网上搜索。
1、第36卷第2期2023年6月Vol.36 No.2Jun.2023闽南师范大学学报(自然科学版)Journal of Minnan Normal University(Natural Science)复杂网络控制核心的进一步分析袁正中,李灿东(闽南师范大学数学与统计学院,福建 漳州 363000)摘要:对复杂网络进行控制的首要任务是找到驱动节点.通过叶子节点删除法能删除网络部分节点,可以形成一个至少包含一组驱动节点的控制核心.进一步对控制核心进行约简,利用矩阵的初等变换和边融合方法,实现对核心中度为2和3的节点的约简,可以进一步压缩网络控制核心规模,方便寻找网络的一组驱动节点.关键词:复杂网络
2、;控制核心;叶子节点删除法;网络可控性中图分类号:O231 文献标志码:A 文章编号:2095-7122(2023)02-0027-08Further analysis on control core of complex networkYUAN Zhengzhong,LI Candong(School of Mathematics and Statistics,Minnan Normal University,Zhangzhou,Fujian 363000,China)Abstract:The primary task of controlling complex networks is t
3、o find the driver nodes.The leaf removal process can delete many nodes.The rest of nodes and edges form a control core of the original network,which contains at least one group of driver nodes.In this paper,the control core is further reduced.Through the matrix elementary transformation and edge fus
4、ion,the nodes with degree 2 and 3 are reduced,which lead to the little scale of control core.This technique facilitates the search for a set of driver nodes of the original network.Key words:complex network;control core;the leaf removal process;network controllability复杂网络化动力系统的控制研究是当前复杂性科学的一个重要研究课题.
5、复杂网络有着非常丰富的动力学特性1,目前研究人员对这方面的研究已有一定的基础,自无标度网络2被发现以来,研究人员对复杂网络的结构进行了大量的理论和实证研究3-4.随着对复杂网络结构机制和动力学机制研究的不断深入5-6,人们更加关注复杂网络化动力系统的控制研究.2011年,Liu等7构建了结构可控性理论(SCT)对网络可控性问题展开研究.然而,SCT对于无向复杂网络或给定权重的复杂网络动力系统的分析存在一定限制.在SCT的基础上,Yuan等8提出了严格可控性理论(ECT),通过计算耦合矩阵的最大几何重数获得使网络可控的驱动节点数,特别地,对于稀疏网络,网络的驱动节点数由邻接矩阵的秩决定.基于Po
6、pov-Belevitch-Hautus(PBH)可控条件的严格数学证明,ECT 对有向或无向,加权或未加权的网络都是适用的,因此ECT对解决更一般情况下的控制问题提供了新的思路和方法.受这两项研究启发,许多研究人员将注意力转移到控制复杂网络的问题上9,包括可控性理论的改进10-12、可控性的优化13-14、动力系统的可控性15-16、目标控制17、控制节点分析18-19、利用可控性计算大型矩阵的秩20等.尽管 SCT 和 ECT 允许研究人员识别所有驱动节点,但由于复杂网络节点众多,对于其可控性分析在计算上仍然非常困难.控制复杂网络的首要问题是识别驱动节点,2021年,Yuan等21基于EC
7、T理论利用叶子删除法(LRP)剔除网络的明显非驱动节点,构建了至少包含网络一组驱动节点的控制核心.叶子删除法通过移除叶子获收稿日期:2022-10-20基金项目:福建省自然科学基金(2022J01893)作者简介:袁正中(1980),男,四川乐山人,博士,副教授.2023年闽南师范大学学报(自然科学版)得网络核心,有效降低了网络规模并保持一组驱动节点在网络核心中,因此仅基于网络局部节点的结构信息即可判断控制核心.通过控制核心至少可以找到原始网络的一组驱动节点,且在控制核心中分析原始网络的可控性相对更高效.基于PBH可控条件,研究人员进一步证明了对于大部分网络,控制网络核心可以完成对整个网络的控
8、制,并在此基础上研究了一些核心可控,但原始网络不可控的网络控制问题22-23.尽管叶子删除法可以有效降低网络规模,但通过叶子删除后,网络依然存在度大于1的节点连通集团.对于大型复杂网络,这部分节点连通集团的计算依然复杂,因此节点连通集团还有进一步约简的空间.针对Yuan等21获得的网络核心继续展开分析,利用代数理论和方法完成对控制核心的进一步约简.通过采取初等变换和连边融合的方法,针对不同度的节点连接情形进行分类讨论,提出对应的约简策略,并给出处理度为2和度为3的节点连接情形的实例.推广到一般情形,证明了在稀疏网络中删除任意一个全联通子图并不会影响驱动节点的寻找.1 基础知识含有N个节点的网络
9、化受控动力系统为x=Ax+Bu,(1)其中:x=(x1x2xN)T为N个节点的状态.N阶方阵A=(aij)表示网络节点的邻接矩阵,如果节点j对节点i有直接影响,则aij=1,否则aij=0.为方便起见,本文仅对无向网络进行处理,即A为对称矩阵.u=(u1u2um)T为外界的控制输入;B=(bij)Nm为控制输入矩阵,表明外界的控制输入分别作用于哪个节点.复杂网络控制的首要研究目标为寻找需要独立控制输入作用的节点,即驱动节点,以满足系统(1)的可控性.Liu等7引入图的匹配理论,说明系统(1)的驱动节点为网络最大匹配中的未匹配节点.然而该结论仅对结构矩阵A成立,其中A中的非零元素必须是完全独立的
10、可任意取值的数.对于有网络权重信息的情形,Yuan等8利用矩阵A特征值的几何重数和代数重数给出驱动节点的数量结论,并通过对相应矩阵进行初等变换的方法找到驱动节点.特别地,对于现实中大量的结构稀疏的网络,驱动节点数满足ND=N-rank(A).(2)通过对矩阵A进行初等变换可以找到其线性相关行,对应的节点即为驱动节点.然而,对于存在成千上万的节点和连边的复杂网络,对矩阵A进行初等变换是困难重重的.大量的数值计算表明,一个网络的驱动节点往往是比较少的,说明矩阵A中存在大量的线性无关的行,如果能直接删除线性无关行所对应的节点及其连边,那么将大大减少寻找驱动节点的困难.基于此,Yuan等21利用叶子删
11、除法,删除网络中度为1的节点及其邻居和相应的连边并保留孤立节点形成网络的控制核心,从控制核心中寻找到的驱动节点就是原始网络的一组驱动节点.该方法操作简单,能有效的降低寻找复杂网络驱动节点的计算复杂度.通过叶子删除法,最后的控制核心只包含孤立节点(度为0)及度大于1的节点.孤立节点必定是驱动节点,网络的其它驱动节点则需要对剩余的度大于1的节点组成的连通集团进行初等变换获得.2 度为2的节点的处理控制核心中度为2的节点连接方式存在两种情形,如图1所示,其中标号为1的节点度为2,图1(a)中1号节点的邻居彼此不相连,图1(b)中1号节点的邻居彼此相连.28袁正中,等:复杂网络控制核心的进一步分析第2
12、期2.1 连接情形1的处理此时1号节点的邻居彼此不相连(图1(a),对应的邻接矩阵可表达为A=0110100T1100T2012A0,其中:12分别为2号和3号节点与其余的N-3个节点的连接情况;A0为除了1,2,3号节点外的N-3个节点自身连接情况.上面的矩阵A经过初等变换为 01001000000T2-T1002-1A0.显然节点1,2线性无关,说明对此种情形的处理为:1)删除度为2的节点以及其一个邻居与相应的连边;2)将删除的邻居中与其余节点的连边融合给另一个邻居.融合规则为相同邻居的边抵消,不同邻居的边保留.注注1 融合过程中,将数值为-1的也改为1,可能将不相关的点变为相关,将相关的
13、点变为不相关,但是这种几率比较小.在对大型网络进行处理时,仍然是可行的.注注2 以上处理方法并没有改变节点的序号,即融合处理后寻找到的驱动节点与原网络的驱动节点是一致对应的.2.2 连接情形2的处理此时1号节点的邻居彼此相连(图1(b),对应的邻接矩阵可表达为A=0110101T1110T2012A0.相关数学符号意义同2.1节一致.经过初等变换,此种情形的矩阵化为 0100100000-2T2-T1002-1A0.图1 度为2的节点连接情形图Fig.1 Connection cases of the nodes with degree 2(a)(b)292023年闽南师范大学学报(自然科学版
14、)因为子块A1=()01010000-2为可逆矩阵,所以A的前三行(列)一定线性无关,线性相关行只能出现在后面N-3行.利用A0找到的线性相关行必然包含(002-1A0)对应的线性相关行.于是,对此种情形的处理为:直接删除节点1,2,3,以及对应连边.2.3 例子下面以两个已完成叶子节点删除的实际网络例子对度为2的节点进行处理说明.图2(a)为一个具有稀疏结构的6节点网络,1号节点度为2,它的邻居彼此不相连.按照处理方法,删除1号和2号节点及其连边,将2号节点剩余的一条边与3号节点融合,如图2(b)所示.由于2号和3号有相同的邻居,所以边就被抵消,变成两个孤立的节点,结果如图2(c)所示.经过
15、验证,对于图2(a)所示网络,ND=4,融合处理后得到4个孤立节点,它们就是原始网络的驱动节点.对于图3(a)所示的由7个节点构成的稀疏网络,与上一例类似,先删除1号和2号节点,并将2号节点连边与3号节点融合,如图3(b)所示.由于2号和3号节点的邻居不同,所以融合后产生一条新的边,如图3(c)所示.此时网络包含3个节点彼此相连的结构,按融合规则,直接删除这3个节点和相应连边,最后网络只剩2个孤立节点,如图3(d)所示.经过验证,对于图3(a)所示网络,ND=2,融合处理后得到2个孤立节点,它们就是原始网络的驱动节点.图2 度为2情形1删除示例图Fig.2 Removal example of
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 复杂 网络 控制 核心 进一步 分析
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。