复杂网络的结构可控性与可预测性

复杂网络的结构可控性[1, 2]是线性系统控制的一种简化普适版本，意指对一类链路权重可调的线性系统的控制可行性分析。结构可控性中最经典的最小输入定理指出，对有向网络中结构可控的最小驱动节点集的搜索等价于对有向网络最大匹配链路集合的搜索。结构控制理论将复杂的动力学机制归结为简单的拓扑机制，实现了网络结构与网络功能的有机结合。

复杂网络的结构可预测作为复杂网络的另一种典型的功能应用，则致力于评估链路存在的“合理性”，即可预测性。我们在利用链路进行结构控制的鲁棒性分析时发现：严重影响结构可控的最小驱动节点集规模的“临界链路”，具有极低的可预测性；而其它的“一般链路”则具有相对较高的可预测性（见图1）。这一现象被我们命名为“结构协调性”[3]，其广泛存在于真实世界中，尽管偶有反例（见图1B）。

图 1 真实网络上普遍存在的结构协调性现象

进一步地，为了理解并解释这一现象，我们首先从理论出发，推导出

（1）在结构可控性理论中，临界链路偏好于位于边缘区域的链路，原因是在leave-one-out的鲁棒性分析中，对最小驱动节点集扰动更大的临界链路更倾向于临近边缘节点的链路：

其中表示网络最小驱动节点数的波动。

（2）在结构可预测性中，基于CN、PA等多种算法的可预测性则偏好于位于中心区域的链路，原因是在leave-one-out的鲁棒性分析中，中心性得分更高的链路的可预测性也更高：

理论分析向我们揭示了，网络的核心-边缘结构或许是结构协调性现象的根源，因此我们需要进行链路中心性测度，此处可以通过线图将节点中心性测度转化为链路中心性测度（见图2）。

图 2 线图转化与链路中心性测度。

而对真实网络的链路中心性测度的分析，向我们揭示了网络的结构协调性是否显著取决于临界链路是否倾向于网络的核心区域：

图 3 基于四种不同的链路中心性测度：一般链路VS临界链路

至此得到最终结论：结构协调性现象广泛存在于真实世界中，在结构可控性和可预测性这两大网络功能性之间建立了联系。结构可预测性帮助解释了线性控制系统的鲁棒性中，临界链路的重要性（其缺失不仅造成严重后果，而且难以复原）；而临界链路存在本身也成为了结构可预测性亟待攻克的一大难题，将对后续的算法开发与优化产生一定的借鉴意义。

参 考 文 献 :

[1].   Lin, C.T., Structural controllability. IEEE Transactions on Automatic Control, 1974. AC19(3): p. 201-208.

[2].   Liu, Y., J. Slotine and A. Barabási, Controllability of complex networks. Nature, 2011. 473(7346): p. 167-173.

[3] Fei Jing, Chang Liu, Jian-Liang Wu, Zi-Ke Zhang. Toward structural controllability and predictability in directed networks, IEEE Transactions on Systems, Man, and Cybernetics: Systems, Early Access, doi: 10.1109/TSMC.2022.3161408.

论文下载网址：https://ieeexplore.ieee.org/document/9748894