有向网络能控性指数的上下界研究

Research on upper and lower bounds of controllability index for directed networks

摘要:

研究网络可控性的重要前提是证明系统是可控的.网络的可控性是指通过施加适当的外部输入或者调节输入来控制整个网络,从而获得预期的状态.传统计算有向网络控制输入节点的方法是通过求解网络对应的二分图的最大匹配,由于这种方法对于网络节点的匹配方式没有施加限制,导致节点控制链路过长,造成网络控制信息传递存在延迟,影响网络的可控性性能.通过Kalman判据、PBH判据等可证明一定时间内系统是否可控,但是随着网络规模的增大,网络中节点之间的关系也变得更加复杂,单纯使用这类方法使得运算的复杂度变高.本文首先结合Kalman秩判据提出能控性指数K的下界算法(KMLA).通过确定网络达到可控状态时的能控性指数的下界,可以快速确定控制输入的控制节点集群.然后提出基于入度的能控性指数K的最小上界算法(KMUA).发现本文提出的KMUA算法能够使K值的上界更加接近网络达到步可控时的K值.结合具体的网络模型和实际的网络对能控性指数的上下界进行验证,结果表明本文提出的算法,结合能控性指数上下界,可优化节点的控制链长度.

Abstract:

An important prerequisite for the study of network controllability is to prove that the system is controllable. The controllability of the network means that the entire network is controlled by applying proper external inputs or adjusting inputs to achieve the desired state. The traditional way to calculate the control input nodes of directed network is to solve the maximum matching of the bipartite graphs corresponding to the network. However, since this method does not impose restrictions on the matching manner of the network node, the node control chain is too long and the information transfer of the control input is delayed, which affects the whole controllable performance of the network. The Kalman criterion and the PBH criterion can prove whether the system is controllable within a certain period of time. However, the relationship between nodes in the network becomes more complicated as the size of the network increases, so the simple utilization of such methods increases the complexity of the operation. Therefore, the lower bound algorithm for the controllability index K (KMLA) was proposed by combining the Kalman rank criterion. Control node cluster for control input can be quickly determined by determining the lower bound of the network’s controllability index. Then based on in-degree of networks, the minimum upper bound algorithm for the controllability index K (KMUA) was proposed. It was found that the KMUA algorithm proposed in this paper could make the upper bound of the K value closer to the K value when the network reached the K-step controllable. The upper and lower bounds of the controllability index K were verified by the specific network model and the real network. Results show that the algorithm can optimize the control chain length of the driven node by combining the upper and lower bounds of the controllability index.