博文
节点分类及失效对网络能控性的影响
|
引用本文
孔芝, 袁航, 王立夫, 郭戈. 节点分类及失效对网络能控性的影响. 自动化学报, 2022, 48(4): 1048−1059 doi: 10.16383/j.aas.c200900 Kong Zhi, Yuan Hang, Wang Li-Fu, Guo Ge. Node classification and the influence of node failure on network controllability. Acta Automatica Sinica, 2022, 48(4): 1048−1059 doi: 10.16383/j.aas.c200900 http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c200900?viewType=HTML 文章简介 关键词 复杂网络, 网络能控性, 节点失效, 驱动节点 摘 要 复杂系统间的相互作用能够用复杂网络描述. 复杂网络中某些节点遭受攻击或破坏会造成网络故障, 导致整个网络能控性变化. 不同节点失效会对网络能控性有不同的影响. 本文提出一种网络节点的分类方式, 将网络中的节点根据边的方向和匹配关系分成九种类型, 并给出了辨识节点类型的算法. 另外, 本文给出了基于此分类方式下复杂网络中某类节点失效时, 网络中驱动节点数量(用来衡量网络能控性大小的指标)的变化规律. 并通过模型网络进行仿真实验, 验证了当节点失效时本文给出的驱动节点数量变化情况, 同时还分析社交网络中不同类型节点的占比与实际中人际交往的对应关系. 引 言 近年来, 随着科学技术的发展, 人们已经认识到各种复杂系统是由相互作用和相互依赖的若干部分组成的具有特定功能的有机整体. 而网络是由节点和连接节点的边所组成的. 如果用节点表示系统的各个组成部分, 两节点之间的边表示各个组成部分之间的相互作用, 那么网络就为研究复杂系统提供了一种新的描述方式. 例如神经系统可以看作是由神经细胞通过神经纤维相互连接形成的网络; 计算机网络可以看作是自主工作的计算机通过通信介质(如光缆、同轴电缆等)相互连接形成的网络; 人际关系网是将每一个人作为一个节点, 如果两个人之间存在某种关系(比如相识)就连一条边; 类似的还有电力网络和交通网络等. 复杂网络研究的近年来受到了许多关注, 其最终目标是寻找有效的策略来控制网络的行为使其为人类服务. 许多学者对复杂网络的控制算法进行了研究, 并取得了丰硕的成果, 如牵制控制, 自适应控制, 同步控制及存在延时的网络系统同步, 最优滤波等方法都已应用于网络中. 然而对网络进行控制算法应用的前提条件是此网络系统必须是能控的. 另外, 现实世界中很多复杂的系统问题也可以抽象为网络能控性问题. 例如, 在错综复杂的基因调控网络中, 如何选择最有效的基因节点作为药物的靶标, 使得整个生物体网络系统朝着预期的良好状态发展; 在电力网络中, 如何优化网络的拓扑结构使得可以用最少的变电站就能够控制整个地区的电力供应; 在计算机网络中, 当部分计算机遭遇黑客袭击后, 如何重新选择控制节点保证整个计算机系统的正常运转. 对于线性系统能控性的基础理论已较为成熟, 并广泛应用于工程中. 然而, 要把传统的线性系统结构能控性理论直接应用到复杂系统或者复杂网络中却存在诸多困难. 如何选择一部分节点控制整个复杂网络, 首要问题是需要多少外界输入信号才能使网络达到期望状态, 也就是满足能控性条件的控制器的最少个数是多少. 2011年, Liu等在Nature上发表了关于复杂网络结构能控性的论文通过引入图论中的匹配理论得到了求解最少输入信号和驱动节点的最少(最小)输入定理, 建立复杂网络能控性研究框架. Yuan 等从PBH能控性判据出发提出了求解网络严格能控性的理论框架, 可用于求解具有确定性边权和任意结构的网络的能控性. 许多学者在这两个框架下研究了时变网络的能控性、深度耦合动态网络的能控性、对称网络结构能控性、具有对抗相互作用的多智能体网络的能控性和多层网络的能控性等问题, 这些研究大大提高了人们对网络能控性问题的认识. 现实生活中, 网络某些节点遭到攻击或发生故障失效, 可能会导致整个网络失控, 例如互联网络中某个计算机或服务器发生故障可能导致互联网络瘫痪; 电力网络中某个电站或变压器发生故障可能会导致电力系统瘫痪等. 网络中不同节点失效时, 对整个网络功能的影响是不同的. Pu等研究了单一节点攻击和级联失效两种攻击模式下网络可控性的影响, 结果表明基于度的攻击方式都比随机攻击对网络能控性的影响更大. Liu等提出了一种随机上游攻击策略来破坏有向网络的结构能控性, 该策略移除随机选择的点的上游节点, 相较于依据节点度的攻击策略, 该策略不需要知道网络全局的拓扑结构信息. Lu等研究了边失效对网络能控性的影响, Pu等研究了最长简单路径失效时网络能控性的影响, 以上研究说明当失效边介数越大或失效时简单路径越长, 对网络能控性的影响更大. 综上所述, 可以发现当前节点失效对网络能控性的影响的研究主要集中在部分节点或者边失效对网络能控性的影响上, 主要针对具有某种结构特征的节点或边通过实验和仿真等手段给出结论, 并未从理论层面给出节点失效对网络能控性的影响. 对于整个网络而言, 不同类型的节点对网络能控性的影响也不相同: 有些节点失效网络能控性会增加, 有些节点失效网络的能控性保持不变, 有些节点失效网络能控性会降低. 哪些节点失效对网络能控性有何影响, 至今未有明确结论. 因此, 本文为了研究此问题将网络节点进行分类, 并从理论层面给出不同类型的节点对网络能控性影响的确切结论. 首先根据边的方向和匹配关系提出一种网络节点的分类方式, 将网络中的节点分成九种类型, 并给出了辨识节点类型的算法, 然后研究了复杂网络中某类节点失效对网络能控性有何影响, 给出了节点失效后网络能控性的变化规律, 最后通过仿真实验验证上述规律的有效性. 图 3 节点分类 图 11 社交网络节点失效能控性变化 作者简介 孔 芝 东北大学秦皇岛分校副教授. 研究方向为知识发现, 决策分析, 智能优化算法和复杂网络. E-mail: kongz@neuq.edu.cn 袁 航 东北大学秦皇岛分校硕士研究生. 研究方向为复杂网络能控性. E-mail: yuanhang951115@163.com 王立夫 东北大学秦皇岛分校副教授. 研究方向为复杂网络, 同步控制, 能控性和交通网络. 本文通信作者. E-mail: wlfkz@qq.com 郭 戈 东北大学秦皇岛分校教授. 研究方向为智能交通系统, 交通大数据分析, 人工智能应用和信息物理系统. E-mail: geguo@yeah.net 相关文章 [1] 郭天姣, 涂俐兰. 噪声下相互依存网络的自适应H∞异质同步. 自动化学报, 2020, 46(6): 1229-1239. doi: 10.16383/j.aas.c180075 http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c180075?viewType=HTML [2] 张檬, 韩敏. 基于单向耦合法的不确定复杂网络间有限时间同步. 自动化学报, 2021, 47(7): 1624-1632. doi: 10.16383/j.aas.c180102 http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c180102?viewType=HTML [3] 楼洋, 李均利, 李升, 邓浩. 复杂网络能控性鲁棒性研究进展. 自动化学报. doi: 10.16383/j.aas.c200916 http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c200916?viewType=HTML [4] 曹连谦, 王立夫, 孔芝, 郭戈. 多层异质复杂网络系统的能控性. 自动化学报. doi: 10.16383/j.aas.c210654 http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c210654?viewType=HTML [5] 潘永昊, 于洪涛. 基于网络同步的链路预测连边机理分析研究. 自动化学报, 2020, 46(12): 2607-2616. doi: 10.16383/j.aas.c180469 http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c180469?viewType=HTML [6] 陈伟哲, 李乡儒. 基于复杂网络的封闭小区交通开放策略探究. 自动化学报, 2018, 44(11): 2068-2082. doi: 10.16383/j.aas.2017.c160819 http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2017.c160819?viewType=HTML [7] 陈玲玲, 李珊珊, 刘作军, 张燕. 基于表面肌电的下肢肌肉功能网络构建及其应用研究. 自动化学报, 2017, 43(3): 407-417. doi: 10.16383/j.aas.2017.c160230 http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2017.c160230?viewType=HTML [8] 韦相, 赵军产, 胡春华. 两个异构复杂网络的广义同步与参数识别. 自动化学报, 2017, 43(4): 595-603. doi: 10.16383/j.aas.2017.c160449 http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2017.c160449?viewType=HTML [9] 王守辉, 于洪涛, 黄瑞阳, 马青青. 基于模体演化的时序链路预测方法. 自动化学报, 2016, 42(5): 735-745. doi: 10.16383/j.aas.2016.c150526 http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2016.c150526?viewType=HTML [10] 袁超, 柴毅. 复杂网络的局部社团结构挖掘算法. 自动化学报, 2014, 40(5): 921-934. doi: 10.3724/SP.J.1004.2014.00921 http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2014.00921?viewType=HTML [11] 席裕庚. 大系统控制论与复杂网络——探索与思考. 自动化学报, 2013, 39(11): 1758-1768. doi: 10.3724/SP.J.1004.2013.01758 http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2013.01758?viewType=HTML [12] 张新猛, 蒋盛益. 基于核心图增量聚类的复杂网络划分算法. 自动化学报, 2013, 39(7): 1117-1125. doi: 10.3724/SP.J.1004.2013.01117 http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2013.01117?viewType=HTML [13] 陈娟, 陆君安, 周进. 复杂网络同步态与孤立节点解的关系. 自动化学报, 2013, 39(12): 2111-2120. doi: 10.3724/SP.J.1004.2013.02111 http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2013.02111?viewType=HTML [14] 杨博, 刘杰, 刘大有. 基于随机网络集成模型的广义网络社区挖掘算法. 自动化学报, 2012, 38(5): 812-822. doi: 10.3724/SP.J.1004.2012.00812 http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2012.00812?viewType=HTML [15] 殷春霞, 彭勤科. 利用复杂网络为自由评论鉴定词汇情感倾向性. 自动化学报, 2012, 38(3): 389-398. doi: 10.3724/SP.J.1004.2012.00389 http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2012.00389?viewType=HTML [16] 黄发良, 肖南峰. 基于线图与PSO的网络重叠社区发现. 自动化学报, 2011, 37(9): 1140-1144. doi: 10.3724/SP.J.1004.2011.01140 http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2011.01140?viewType=HTML [17] 金弟, 刘杰, 杨博, 何东晓, 刘大有. 局部搜索与遗传算法结合的大规模复杂网络社区探测. 自动化学报, 2011, 37(7): 873-882. doi: 10.3724/SP.J.1004.2011.00873 http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2011.00873?viewType=HTML [18] 刘旭, 易东云. 基于局部相似性的复杂网络社区发现方法. 自动化学报, 2011, 37(12): 1520-1529. doi: 10.3724/SP.J.1004.2011.01520 http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2011.01520?viewType=HTML [19] 潘欢, 年晓红, 桂卫华. 基于线性反馈控制器的时变时滞动态网络中的同步. 自动化学报, 2010, 36(12): 1766-1772. doi: 10.3724/SP.J.1004.2010.01766 http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2010.01766?viewType=HTML [20] 何东晓, 周栩, 王佐, 周春光, 王喆, 金弟. 复杂网络社区挖掘---基于聚类融合的遗传算法. 自动化学报, 2010, 36(8): 1160-1170. doi: 10.3724/SP.J.1004.2010.01160 http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2010.01160?viewType=HTML [21] 黄文良, 刘勇, 钟志强, 沈仲明. 基于复杂网络的垃圾短信过滤算法. 自动化学报, 2009, 35(7): 990-996. doi: 10.3724/SP.J.1004.2009.00990 http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2009.00990?viewType=HTML 
https://blog.sciencenet.cn/blog-3291369-1333566.html
上一篇： 基于多对多生成对抗网络的非对称跨域迁移行人再识别
下一篇： 结合领域知识的因子分析: 在金融风险模型上的应用
0
该博文允许注册用户评论 请点击登录 评论 (0 个评论)
欧彦
- 加为好友
- 给我留言
- 打个招呼
- 发送消息
全部作者的精选博文
- • 2023年度自动化领域国家自然科学基金申请与资助情况
全部作者的其他最新博文
- • Bagging RCSP脑电特征提取算法
- • 基于混合模糊多人多目标非合作博弈的车道选择模型
- • 基于代价参考粒子滤波器组的多目标检测前跟踪算法
- • 基于时滞测量的复杂网络分布式状态估计研究
- • 北京化工大学王友清教授等：基于内模原理和ADP的自适应最优离散时间输出反馈
- • 基于距离信息的追逃策略: 信念状态连续随机博弈
全部精选博文导读
- • 即时开通权限！科学网APP推出论文&基金全新活动
- • 科学网编辑部：我们悄悄准备了一份惊喜……
- • 今年参加和旁听研究生学位论文答辩会的体会
- • 生命科学的十个基本问题-兼答“颜宁之问”
- • 人工智能有没有创造力？
- • NML文章集锦| 锂离子电池文章（三）