复杂网络能控性鲁棒性研究进展

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

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

复杂网络作为现今科学研究中的一个热点学 科, 在过去 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 个问题, 本文就能控性鲁棒性研究 现状与进展进行归纳总结, 指出当前研究中存在的 问题与技术挑战, 并探讨了未来发展趋势.

专知便捷查看