  A common approach to controlling complex networks is to directly control a
subset of input nodes, which then controls the remaining nodes via network
interactions. While techniques have been proposed for selecting input nodes
based on either performance metrics or controllability, a unifying approach
based on joint consideration of performance and controllability is an open
problem. In this paper, we develop a submodular optimization framework for
selecting input nodes based on joint performance and controllability in
structured linear descriptor systems. We develop our framework for arbitrary
linear descriptor systems. In developing our framework, we first prove that
selecting a minimum-size set of input nodes for controllability is a matroid
intersection problem that can be solved in polynomial-time in the network size.
We then prove that input selection to maximize a performance metric with
controllability as a constraint is equivalent to maximizing a monotone
submodular function with two matroid basis constraints, and derive efficient
approximation algorithms with provable optimality bounds for input selection.
Finally, we present a graph controllability index metric, which characterizes
the largest controllable subgraph of a given complex network, and prove its
submodular structure, leading to input selection algorithms that trade-off
performance and controllability. We provide improved optimality guarantees for
known systems such as strongly connected networks, consensus networks, networks
of double integrators, and networks where all system parameters (e.g., link
weights) are chosen independently and at random.
