研究论文难度：进阶

动态网络的自适应控制

Adaptive Control of Dynamic Networks

Pan C, Zhang X, Zheng H, Zhang Y, Su Z, Zhang C, et al. · IEEE Transactions on Network Science and Engineering 2026 · DOI: 10.1109/TNSE.2025.3605812

动态网络自适应控制最小驱动节点集最大匹配额外控制代价

一句话

在只知道历史拓扑的条件下，为动态网络每个快照实时选取驱动节点，并使前后驱动节点尽量一致以降低切换代价。

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

VIDEO讲解视频

动态网络的自适应控制3 分 48 秒

文字稿

大家好，这次我们精读一篇发表在IEEE TNSE上的论文。它讨论的问题是，当网络本身在不断变化时，我们该怎样持续地控制它。这篇论文直接建立在最大匹配和驱动节点这套结构可控性理论之上。

邮件往来、人际接触，还有细胞里的分子相互作用，连边都在不停变化。已有的时序网络控制方法，大多假设整个演化过程事先就知道。但在真实场景里，我们在当下只能看到过去和现在的网络。而且每更换一个驱动节点，就意味着要把控制器搬个家，这是额外代价。

我们先回顾一下，最大匹配里没有匹配边指向的节点就是驱动节点。关键在于，同一个网络的最大匹配往往不止一个。不同的最大匹配给出大小相同、但成员不同的驱动节点集。这就给了我们选择的余地，可以挑一个和上一时刻最像的方案。比如上一时刻用的是节点a和b，这一时刻如果还能用a和b，就一个都不用换。

论文把动态网络看成一串快照，每个快照内部的拓扑固定。额外控制代价，就是相邻快照之间新加入的驱动节点个数，再对所有时刻求和。我们的目标是在每个时刻都保证可控的前提下，让这个代价尽量小。这是一个在线的组合优化问题，而且是NP难的，所以我们采用启发式方法。

第一条是稳定性原则，历史上连边多、连边变化少的节点更适合当驱动节点。第二条是一致性原则，尽量保留上一时刻已经在用的驱动节点。两者冲突时，我们让一致性优先，因为它直接决定要换掉多少节点。

稳定性由两部分相乘，一是节点前后两个快照边集的相似度，二是度中心性。把最近几个快照的稳定性加起来，就得到这个节点的累计稳定性。再加上一项，如果节点在上一时刻是驱动节点，就额外加上一个足够大的值。论文证明，这样设计后，上一时刻的驱动节点得分一定高于其他节点。

第一步，从上一时刻的最大匹配出发，删去已经不存在的匹配边。第二步，为当前快照里的每个节点计算自适应控制指标。第三步，按指标从小到大搜索增广路径，得分高的节点更可能留下来当驱动节点。

我们在1860个由ER和无标度模型生成的合成动态网络上做了测试。在重连比例低于0.1的相对稳定网络上，额外控制代价几乎减半。无标度网络上两种算法代价之比平均为0.72，ER网络上为0.84。在20个真实动态网络上平均比值是0.81，变化慢的网络能降到0.50。网络剧烈变化时，指标失效，算法退化成普通最大匹配，不会比基线更差。

要注意，这是启发式算法，论文也承认它还没有相对全局最优的近似界。代价只统计新增的驱动节点，没有区分不同节点的实际干预成本。大家可以联系脑网络中的动态功能连接，想想怎样在变化的网络上选刺激位点。读完论文后，请完成页面上的思考题，我们下次再见。

一句话看懂

网络在不断变化，每一时刻都要重新选驱动节点。由于最小驱动节点集往往不唯一，我们可以在“同样大小”的众多方案里，挑一个和上一时刻最像的方案，从而少换人、少花钱。这篇论文把这个想法形式化为自适应控制问题，并给出一个基于“部分匹配修复”的启发式算法 AC。

研究背景与问题

结构可控性与最大匹配中的结构可控性默认网络拓扑固定：用最大匹配求出最小驱动节点集（minimum driver node set, MDS），未被匹配边指向的节点就是驱动节点。但真实系统（邮件往来、人际接触、细胞内的分子相互作用）的连边随时间变化。

已有的时序网络控制方法大多有一个隐含前提：整个演化过程事先已知，于是可以离线找一个对所有时刻都适用的全局驱动节点集。论文指出，这个前提在多数真实网络中不成立，因为未来的结构变化是随机的、难以预测的。

于是问题变成：在时刻 $t$ ，只看得到快照 $G_1,\dots,G_t$ ，必须马上给出 $G_t$ 的一个 MDS，使它能控制当前网络；同时，前后两个 MDS 差别越小越好，因为每更换一个驱动节点，都意味着要把控制器“搬家”，产生额外代价。

核心思想与方法

问题形式化

动态网络建模为快照序列，每个快照内拓扑固定、可看作线性时不变系统 $\dot{x}=A_i x+B_i u$ 。目标是得到驱动节点集序列 $DS=\{D_1,D_2,\dots\}$ ，每个 $D_i$ 都必须是 $G_i$ 的某个 MDS。

额外控制代价（Extra Control Cost, ECC）：相邻快照之间新增驱动节点数之和 $\mathrm{ECC}=\sum_{i=2}^{T}|D_i-D_{i-1}|,$ 其中 $|D_i-D_{i-1}|$ 是属于当前 MDS、但不属于上一个 MDS 的节点数。自适应控制的目标是在每个 $D_i$ 都是合法 MDS 的约束下最小化 ECC。

论文说明这是一个在线组合优化问题，非凸且 NP 难，因此不追求全局最优，而是设计启发式方法。

小例子：网络 $a\to b$ 、 $a\to c$ 。最大匹配只能选一条边，所以 MDS 大小为 2，可以是 $\{a,b\}$ （匹配 $a\to c$ ）或 $\{a,c\}$ （匹配 $a\to b$ ）。如果上一时刻用的是 $\{a,b\}$ ，这一时刻就应优先仍选 $\{a,b\}$ ，ECC 为 0；若随手选了 $\{a,c\}$ ，ECC 就多 1。

两条原则与节点指标

稳定性原则：在历史快照中连边多、连边变化少的节点更“稳定”，优先选作驱动节点。
一致性原则：尽量沿用上一时刻的驱动节点。论文明确把一致性放在稳定性之前。

对节点 $v$ ，先算相邻快照边集的 Jaccard 相似度 $S_t(v)=\frac{|E_t(v)\cap E_{t-1}(v)|}{|E_t(v)\cup E_{t-1}(v)|}$ ，再乘以度中心性 $DC_t(v)\in[0,2]$ 得到 $\sigma_t(v)$ ，对最近 $l$ 个快照求和得稳定性 $stb_t(v)$ 。最终指标为 $q_v = 2l\cdot P_{t-1}(v) + stb_t(v),$ 其中 $P_{t-1}(v)$ 表示 $v$ 是否在上一时刻的 MDS 中。由于 $stb_t(v)\in[0,2l]$ ，论文证明（性质 1）：上一时刻的驱动节点的 $q$ 值一定大于非驱动节点——这就是“一致性优先”的数学保证。

AC 算法：部分匹配修复

从上一时刻的最大匹配中删去已经消失的匹配边，得到一个“部分匹配”；
计算每个节点的 $q$ ；
对未匹配节点按 $q$ 从小到大的顺序搜索增广路径，扩展匹配直到找不到增广路径。

直观上， $q$ 小的节点先被“匹配掉”， $q$ 大的节点更可能留作未匹配节点，也就是驱动节点。由于从旧匹配出发，网络只小改时修复工作量也小。若拓扑剧变导致指标失效，AC 退化为按随机顺序做最大匹配，与基线等价——论文称之为算法的性能下界。

主要发现

合成网络：共 1,860 个动态网络。SF 模型 31 个静态实例（10,000 个节点，平均度 2.0–8.0、步长 0.2，度指数 3），每个实例按 30 个重连比例 $r$ （0.01–0.30）生成 100 个快照，得 930 个；ER 模型同样 930 个。基线 MM 为对每个快照独立求 MDS 的最大匹配算法。AC 在全部参数下 $\mathrm{ECC}_{AC}/\mathrm{ECC}_{MM}<1$ ；在相对稳定的网络（ $r<0.1$ ）上 ECC 几乎减半。
网络类型差异：SF 网络平均比值 0.72，ER 网络 0.84。论文解释为 SF 网络的度异质性与“偏好稳定节点”的指标相契合。
密度的影响：ER 网络平均度为 2.0 时比值 0.63，平均度 8.0 时升至 0.85。原因是网络越稠密 MDS 越小，可选空间变窄。在 ER 网络上平均度小于 4 时，AC 在 95% 的快照上优于 MM；SF 网络平均度小于 6 时为 100%。ER 网络重连比例超过 0.50 后两者几乎相同。
真实网络：20 个真实动态网络（邮件、人际接触、社交网络）上平均比值 0.81；变化较慢的 email-Eu-core-temporal 与 contacts-prox-high-school-2013 为 0.50，而高度动态的 sx-superuser、edit-enwikibooks 上两者相近。11 个网络中 AC 在所有快照上都优于 MM，17 个网络中优于 MM 的快照超过 80%。比值与相邻快照的节点、边相似度呈负相关。摘要将其概括为合成网络平均降低切换代价 22%、真实网络 19%。
与其他偏好策略比较：在 121 个 1,000 节点 ER 动态网络上，与按度偏好（DPB）、按 PageRank 偏好（PPB）的匹配相比，四种方法 MDS 大小相同，但 AC 的驱动节点并集更小、ECC 更低。

怎样读这篇论文

先读引言与图 1、图 3：弄清“只知道过去”的设定，以及同一快照有多个 MDS 为什么能被利用。
再读第 III 节 ECC 定义和第 IV-B 节公式 (2) 与性质 1，这是全文的核心设计。
用图 4 的小例子手动走一遍算法 1，体会“旧匹配作为起点”和“搜索顺序”的作用。
实验部分重点看图 5（比值热图）、图 7（MDS 大小随平均度下降）、表 III 与图 9（相似度与性能的关系）。
相关工作中的表 I 可以快速浏览，用来定位本文与离线时序控制方法的区别。

局限与后续工作

启发式且无近似界：作者在结论中承认，AC 尚无相对于全局最优 ECC 的理论近似保证。
建模假设：仍是结构可控性框架，即线性动力学、权重“几乎任意”、快照内拓扑固定；ECC 只计新增驱动节点，没有区分不同节点的实际干预成本。
对剧烈变化无能为力：相似度很低时只能退回到基线水平，这是设计上的保守，而非优势。
与相关研究的关系：算法依赖“MDS 不唯一、可通过交替路径互换”这一事实，正是输入图与驱动节点枚举研究的基础（见驱动节点的枚举、分类与自适应控制）。双层网络控制研究（zheng2026_duplex）把“让两个驱动节点集尽量重叠”的思想从时间维度推广到层间维度。论文引言也把蛋白网络、癌症维持基因、COVID-19 药物等生物学应用列为动态控制的潜在场景，但本文实验本身没有使用生物数据。

关联知识

网络可控性与稳定性：最大匹配、最小输入定理、驱动节点不唯一，是本文的出发点；驱动节点的枚举、分类与自适应控制中有对本文的简述。
动态功能连接与多层脑网络：动态功能连接把脑网络看成随时间变化的快照序列，与本文的快照建模完全同构，可以思考在动态脑网络上做“少切换”的刺激位点选择。
度、平均度与密度：度中心性是本文节点稳定性指标的组成部分；读完可以思考为什么作者把“度大”等同于“稳定”，这个假设在生物网络中是否成立。

延伸思考

ECC 只统计新加入的驱动节点。如果离开驱动节点集也有成本（例如撤除电极），目标函数应如何修改？AC 的指标需要改动吗？
论文发现参数 $l$ 取不同值结果相近。这对“需要保存多少历史”有什么启示？在什么样的真实网络中你预计 $l$ 会变得重要？
设想用动态功能连接构造每个时间窗的脑网络并做自适应控制，你会如何检验“少切换”的方案在神经调控上是否真的更可行？
当相邻快照几乎完全不同时，AC 退化为基线。你能否设计一种利用“预测未来拓扑”的变体？它与本文“不依赖未来信息”的设定有什么冲突？