生物医学网络科学Biomedical Network Science
网络可控性与稳定性05 / 17

控制中心性与可控子空间

阅读
约 2 分钟

最小输入定理回答“控制全部节点需要几个输入”。反过来也可以问:如果只能驱动一个节点,它能控制多大一部分系统? 这对应可控子空间的维数,Liu、Slotine 与 Barabási(2012,PLoS ONE)称之为节点的控制中心性(control centrality)。

控制中心性:只在节点 ii 施加输入(B=𝒆iB=\mathbf e_i)时,可控性矩阵 𝒞(i)=[𝒆i,A𝒆i,…,AN−1𝒆i]\mathcal C(i)=[\mathbf e_i,A\mathbf e_i,\dots,A^{N-1}\mathbf e_i] 的通用秩(generic rank),即非零元取独立自由参数时对几乎所有取值都成立的秩: Cs(i)=rank⁡g𝒞(i).C_s(i)=\operatorname{rank}_g\,\mathcal C(i). Cs(i)=NC_s(i)=N 表示仅凭节点 ii 就能控制整个系统;Cs(i)=1C_s(i)=1 表示它只能控制自己。这一定义可以推广到一组节点。

图论计算(Hosoe 定理)。对所有状态节点都可达的结构系统,可控子空间的通用维数等于:在网络中用若干条互不相交的“茎”(从输入出发的有向路径)和有向环所能覆盖的最多边数(包括从输入指向驱动节点的那条边)——也就是寻找边数最多的“仙人掌”。由此得到两个实用结论:

  • 无环有向网络:从节点 ii 出发只有一条茎,控制中心性等于从 ii 出发的最长有向路径所含的节点数,即节点在层次结构中的层号。代码示例中的 8 节点无环网络,数值秩与最长路径一一对应。
  • 一般网络:可以转化为最大权环划分问题,用线性规划求解(Poljak 1990)。

前文星形例子中,中心节点的控制中心性为 2:一条茎只能沿一个叶子延伸。这也解释了为什么出度高不等于控制中心性高——一个输入只能沿一条不分叉的路径展开,再加上可以“挂”在路径上的环。在随机有向网络中,控制中心性与出度只有中等程度的相关(代码示例中 Spearman 相关约 0.6);Liu 等(2012)在真实网络中也发现控制中心性与度、介数等结构中心性并不一致,而与网络的层次结构关系更密切。

相关度量。Lo Iudice 等(2015)把问题反过来:给定 MM 个驱动节点,选择使可控子空间维数 |C(M)||C(M)| 最大的组合,并用 |C(M)||C(M)| 随 MM 的增长曲线定义网络的“渗透性”(permeability)。

控制中心性是结构度量,它只回答“能否独立影响这么多方向”,不回答“要花多少能量”。在脑网络等加权系统中,控制中心性往往等于 NN(几乎所有节点在理论上都能单独控制全脑),这时有区分力的是基于 Gramian 的定量指标,见控制能量与 Gramian 的数值问题和脑网络控制。