基于大规模网络的结构能控性指数算法*

东华大学信息科学与技术学院 曾涛 李晓丽

传统的网络能控性是在给定输入下通过能控性判据来判断该网络是否可控，或是寻找使有向网络达到可控时的最少驱动节点集。为了研究网络达到可控时的链路长度，对于一个没有给定输入的有向网络，本文通过对节点度的研究和删除边等操作将有向网络分解成多条控制链，将控制链的根节点作为整个网络的驱动节点集。同时引入能控性指数的概念，对控制链长度进行研究。最后基于节点的度提出了一个算法将有向网络分解成独立可控的控制链,得出网络的驱动节点集和结构能控性指数，通过对大规模随机网络和真实网络的仿真，验证了算法的有效性。

现代网络科学中最具挑战性的问题之一是对复杂网络的控制。由于复杂网络具有高维度、非线性等特征，许多研究人员致力于了解复杂网络的结构以及节点间的相互作用，但是目前还有特定的框架来解决网络拓扑结构和非线性动力学之间的极其复杂的相互作用问题，因此复杂网络的控制依旧是一个复杂的问题。

Liu等人作出了开创性的贡献。提出了最小输入定理来有效地表征有向网络的结构可控性，通过识别最少驱动节点集以实现网络的完全控制。在此基础上将有向网络的结构可控性映射到最大匹配的问题上，通过给不匹配的控制节点施加控制使网络可控。但是，最大匹配并不是唯一的，所以在最大匹配的基础上提出了一个算法用于查找所有可能的输入节点使复杂网络可控。……