Target Controllability of Complex Networks Based on Greedy Optimization
Jie Ding, Yue Zhuo, Xiaole Hu, Yan Ming Zhao, Cong Li, Xiang Li · IEEE Transactions on Control of Network Systems · 2025
Controlling large complex networks is a common and important problem. In the field of network control, controlling target nodes has higher efficiency and feasibility than controlling all nodes to achieve the desired functionality for a network system. This paper revisits target controllability problem and theoretically proves that it is NP-hard by reduction from 3-dimensional matching. Moreover, four greedy algorithms are proposed. Three of them follow the order of in-degree, the order of out-degree and the order of degree for the maximum matching during iterations respectively. The other algorithm uses an updated matching order based on in-degree as well as frequency, which reflects the times that the nodes are matched in previous iterations. Simulations on synthetic networks, as well as real-world networks are carried out, which illustrate satisfactory performance of the proposed algorithm using an updated matching order. The results in the paper provide valuable insights into the efficient control of complex networks in real-world applications.