A Networked system consists of a large number of subsystems interconnected through a network. Examples of networked systems include power grids, robot swarms, social networks, to name a few. In complex networks, even though a network might be theoretically controllable, it is often not controllable in practice, for example, the system may require an unreasonable amount of energy required to steer the system in certain directions. Based on controllability gramian, several energy related metrics have been proposed in the literature.

In our work, we choose the trace of a gramian, termed as average controllability in all directions in state space, as a measure of controllability. Due to physical constraints, there exist limitations on the number of interconnection links across subsystems in the networked system. Hence, we consider the problem of the design of network topology that maximizes the average controllability when there is a constraint on the number of links across subsystems in the networked system, which is formulated as a set function optimization problem. We show that the problem is NP-hard. We analyze the performance bounds obtained for a greedy algorithm in terms of supermodular curvature, which quantifies how far a set function is from being modular. We show that the supermodular curvature, for this problem tends to 1 as the number of subsystems increases. Hence, the bounds obtained for this problem becomes trivial. We propose few heuristics and numerically demonstrate the efficiency of the proposed heuristics and the greedy algorithm in terms of computational complexity and performance improvement.