Optimizing network topology for average controllability

We address the problem of identifying a network topology of a networked system for maximizing a controllability measure, the average controllability under constraints on the number of links in the network. We consider networked systems consisting of subsystems with higher-order discrete-time linear time-invariant dynamics. We show that the average controllability is a monotone increasing supermodular function of a set of links in the networked system. Since maximizing such a function with cardinality constraints is an NP-hard problem, we analyze the performance guarantees obtained from the greedy algorithm for maximizing non-submodular set functions in terms of supermodular curvature. We show that the lower bound obtained for the greedy algorithm becomes trivial as the number of subsystems in the networked system increases. Hence, we propose two heuristic algorithms to solve the optimization problem and numerically demonstrate the efficiency of the proposed heuristics in terms of computational complexity and performance improvement in average controllability.