结构可控性与最大匹配 · 生物医学网络科学

结构可控性

Lin（1974）提出结构可控性（structural controllability）：只考虑 $A$ 、 $B$ 中哪些元素为零、哪些不为零（即网络拓扑），不关心非零元素的具体数值。如果存在一组非零权重使 $(A,B)$ 可控，就称它结构可控。一个重要事实是：若系统结构可控，则几乎所有权重取值（除去一个测度为零的集合）都使它可控。因此，结构可控性只依赖网络拓扑，恰好适合权重未知的生物网络。

最小输入定理

匹配（matching）：有向图中一组边，任意两条边既不共享起点，也不共享终点。若某节点是某条匹配边的终点，称它为匹配节点，否则为非匹配节点。边数最多的匹配称为最大匹配；所有节点都是匹配节点时称为完美匹配。

最小输入定理（Liu、Slotine 与 Barabási 2011，Nature）：控制网络所需的最小驱动节点数为 $N_D=\max\big(N-|M^*|,\;1\big)$ $|M^*|$ 为最大匹配的边数。若存在完美匹配， $N_D=1$ （任选一个节点即可）；否则，最大匹配下的非匹配节点就是驱动节点（driver nodes），对每个驱动节点直接施加独立输入即可控制整个网络。

直观理解：每条匹配边是一条“控制信号传递链”中的一环；最大匹配把网络分解为若干条互不相交的有向路径（以及环），每条路径的起点必须由外部输入驱动。回到星形例子：中心 1 只能“匹配”一个叶子，另一个叶子和中心本身是非匹配节点， $N_D=2$ ，与 Kalman 判据的结论一致。

计算方法：把有向图转化为二分图——每个节点拆成“出端” $u^+$ 和“入端” $v^-$ ，有向边 $u\to v$ 变为 $u^+$ – $v^-$ 的无向边。有向图的最大匹配就是这个二分图的最大匹配，可用 Hopcroft–Karp 算法在 $O(\sqrt N L)$ 时间内求得（ $L$ 为边数）。未被匹配的入端对应的节点就是驱动节点。本专题的代码示例用 NetworkX 实现这一步，并用 Kalman 判据验证结果；定理的来源与算法伪代码见数学推导与算法。

最大匹配一般不唯一，所以驱动节点集合也不唯一，但驱动节点的数目 $N_D$ 唯一。说“某个节点是驱动节点”之前，要先问“在哪一个最大匹配下”。这一点正是驱动节点与网络结构中节点角色分类和驱动节点的枚举、分类与自适应控制的出发点。

“几乎所有权重”的含义

把 $A$ 、 $B$ 中所有非零元看作独立的自由参数 $\mathbf p=(p_1,\dots,p_r)$ 。 $(A,B)$ 不可控 $\iff$ $\mathcal C$ 的所有 $N\times N$ 子式都为零。每个子式都是 $\mathbf p$ 的多项式。若存在一组参数使系统可控（即结构可控），则至少有一个子式不是零多项式；而非零多项式的零点集在 $\mathbb R^r$ 中测度为零。所以结构可控时，“随机”取权重几乎必然可控。

结构可控性与精确参数下的可控性

结构可控 ≠ 给定参数的系统可控。 “几乎所有”依赖于“各非零元是相互独立的自由参数”这一假设。真实模型中参数常常受约束：边权对称、多条边权重相同、所有节点有相同的自衰减项等，这些约束恰好可能落在测度为零的“坏集合”里。

例子： $N$ 个节点的完全图（每对节点双向相连）。它含有一条覆盖所有节点的有向环，存在完美匹配，结构上只需 1 个驱动节点。但若所有边权都等于 1， $A=J-I$ （ $J$ 为全 1 矩阵）的特征值 $-1$ 具有 $N-1$ 重。按 PBH 判据（ $(A,B)$ 可控 $\iff$ 对 $A$ 的每个特征值 $\lambda$ ， $\operatorname{rank}[\lambda I-A,\;B]=N$ ）， $-I-A=-J$ 的秩只有 1，于是需要 $\operatorname{rank}B\ge N-1$ ，即 $N-1$ 个独立输入。Yuan 等（2013，Nature Communications）的“精确可控性”框架给出一般结论：给定 $A$ 时最少输入数等于 $A$ 各特征值几何重数的最大值。另一方面，若每个节点带有独立的自环参数（自身动力学），结构上 $N_D$ 会变为 1（Cowan 等 2012，PLoS ONE）——驱动节点数对“如何建模节点自身动力学”非常敏感。

精确可控性：给定权重时的最少输入数

Yuan 等（2013）从 PBH 判据出发：对特征值 $\lambda$ ， $\operatorname{rank}[\lambda I-A,B]=N$ 要求 $B$ 补足 $\lambda I-A$ 缺失的秩 $N-\operatorname{rank}(\lambda I-A)=\mu(\lambda)$ （ $\lambda$ 的几何重数），而 $B$ 的每一列最多补一个秩。因此

$N_D=\max_{\lambda}\;\mu(\lambda)=\max_{\lambda}\big[N-\operatorname{rank}(\lambda I_N-A)\big].$

几个推论便于计算：

无向网络（ $A$ 对称、可对角化）：几何重数等于代数重数，只需数特征值的重数。
稀疏网络：大型稀疏网络中最大重数多出现在 $\lambda=0$ ，于是 $N_D\approx\max\{1,\;N-\operatorname{rank}(A)\}$ ，只需一次秩计算（Yuan 等 2013 用 LU 或奇异值分解）。
稠密、等权网络：许多节点拥有相同的邻居，使 $\lambda=-1$ 的重数很大， $N_D\approx\max\{1,\;N-\operatorname{rank}(I_N+A)\}$ ；完全图正是极端情形（ $N_D=N-1$ ）。
驱动节点的位置：对 $\lambda_M I-A$ （ $\lambda_M$ 为重数最大的特征值）做初等列变换，找出线性相关的行，这些行对应的节点就是驱动节点。

Yuan 等报告：在有向稀疏网络中，精确可控性给出的 $n_D$ 与最大匹配几乎一致，说明稀疏网络的可控性对权重不敏感；而稠密且权重相同的网络很难控制，这是结构可控性无法揭示的现象。代码示例中，对 $N=300$ 、 $L=450$ 的单位权重有向 ER 网络， $N-\operatorname{rank}(A)$ 、最大几何重数与最大匹配给出相同的 $N_D$ ；完全图在全 1 权重与随机权重下分别需要 $N-1$ 与 1 个输入（见代码示例）。

节点自身动力学的影响。若每个节点都有一阶自身动力学 $\dot x_i=a_{ii}x_i+\dots$ ，结构理论把它当作自环，每个节点都能“匹配自己”，于是 $N_D=1$ 。但若所有自环权重相同（同一种细胞、同一种神经元），由 $\operatorname{rank}[B,AB,\dots]=\operatorname{rank}[B,(A+wI)B,\dots]$ ，驱动节点数与完全没有自环时完全相同。Liu 与 Barabási（2016）综述的进一步结果是：自环取几种不同权重时， $n_D$ 在各类自环比例相等处最小——驱动节点数取决于“节点动力学有多少种”，而不仅是拓扑。

两种可控性回答的问题可以概括为：

	结构可控性	精确参数下的可控性
需要的信息	$A$ 、 $B$ 的零/非零模式（拓扑）	$A$ 、 $B$ 的全部数值
判据	Lin 定理；最小输入数由最大匹配给出	Kalman 秩判据、PBH 判据；精确可控性框架（最大几何重数）
计算	Hopcroft–Karp， $O(\sqrt N L)$	特征值与秩计算，一般 $O(N^3)$ ；稀疏网络只需 $\operatorname{rank}(A)$
结论的含义	对几乎所有独立取值的权重成立	只对这一组参数成立
失效情形	参数之间有约束（对称、相等、相同自衰减），可能落入测度为零的例外集合	参数未知或随时间变化时无法使用

最大匹配框架与最小支配集框架

最大匹配框架（Liu 等 2011）：线性动力学；每个驱动节点接收一个独立信号，信号沿控制路径逐级传递；驱动节点数 $N_D$ 多项式时间可算；驱动节点倾向于避开枢纽。适用于有向网络，回答的是结构可控性问题。
最小支配集框架（MDSet，如 Nacher 与 Akutsu 2012，New Journal of Physics）：假设驱动节点可以对每条出边分别施加独立控制，因此每个节点要么是驱动节点、要么与驱动节点直接相邻；求最小支配集是 NP 难问题，常用整数规划或贪心近似；在这一框架下高度节点倾向于被选中，度异质的网络反而更容易被支配。在无向网络中，控制通常基于这一框架，控制信号施加在连边上；症状网络的模块控制研究采用的就是这一框架。

两者回答的是不同建模假设下的问题，驱动节点数和“枢纽是否重要”的结论不能直接比较。注意缩写：MDS 指最大匹配框架下的最小驱动节点集（minimum driver node set），MDSet 指最小支配集（minimum dominating set）。