引用本文

楼洋, 李均利, 李升, 邓浩. 复杂网络能控性鲁棒性研究进展. 自动化学报,  2022, 48(10): 2374−2391 doi: 10.16383/j.aas.c200916

Lou Yang, Li Jun-Li, Li Sheng, Deng Hao. Recent progress in controllability robustness of complex networks. Acta Automatica Sinica, 2022, 48(10): 2374−2391 doi: 10.16383/j.aas.c200916

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c200916

关键词

复杂网络，能控性鲁棒性，攻击，优化 

摘要

研究复杂网络能控性鲁棒性对包括社会网络、生物和技术网络等在内的复杂系统的控制和应用具有重要价值. 复杂网络的能控性是指: 可通过若干控制节点和适当的输入, 在有限时间内将系统状态驱动至任意目标状态. 能控性鲁棒性则是指在受到攻击的情况下, 复杂网络依然维持能控性的能力. 设计具有优异能控性鲁棒性的复杂网络模型和优化实际网络的能控性鲁棒性一直是复杂网络领域的重要研究内容. 本文首先比较了常用的能控性鲁棒性定义及度量, 接着从攻击策略的角度分析了3类攻击的特点及效果, 包括随机攻击、基于特征的蓄意攻击和启发式攻击. 然后比较了常见模型网络的能控性鲁棒性. 介绍了常用优化策略, 包括模型设计和重新连边等. 目前的研究在攻击策略和拓扑结构优化方面都取得了进展, 也为进一步理论分析提供条件. 最后总结全文并提出潜在研究方向.

文章导读

复杂网络作为现今科学研究中的一个热点学科, 在过去20年里得到了巨大的发展[1-4]. 复杂网络普遍存在, 如互联网、神经网络、交通运输网[5]等. 同时许多系统, 如人际社会关系[6]、学术合作[7]、人类迁徙[8]等都可以抽象为复杂网络, 以进行系统地分析和研究. 除了广泛应用于数学、工程、经济等学科之外, 复杂网络更与我们的日常生活息息相关, 如在信息的传播[9]、语言的演变[6, 10-12]、流行病的传播和阻断[13-15]、网络群体智能[16-17]等方面, 复杂网络都提供了极有价值的参考模型和分析工具.

复杂网络能控性(Controllability)是复杂网络研究的一个核心问题[18-33], 其概念是指在有限时间内, 通过适当的控制输入, 控制网络从任意初始状态到达一个目标状态的能力. 人类对自然系统和技术系统的理解, 最终体现在如何有效地控制它们, 使之为人类的生存和发展服务. 作为一个跨学科的研究领域, 网络科学与控制系统理论之间的跨学科研究在过去20年里得到迅速的发展.

由于复杂网络通常具有大量的节点和连边, 其中高维动态节点系统相互连接, 这给经典控制理论和技术带来了新的机遇, 但同时也带来了巨大的挑战. 对于复杂的动态网络, 要达到最佳控制目标, 往往只需要通过外部输入控制小部分节点或连边. 作为实现网络优化控制的实用方法之一, 牵引控制(Pinning control)策略[34]旨在通过高效的算法来回答“牵引控制多少节点和哪些节点” 的问题, 以最少的能量消耗和代价, 达到牵一发而动全身的最优效果.

复杂网络在攻击下维持能控性的能力称为能控性鲁棒性(Controllability robustness). 本文中“攻击” 的表现形式为删除节点或连边. 近年来, 对复杂网络的攻击成为主要关注的问题之一[35-45]. 这些随机或恶意的攻击可能导致系统瘫痪等严重后果. 复杂网络的能控性理论为研究神经网络结构和功能之间的联系提供了分析工具, 如分析秀丽线虫 (Caenorhabditis elegans) 的各神经元功能及其与肌肉运动的联系[46]. 而能控性鲁棒性则为进一步研究提供分析基础, 如秀丽线虫部分神经元损坏可导致生物功能障碍和疾病[46], 这里神经元损伤可看作网络拓扑结构受到攻击, 即网络中的节点和连边受到破坏和攻击. 此外, 能控性鲁棒性的研究对交通运输、电力、社交网络的鲁棒控制具有重要的指导意义.

在不同背景下, 复杂网络抵御攻击的能力 (或称“抗毁性”) 具有不同的定义和度量[47]. 在维持连通性能力(Connectedness)[37, 45, 47-48]的研究中, 抗毁性是指复杂网络在攻击情况下保持连通性的能力. 在能控性研究中, 抗毁性是指网络维持能控性的能力. 为避免混淆, 本文将保持连通的抗毁性称为“连通鲁棒性”; 将保持能控性的抗毁性称为“能控性鲁棒性”, 也是本文的主要讨论对象. 良好的能控性以较强的连通性为基础, 但是, 强的连通性却不能保证良好的能控性. 同样地, 良好的能控性鲁棒性以良好的连通鲁棒性为基础, 而良好的连通鲁棒性并不能保证良好的能控性鲁棒性. 能控性鲁棒性较好的网络系统具有好的抵御攻击的能力, 同时能延迟系统的整体瘫痪, 为攻击后的补救争取时间. 相反地, 能控性鲁棒性差的系统则容易在受到攻击以后, 迅速导致网络系统的整体失效. 因此, 实用的控制网络模型应同时兼备良好的能控性和能控性鲁棒性. 基于当前理论研究的局限和日益发展的超级计算能力, 复杂网络的能控性鲁棒性研究以仿真实验研究为主[49-50]. 同时, 深度学习的发展也为这一领域提供新的研究技术[51-53]. 不同类型网络系统具有不同的能控性计算方式, 如有向和无向网络, 无权和有权网络, 以及单输入单输出和多输入多输出系统等, 因而其能控性鲁棒性的研究与优化也有所不同. 本文主要阐述针对有向网络的能控性鲁棒性研究, 主要关注以下3个关键问题:

1) 如何定义和度量复杂网络的能控性鲁棒性? 能控性鲁棒性的定义和度量为不同拓扑结构的优劣提供比较标准, 为不同攻击方式的破坏能力提供参考, 也为复杂网络的优化提供依据. 不同的定义方式具有不同的理论依据及其侧重点, 导致不同的比较结果. 在计算方式上, 基于仿真的能控性鲁棒性的计算得到的结果真实准确, 但需要较大的计算量, 而基于深度神经网络的能控性鲁棒性预测则可以较小的计算代价取得相对准确的估值.

2) 常见的攻击方式有哪些? 哪些攻击对能控性的危害最大? 针对不同的攻击方式, 复杂网络可能表现出不同的能控性鲁棒性, 所以研究攻击方式对于复杂网络的能控性鲁棒性有重要意义. 通过分析常见的攻击方式及其危害程度, 可以理解网络中节点、连边和其他特征对能控性鲁棒性的重要程度; 找到危害最大的攻击对于评价网络的性能也有着重要的意义, 启发式攻击由计算智能算法自主选择攻击对象, 可以达到相较于传统方法更大的破坏效果. 同时, 对网络攻击的研究也有助于对网络优化的研究, 对网络的攻击的理解和将其应用于优化犹如理解“矛与盾” 的关系, 既相互抑制, 又相互促进.

3) 怎样提高能控性鲁棒性? 如何达到最优的能控性鲁棒性? 对复杂网络的能控性鲁棒性优化问题属于NP (Nondeterministic polynomial time)难问题. 但是由于能控性鲁棒性度量方式, 攻击方式, 以及限制条件等的不同, 使其成为一个多目标优化问题. 同时, 由于基于仿真的能控性鲁棒性度量普遍耗时较多, 以及节点和连边特征与能控性鲁棒性之间相关性不够明确等问题, 给该优化问题带来了挑战.

围绕以上3个问题, 本文就能控性鲁棒性研究现状与进展进行归纳总结, 指出当前研究中存在的问题与技术挑战, 并探讨了未来发展趋势.

图1 匹配和节点控制中心性的例子

图2 按文献[57]连边分类举例

图4 能控性鲁棒性度量方式比较举例

本文围绕3个问题进行归纳与总结:

1)复杂网络能控性鲁棒性的定义和度量. 不同的定义因侧重点不同而稍有区别, 须根据实际应用场景选取适当的定义和度量方式.

2)常见的复杂网络攻击方式及其对网络连通性和能控性的危害. 随机攻击的危害较小, 对攻击者来说需要掌握的网络相关信息较少; 基于特征的蓄意攻击依据预先设定的特征对网络的节点或连边实施攻击, 取得的攻击效果往往较好, 对攻击者来说需要掌握较多网络相关信息; 启发式攻击以智能计算优化攻击, 往往需要具备较全面的网络相关信息和较多的计算资源, 同时攻击效果的提升也较为显著.

3)能控性鲁棒性的优化问题. 对于尚未建立的网络可采取优化建模, 对于已有网络可采取(全部或部分)重新连边策略. 如果能够掌握攻击者的信息, 则可更有效地针对某一类攻击做出防御. 一般的, 在各类攻击情况下, 极同质网络具有较好的能控性鲁棒性.

针对以上3个问题, 未来可研究内容包括:

1)深度学习和计算智能可更广泛地应用于复杂网络能控性鲁棒性的预测、分析和优化. 目前, 利用深度学习预测复杂网络能控性鲁棒性的研究和利用计算智能来生成优化网络拓扑结构的研究处于起步阶段. 深度学习和计算智能处理大规模问题能力的进一步发展, 将会对包括能控性鲁棒性在内的复杂网络各项研究带来新的机遇和挑战.

2)相关网络特征与能控性鲁棒性的相关性值得进一步探索和研究, 包括相关拓扑结构特征、关键节点和关键连边的定义与搜索等. 这一研究方向的难点在于网络规模、拓扑结构、攻击方式等同时具有多样性. 同时, 在实际网络中, 各节点和连边存在权值等因素, 因此, 相对不容易形成一般性可泛化的理论结果.

3)全齐性网络和经验必要条件的进一步研究和理论拓展. 全齐性网络和经验必要条件的研究从简单结构开始, 逐步推向一般情况, 简单的网络拓扑结构比一般实际网络更容易研究分析, 实现理论突破. 对经验必要条件的理论证明, 以及对经验和理论充分条件的探索, 将从理论上实现复杂网络能控性鲁棒性的最优化.

作者简介

楼洋

四川师范大学副研究员, 中国香港城市大学博士后. 2017年获得中国香港城市大学博士学位. 主要研究方向为复杂网络, 进化算法和机器学习. E-mail: felix.lou@my.cityu.edu.hk

李均利

四川师范大学研究员. 2002年获得浙江大学博士学位. 主要研究方向为图像处理, 目标跟踪, 智能计算. 本文通信作者. E-mail: li.junli@vip.163.com

李升

四川师范大学硕士研究生. 主要研究方向为复杂网络.E-mail: yunchunrui@163.com

邓浩

四川师范大学硕士研究生. 主要研究方向为进化计算, 复杂网络.E-mail: 18108015390@189.cn