网络可控性：结构可控性与最大匹配

“集智百科精选”是一个长期专栏，持续为大家推送复杂性科学相关的基本概念和资源信息。作为集智俱乐部的开源科学项目，集智百科希望打造复杂性科学领域最全面的百科全书，欢迎对复杂性科学感兴趣、热爱知识整理和分享的朋友加入！

本文是对集智百科中“网络可控性”词条的摘录，参考资料及相关词条请参阅百科词条原文。

本词条由集智俱乐部众包生产，难免存在纰漏和问题，欢迎大家留言反馈或者前往对应的百科词条页面进行修改，一经修改，可以获得对应的积分奖励噢！

一、背景

二、复合量子系统的控制与代数图论

三、编者推荐

四、百科项目志愿者招募

五、集智百科平台底层维护人员招募

网络可控性 Network Controllability研究的是网络的结构可控性。可控性描述了我们在有限时间内，通过合适的输入选择，引导动力系统从任何初始状态到任何期望的最终状态的能力。这个定义与我们直观的控制概念非常吻合。一般的有向加权复杂网络的可控性是近年来世界范围内许多研究小组的重点研究课题。夏尔马[1]等人最近在多种生物学网络(基因-基因、 miRNA-基因、蛋白质-蛋白质相互作用网络)上的研究，确定了骨肉瘤表现型特征的控制目标，显示了基因和蛋白质在维持肿瘤微环境中的重要作用。

图1：控制一个简单的网络。

背景

考虑复杂网络 Complex Network上的经典线性时不变动力学

其中，向量

表示在N个节点的系统时间 t 时的状态。

N×N的矩阵A描述了系统的连接图以及各组分之间的交互强度。N×M矩阵B列出了由外部控制器控制的节点。控制器通过施加给系统的时间相关向量

来实现对系统的控制。为了确定驱动节点的最小数目，N_D亦即确定对最少几个节点施加控制便足以完全控制系统的动力学进程，在这方面，Liu等人尝试了将结构控制理论 Structural Control Theory、图论 Graph Theory 和统计物理 Statistical Physics的工具的结合。他们发现，完全控制一个网络所需要的最少输入或驱动节点，取决于网络的最大匹配 maximum matching，也就是不共享起始顶点和终止顶点的最大边集。从这个结论出发，一个基于入-出度分布的分析框架被开发出来，用于预测无标度网络 scale-free network和ER随即图 Erdős–Rényi Graph的n_D=N_D/N值。

同样值得关注的是，刘等人的工作提出了这么一个问题：度 Degree,作为网络中一种纯粹的局部度量，能否完全描述网络的可控性？是不是即便稍微远一点的节点，就对网络的可控性没有影响？事实上，对于许多现实世界里的网络 Real-World Networks，像食物网络 Food Webs、神经元网络 Neuronal Network 和代谢网络 Metabolic Network，Liu等人计算的n_D^real和n_D^rand_degree 的值并不匹配。值得注意的是。如果可控性主要是由度决定，那么为什么对于许多现实世界的网络来说，n_D^real和n_D^rand_degree如此不同？他们认为，这可能是由于度相关性的影响。然而，已有的研究表明，网络的可控性只能通过中间性和封闭性来改变，而完全不需要使用度（图论）或度相关性 Degree Correlations。

图2：示意图显示了一个有向向网络的控制。对于给定的有向网络（图a），可以计算其最大匹配：没有共同头部或尾部的最大边集。最大匹配将由一组顶点不相交的有向路径和有向环组成（请参见图b中的红色边缘）。如果一个节点是匹配边的头部，则该节点是匹配的（图b中的绿色节点）。否则，它是不匹配的（图b中的白色节点）。那些不匹配的节点是需要施加控制的节点，即驱动节点。通过向这些驱动节点注入信号，可以得到一组以起点为输入的有向路径（见图c）。这些路径被称为“茎”。得到的有向图称为U根因子连接。通过将定向周期“嫁接”到那些“茎”，人们就会得到“芽”。得到的有向图称为仙人掌 cacti（见图d）。根据结构可控性定理，由于存在跨越受控网络的cacti结构（参见图e），因此该系统是可控的。受控网络（图e）下的cacti结构（图d）是维持可控性的“骨架”。

结构可控性

结构性质的概念最早是由 Lin (1974) 提出的，然后由 Glover 和 Silverman (1976)扩展。主要的问题是，对于可变系统参数来说，缺乏可控性或可观测性是否是普遍存在的现象。在结构控制的框架里，系统参数要么是独立自由变量，要么是固定的0。这对于物理系统的模型是一致的，因为参数值永远不会准确地获得，零值除外，零值代表没有交互和连接。

最大匹配

在图论中，匹配（图论）是一组没有共同顶点的边。Liu等人将此定义扩展到有向图，其中匹配是一组不共享起始或终止顶点的有向边。很容易知道，有向图的匹配由一组顶点不相交的简单路径和周期组成。定向网络的最大匹配可以通过在二部图表示 Bipartite Representation中使用经典的Hopcroft-Karp 算法来高效地计算，该算法在最坏情况下的时间复杂度是O(E)。对于无向图，统计物理中开发的空腔法 Cavity Method研究了最大匹配的大小和数量的解析解。Liu等人扩展了有向图的计算范围。

通过计算各种真实网络的最大匹配，Liu等人断言驱动节点的数量主要由网络度分布P(k_in,k_out)决定。他们还使用空腔方法计算了具有任意度分布的网络集合的驱动节点的平均数量。有趣的是，对于链图 Chain Graph和弱密集连通图 Weak Densely Connected Graph，两者都具有非常不同的进出度分布；Liu等人的公式将会计算得出出nD的相同值。此外，对于许多真实世界地网络，即食物网、神经元和代谢网络，Liu等人计算的n_D^real和n_D^rand_degree值的不匹配。值得注意的是，如果可控性纯粹由度决定，那为什么n_D^real和n_D^rand_degree对于许多现实世界的网络来说是如此不同？对于网络中的控制健壮性是否更多地受到基于度的中介中心性 Betweenness Centrality和紧密度中心性 Closeness Centrality的影响，仍然是开放的。

虽然稀疏图 Sparser Graph更难以控制，但是，中介中心性和紧密度中心性，或度异质性 Degree Heterogeneity在决定具有几乎相似的度分布的稀疏图的可控性中是否起更重要的作用？这是个有趣的问题。

复合量子系统的控制与代数图论

人们还开发了在复合量子系统的通用控制背景下的网络控制理论，其中子系统及其相互作用分别与节点和链路相关联。该框架允许使用代数图论中的工具通过图的最小等级和相关概念来制定卡尔曼准则 Kalman's Criterion。

编者推荐

集智视频

漫谈图论的起源、发展与应用

https://campus.swarma.org/course/1745

讲师为赵海兴，课程难度为中级。本课程中，介绍了图论中的基本概念和网络科学使用的工具，可以帮助认识真实网络的关键性质。随后的章节将系统地研究这些网络性质，深入理解这些网络性质在认识复杂系统方面发挥的重要作用。

网络科学研究中许多网络包含数千个甚至数百万个节点和链接。在研究小网络的基础上，还需要走的更远。对于具有很多节点和连边的网络，过于复杂，目测的方式对于理解和认识这类网络不再适用。需要适用网络科学的工具来刻画网络的拓扑，例如：度、度分布、邻接矩阵、加权网络、二分网络、路径、距离、连通性、集聚系数等。

图3：赵海兴，现任青海师范大学校长，主要从事网络科学和信息处理的研究工作。

量子系统的演化：薛定谔方程

https://campus.swarma.org/course/562

本课程难度为初级，讲师为吴金闪（图4）。将结合薛定谔方程的例子为你介绍薛定谔方程，同时还将涉及系本征值和本征向量的相关内容。

薛定谔方程又称薛定谔波动方程，是由奥地利物理学家薛定谔提出的量子力学中的一个基本方程，也是量子力学的一个基本假定。

图4：吴金闪，北京师范大学系统科学教授，一直在践行和呼吁融合边界的研究、教学和思考。

论文解读：符号一致性网络的可控性和稳定性

https://campus.swarma.org/course/2495

讲师为朱佳伟，课程难度为中级。本课程中，主要讲解利用符号网络描述带有竞争关系的多智能体系统，并分析符号一致性网络的可控性和稳定性问题。

集智文章

Nature 历年网络科学文集：网络层次和结构

近十年来网络科学蓬勃发展，Nature 系列期刊上发表了近百篇以网络为主题的论文。我们针对为这些论文做了分类，编译了论文摘要，并做简单评价，以展现网络科学的发展的脉络。本篇整理的 21 篇论文涉及生态、进化、大脑、社交等，主要关注网络的层级和结构。

CSDN社区

图论与代数结构
https://blog.csdn.net/fnoi2014xtx/article/details/106773719?
动态大系统方法导论（四）-结构可控性及其在复杂网络中的应用
https://blog.csdn.net/ycheng_sjtu/article/details/25228745?

百科项目志愿者招募

作为集智百科项目团队的成员，本文内容由信白初步参与编译，Ricky审校，糖糖编辑。我们也为每位作者和志愿者准备了专属简介和个人集智百科主页，更多信息可以访问其集智百科个人主页。