输入图：控制复杂网络的隐藏几何结构

一句话看懂

一个网络有成千上万种最小输入节点集（MIS），它们之间有什么关系？这篇论文把原网络的边换成反映”谁能替换谁”的新边，得到输入图（input graph）：输入节点在输入图中的邻居一定能替换它；同一连通分支中的节点控制类型相同。于是，复杂的控制关系被约化为输入图的几个连通分支，稠密网络中”大多数节点要么都能当输入节点、要么都不能”的双峰现象也由此得到拓扑解释。

研究背景与问题

本文把驱动节点称为输入节点（input node），把最小驱动节点集称为最小输入节点集（Minimum Input nodes Set, MIS）。如结构可控性与最大匹配中所述，MIS 由最大匹配给出，但最大匹配不唯一，MIS 的数目可随网络规模指数增长，枚举它们是 #P 问题。按节点是否出现在某个 MIS 中，可以分为：

• 可能输入节点（possible input node）：至少出现在一个 MIS 中；
• 冗余节点（redundant node）：不出现在任何 MIS 中。

Jia 等（2013）发现稠密网络中这两类节点的比例呈双峰分布（集中控制与分布式控制），但其成因和改变节点类型的方法仍不清楚。论文要回答三个问题：（1）众多 MIS 之间是什么关系？（2）什么拓扑结构决定一个节点是不是可能输入节点？（3）如何设计包含指定节点的 MIS？

核心思想与方法

控制邻接与交换定理

证明思路很直观：$a$ 是输入节点，没有匹配入边。取 $a$ 的一条入边 $c\to a$。如果 $c$ 没有匹配出边，就可以把 $c\to a$ 加入匹配，与”最大”矛盾；所以 $c$ 必有匹配出边 $c\to b$。把 $c\to b$ 换成 $c\to a$，匹配边数不变，仍是最大匹配，此时 $b$ 失去匹配入边，成为新的输入节点。每次交换只改动一条匹配边、一个输入节点，是对原控制方案的最小改动。

两个推论：一个节点出现在所有 MIS 中，当且仅当它的入度为 0；输入节点的控制邻接邻居数等于它的入度。

小例子：网络只有两条边 $c\to a$、$c\to b$。$c$ 入度为 0，必为输入节点；$c$ 只能匹配一条出边。若匹配 $c\to b$，MIS 为 $\{a,c\}$；$a$ 与 $b$ 控制邻接，交换后得 MIS $\{b,c\}$。

输入图与控制分支

邻接推论：（1）对任一 MIS $D$ 和其中的输入节点 $n$，$C(n)$ 中的节点都是可能输入节点；（2）若某节点不属于 $D$ 中任何输入节点的控制可达集，它就是冗余节点。因此输入分支中的节点全是可能输入节点，匹配分支中的节点全是冗余节点，节点类型由它所在分支的类型决定。论文还证明，控制分支的类型与选用哪个最大匹配无关。

控制路径本质上是二分图中从非匹配入端出发的交替路径：非匹配边、匹配边交替出现。

一个稍大的例子：边为 $1\to2$、$1\to3$、$4\to3$、$4\to5$、$2\to6$，取最大匹配 $\{1\to2, 4\to3, 2\to6\}$，MIS 为 $\{1,4,5\}$。由 $4\to5$（非匹配）和 $4\to3$（匹配）知 5 与 3 控制邻接；由 $1\to3$（非匹配）和 $1\to2$（匹配）知 3 与 2 控制邻接。所以 $C(5)=\{5,3,2\}$，网络另有 MIS $\{1,4,3\}$、$\{1,4,2\}$。节点 6 只有一条入边且来自 2，而 2 没有别的出边，6 不与任何输入节点控制邻接，单独构成匹配分支，是冗余节点。

改变控制分支的类型

既然同一分支类型相同，要改变大量节点的类型，只需改变分支类型：

• IC → 匹配分支：为分支中每个输入节点添加一条从非饱和节点（没有匹配出边的节点）指向它的边，使其被匹配；
• 匹配分支 → IC：若匹配分支被非饱和节点连接（称为 UMC），先用类似方法把这些非饱和节点匹配掉，变成饱和匹配分支（SMC）；对 SMC，找控制可达集最大的节点 $n$，设其匹配入边为 $m\to n$，添加边 $m\to d$（$d$ 为某个输入节点），于是 $d$ 与 $n$ 控制邻接，$n$ 的可达集整体变为可能输入节点。

构建输入图的复杂度：最大匹配 $O(N^{0.5}L)$，每个节点做一次广度优先搜索 $O(L)$，最坏情况总计 $O(NL)$；而利用输入图为某个输入节点找替代节点只需 $O(1)$。

主要发现

1. 复杂控制关系可约化为少数控制分支。Little Rock 食物网、Political blogs 等网络的输入图只有几个连通分支（图 2A、B）。
2. 许多真实网络存在巨控制分支。表 1 的 37 个真实网络中，TRN-Yeast-1 最大控制分支占 99.21%（输入分支），Consulting 占 97.83%，Slashdot0902 占 91.23%。
3. 巨分支解释双峰现象。在 $N=10^4$、入/出度指数均为 3 的无标度网络中，最大控制分支规模随平均度增大而增大，控制分支数目单调减少，稠密网络中只剩一个巨分支；巨分支是 IC 则多数节点是可能输入节点，是 MC 则多数是冗余节点。
4. 少量加边即可翻转控制模式。网络越稠密，所需加边比例越低。Amazon0312 的最大分支是 SMC（占 83.61%），加边比例仅 0.00003% 即可改变 75.74% 节点的类型；Facebook_0 加 0.02% 的边改变 81.84%。相反，稀疏的 E.Coli 转录网络需加 34.78% 的边，仅改变 1.89%。
5. 翻转后 MIS 显著变小（补充表 S2），例如 Ythan 食物网 MIS 比例从 51.11% 降到 3.70%，TRN-Yeast-1 从 96.46% 降到 0.70%，说明该方法也可用于优化可控性。

怎样读这篇论文

• 正文只有 4 页结论性叙述，证明全在补充材料。建议顺序：正文图 1 → 补充材料第 2 节（最大匹配与 Berge 定理）→ 3.1 交换定理证明 → 3.3 邻接推论 → 回到正文图 2、图 3。
• 图 1B 同时画出原网络、二分图和输入图，务必对照理解；图 1C 画出全部 6 个 MIS 及其交换关系。
• 表 1 中 I、U、S 分别表示 IC、UMC、SMC；$p$ 是改变最大分支类型所需加边比例，$\Delta n_D$ 是类型改变的节点比例。
• 补充材料中 Lemma 1（一个控制分支不能同时含输入节点又被非饱和节点连接）是理解 UMC/SMC 区分的关键，可第二遍再读。

局限与后续工作

• 理论基于线性时不变系统和结构可控性；加边在许多真实系统（如蛋白相互作用）中难以实现。
• 讨论部分指出两点限制：网络中可能存在当前 MIS 无法到达的环，需要额外输入信号；同一输入分支中若两个输入节点在输入图中共享邻居，它们不能同时被替换。
• 构建完整输入图最坏 $O(NL)$，对超大网络仍偏慢。
• 后续工作与相互关系：
  • 本文是这一系列研究的理论枢纽，回答了 2014 年偏好匹配论文留下的”所有可能 MDS”问题。
  • Zhang、Han 与 Zhang（2017，Sci Rep）利用交替路径与本文的邻接推论，在 Hopcroft–Karp 算法的最后一步直接得到所有可能输入节点及每个输入节点的替代节点集，复杂度降为 $O(N^{0.5}L)$。
  • 本文用加边改变控制模式；Zhang 与 Li（2019，Physica A）改用删边，Zhang、Zhu 与 Zhao（2021，Physica A）改用反转边，都以”切断驱动节点与巨输入分支的交替路径连接”为核心思想。
  • 交换定理也是后续研究基于控制路径给节点分 7 类、寻找”控制核心点”的基础（见驱动节点的枚举、分类与自适应控制）。

关联知识

• 驱动节点的枚举、分类与自适应控制对本文做了概括；结构可控性与最大匹配中的最大匹配、二分图拆点是理解控制邻接的前提；驱动节点与网络结构提到的 Jia 等（2013）控制模式双峰性，正是本文解释的对象。
• 连通分支与巨连通分支中的连通分支概念在这里被用到一个”派生图”上：不是原网络的连通性，而是”可替换性”的连通性。
• 在生物网络中，某些蛋白无法作为干预靶点。交换定理提供了一个 $O(1)$ 的”换靶”操作：沿输入图找一个邻居替换即可。

延伸思考

1. 用本文的小例子（边 $1\to2$、$1\to3$、$4\to3$、$4\to5$、$2\to6$）手工画出输入图，并验证节点 6 是冗余节点。如果再加一条边 $5\to6$，节点 6 的类型会变吗？
2. 交换定理说”入度为 0 的节点出现在所有 MIS 中”。在基因调控网络中，这类节点可能对应什么样的基因？
3. 本文指出新发现的边只会让输入图的巨分支变大。对于不完整的蛋白相互作用网络，这对”某蛋白是冗余节点”的结论意味着什么？
4. 分布式控制模式提供了很多可替换的控制方案。请从药物靶点选择和网络安全两个角度，分别讨论它的利与弊。