L₀ norm constraint based external control source allocation for the minimum cost control of directed networks

Locating a pre-given number of key nodes that are connected to external control sources so as to minimize the cost of controlling a directed network ẋ(t)=Ax(t)+Bu(t), known as the minimum cost control problem, is of critical importance. Considering a network consisting of N nodes with M external control sources, the state of art techniques employ iterative searching to determine the input matrix B that characterizes how nodes are connected to external control sources, in a matrix space R^N×M. The nodes having M largest values of a defined importance index are selected as key nodes. However, such techniques may suffer from large performance penalty in some networks due to the diversity of real-life networks. To address this outstanding issue, we propose an iterative method, termed "L₀-norm constraint based projected gradient method" (LPGM). We probabilistically search the input matrix in each iteration by restricting its L₀ norm as a fixed value M, which implies that each control source is always only connected to a single key node during the whole searching process. Simulation results show that the solution always efficiently approaches a suboptimal key node set in a few iterations. These results provide a new point of view regarding the key nodes selection in the minimum cost control of directed networks.