Control of complex networks, including unmanned vehicle networks, social networks, and biological systems, is an ever-growing challenge. A standard approach is to directly control a subset of leader nodes, which then influence the remaining (follower) nodes. While the choice of leader nodes is known to impact the performance, controllability, and security of complex networks, efficient algorithms for selecting optimal leaders are currently lacking. In this talk, we give an overview of our ongoing work on leader selection in complex networks. We focus on three design criteria, namely, the robustness of the system to noise in the links between nodes, the time for the follower nodes to converge to their desired state, and the controllability to the follower nodes from the leader nodes. We present a unifying framework based on submodularity, a diminishing returns property analogous to concavity of real-valued functions, for studying each of these criteria. Our framework enables efficient leader selection based on the criteria above, with provable guarantees on the resulting system performance. Moreover, we generalize our approach to time-varying networks, including networks with random failures, arbitrary topology variations due to node mobility, and attacks by an intelligent adversary targeting one or more links.
