Sufficient control of complex networks

Abstract

In this paper, we propose to study sufficient control of complex networks, which is to control a sufficiently large portion of the network, where only the quantity of controllable nodes matters. To the best of our knowledge, this is the first time that such a problem is investigated. We prove that the sufficient controllability problem can be converted into a minimum-cost flow problem, for which an algorithm with polynomial complexity can be devised. Further, we study the problem of minimum-cost sufficient control, which is to drive a sufficiently large subset of the network nodes to any predefined state with the minimum cost using a given number of controllers. The problem is NP-hard. We propose an “extended L0-norm-constraint-based Projected Gradient Method” (eLPGM) algorithm, which achieves suboptimal solutions for the problems at small or medium sizes. To tackle the large-scale problems, we propose to convert the control problem into a graph problem and devise an efficient low-complexity “Evenly Divided Control Paths” (EDCP) algorithm to tackle the graph problem. Simulation results on both synthetic and real-life networks are provided, demonstrating the satisfactory performance of the proposed methods.