经典论文难度：进阶

复杂网络的可控性

Controllability of complex networks

Liu Y-Y, Slotine J-J, Barabási A-L · Nature 2011 · DOI: 10.1038/nature10011

结构可控性驱动节点最大匹配最小输入定理度分布

一句话

把结构可控性转化为最大匹配，算出最少驱动节点数，发现其主要由度分布决定，且驱动节点倾向于避开枢纽。

相关专题：网络可控性与稳定性

VIDEO讲解视频

复杂网络的可控性5 分 21 秒

文字稿

大家好，这一期我们精读2011年发表在Nature上的复杂网络可控性论文。它问了一个很朴素的问题：要控制一个复杂网络，最少需要直接控制多少个节点？又该控制哪些节点，这和网络结构有什么关系？

控制理论早就有线性系统可控的判据，也就是Kalman秩判据，要求可控性矩阵满秩。但真实网络的边权通常未知，或者只知道个大概。节点数成千上万时，秩的数值计算既昂贵又不稳定。作者因此借助Lin在1974年提出的结构可控性，只关心哪些元素为零、哪些不为零。如果对几乎所有非零权重取值系统都可控，就称它结构可控，权重未知的问题就绕开了。

关键一步，是把最少输入问题映射成图论里的最大匹配。匹配是一组有向边，任意两条既不共享起点，也不共享终点。最小输入定理说，最少驱动节点数等于节点数减去最大匹配的边数，至少为1。如果存在完美匹配，任选一个节点作驱动节点就够了。

看这个小网络，橙色的边是逐条找出的最大匹配。被某条匹配边指向的节点叫匹配节点，其余的是非匹配节点。直观上，最大匹配把网络分解成若干条互不相交的有向路径，以及一些有向环。每条路径的起点必须由外部信号驱动，环则可以挂到已有路径上，不需要新的独立输入。画面上标红的非匹配节点就是驱动节点，对它们施加独立输入，网络就结构可控。最大匹配可以用Hopcroft Karp算法高效求出，所以大型真实网络也能算。

作者还用统计物理中的空腔方法，对给定度分布的网络解析计算驱动节点比例。并分析了基因调控、食物网、代谢、神经元、互联网、社交和通信等多类真实网络。再与两种随机化对照，一种保持每个节点的入度和出度，另一种只保持节点数和边数。结果是，保持度序列的随机网络驱动节点比例与原网络接近，完全随机化后差异明显。所以驱动节点数主要由度分布决定，空腔方法的解析预测也与真实网络相符。画面左边是度分布均匀的随机网络，右边是度分布高度异质的无标度网络。论文发现，平均度越低、度分布越不均匀，需要的驱动节点就越多。作者报告基因调控网络的驱动节点比例较高，而一些社会网络较低。

第二个发现与直觉相反，驱动节点倾向于避开枢纽，多为低度节点。原因在于，一个节点在匹配中只能匹配一个下游节点。枢纽虽然有众多下游，其中也只有一个能被它带动。作者还按删除一条边对控制的影响，把边分成三类。删除后必须增加驱动节点的是关键边，驱动节点集合不变的是冗余边，其余是普通边。

当然，这些结论建立在线性时不变动力学和结构可控性的假设之上。可控只表示存在某种输入，不考虑所需的能量和时间，而生物系统多为非线性和多稳态。Cowan等人指出，如果每个节点都有自环，就存在完美匹配，驱动节点数会大幅下降。所以度分布决定可控性这一结论，依赖于忽略节点自身动力学的假设。

最大匹配一般不唯一，所以本文只给出驱动节点的数目和一个可行集合。后续工作研究了节点在所有方案中的角色、只控制部分目标的目标控制，以及输入图框架。在无向网络常用的最小支配集框架里，高度节点反而更重要，两种框架不能直接比较。2017年，Yan等人在线虫连接组上，第一次用消融实验检验了网络控制的预测。

对生物医学来说，这篇论文提供了一个从网络结构出发思考干预点的框架。但基因调控网络里驱动节点多为低度节点，并不意味着药物就该靶向低度基因。这里要分清结构可控和实际可控，后者还要面对控制能量、非线性和多稳态。同样的控制思路，后来也被尝试用于症状网络。

总结一下，最小输入定理把可控性问题变成了多项式时间可解的匹配问题。驱动节点数主要由度分布决定，稀疏、异质的网络最难控制。驱动节点倾向于避开枢纽，这和直觉正好相反。这些结论依赖线性动力学和忽略自环等假设，阅读时要记住这些前提。建议精读最小输入定理和匹配示意图，再拿星形网络自己找一找驱动节点。

一句话看懂

要让一个有向网络（在线性动力学下）能被引导到任意状态，最少需要直接施加控制信号的节点数，等于节点数减去网络最大匹配的边数；未被匹配的节点就是驱动节点。由此可以在多项式时间内分析大型真实网络的可控性。

研究背景与问题

控制理论早就给出了线性系统 $\dot{\mathbf x}=A\mathbf x+B\mathbf u$ 可控的判据（Kalman 秩判据）：可控性矩阵 $[B, AB, \dots, A^{N-1}B]$ 满秩。但直接用于复杂网络有两个障碍：真实网络的边权 $A$ 通常未知或只知道大概；节点数成千上万时，秩的数值计算既昂贵又不稳定。此外还有一个更基本的问题：在一个复杂网络中，最少需要控制多少个节点、控制哪些节点？这与网络结构有什么关系？

核心思想与方法

作者基于 Lin（1974）的结构可控性理论：只关心 $A$ 、 $B$ 中哪些元素为零、哪些非零，若对几乎所有非零权重的取值系统都可控，则称系统结构可控。这样就绕开了权重未知的问题。

关键一步是把“最少输入”问题映射为图论中的最大匹配：

匹配：有向图中一组边，任意两条既不共享起点，也不共享终点。被某条匹配边指向的节点称为匹配节点，否则为非匹配节点。

最小输入定理：控制网络所需的最少驱动节点数 $N_D=\max\big(N-|M^*|,\,1\big),$ 其中 $|M^*|$ 是最大匹配的边数。若存在完美匹配，任选一个节点作驱动节点即可；否则，对某一最大匹配下的全部非匹配节点施加独立输入，即可使网络结构可控。

直观理解：最大匹配把网络分解为若干条互不相交的有向路径（以非匹配节点为起点）和若干有向环；每条路径的起点必须由外部信号驱动，环可以“挂”到已有的路径上而不需要新的独立输入。最大匹配可用 Hopcroft–Karp 算法高效求得。

在此基础上，作者用统计物理中的空腔方法（cavity method）对给定入度、出度分布的网络系综解析计算驱动节点比例 $n_D=N_D/N$ ，并分析了基因调控、食物网、代谢、神经元、互联网、社交、通信等多类真实网络。为判断哪些结构因素决定 $n_D$ ，作者比较了两种随机化：保持每个节点入度和出度的随机化，以及完全随机化（只保持节点数和边数）。

主要发现

可在大网络上计算：最小输入定理把一个看似组合爆炸的问题变成多项式时间可解的匹配问题。
驱动节点数主要由度分布决定：保持度序列的随机化网络的 $n_D$ 与原网络接近，而完全随机化后差异明显；空腔方法的解析预测与真实网络的计算结果相符。
稀疏、异质的网络最难控制：平均度越低、度分布越不均匀，需要的驱动节点越多；稠密、均匀的网络只需少数驱动节点。作者报告基因调控网络的 $n_D$ 较高，而一些社会网络较低。
驱动节点倾向于避开枢纽：与直觉相反，模型网络和真实网络中的驱动节点都倾向于是低度节点。原因在于一个节点在匹配中只能“匹配”一个下游节点，枢纽的众多下游中只有一个能被它带动。
边的分类：根据删除某条边对控制的影响，把边分为关键边（删除后必须增加驱动节点）、冗余边（删除后驱动节点集合不变）和普通边，用于分析控制的鲁棒性。

怎样读这篇论文

先读正文第一部分，弄清楚结构可控性的含义以及从 Kalman 判据到“结构”的转变；然后精读最小输入定理和配套的匹配示意图（图中用小网络展示匹配、非匹配节点与驱动节点），建议对照结构可控性与最大匹配中的星形网络例子自己验证；接着看真实网络的汇总表和 $n_D$ 与随机化网络的比较图，这是“度分布决定可控性”结论的依据。空腔方法的推导在补充材料中，篇幅很长，初读可以只看结论。

局限与后续工作

线性与结构假设：结论基于线性时不变动力学和结构可控性，“可控”只表示存在某种输入能把系统带到任意状态，不考虑所需能量和时间；生物系统多为非线性、多稳态。后续 Yan 等（2012）研究了控制能量，Zañudo、Yang 与 Albert（2017）提出了基于反馈顶点集的非线性控制框架。
自环与节点动力学：Cowan 等（2012）指出，若每个节点都有自身动力学（自环），则存在完美匹配，驱动节点数会大幅下降，“度分布决定可控性”的结论依赖于忽略节点自身动力学这一假设。
控制哪些节点：最大匹配一般不唯一，驱动节点集合不唯一，本文只给出数目和一个可行集合。后续工作研究了节点在所有最小驱动节点集中的角色（关键、间歇、冗余；Jia 等 2013 的控制双峰性）、只控制部分目标节点的目标控制（Gao 等 2014），以及输入图框架（Zhang、Lv 与 Pu 2016，Scientific Reports，DOI 10.1038/srep38209）和高效枚举所有可能输入节点的算法（Zhang、Han 与 Zhang 2017，Scientific Reports，DOI 10.1038/s41598-017-10744-w），这两篇另有专门精读。
框架之争：在无向网络中常用的最小支配集框架做了不同的建模假设，在那里高度节点反而更重要；两种框架的结论不能直接比较。
实验检验：Yan 等（2017）在线虫连接组上第一次用消融实验检验了网络控制原理的预测。

关联知识

线性系统的可控性（Kalman 判据）、结构可控性与最大匹配、驱动节点与网络结构（含最大匹配与最小支配集框架）和数学推导与算法（最小输入定理的来源）都以本文为核心；网络可控性与稳定性中的最大匹配交互演示可以亲手找驱动节点。
驱动节点的枚举、分类与自适应控制正是从本文“最大匹配不唯一”这一点出发的。
本文的度分布视角承接幂律度分布与无标度网络；把控制理论用于症状网络的尝试见症状网络的模块控制。

延伸思考

星形网络（中心指向 $N-1$ 个叶子）需要多少个驱动节点？如果把方向反过来（所有叶子指向中心）呢？用最大匹配解释。
如果每个节点都加上自环，最小输入定理会给出什么结果？这个结果在生物学上意味着什么？是否合理？
在一个基因调控网络中，驱动节点多为低度节点。这是否意味着药物应当靶向低度基因？请从“结构可控”与“实际可控”的区别讨论。