Submodularity in Input Node Selection for Networked Linear Systems: Efficient Algorithms for Performance and Controllability

Networked systems are systems of interconnected components in which the dynamics of each component (often referred to as a node or agent) are influenced by the behavior of neighboring components. Examples of networked systems include biological networks, ranging in scale from the gene interactions within a single cell to food webs of an entire ecosystem, and critical infrastructures such as power grids, transportation systems, the Internet, and social networks. The growing importance of such systems has led to an interest in the control of networks to ensure performance, stability, robustness, and resilience [1]-[4]. Indeed, over the past several decades, a variety of control-theoretic methods has been employed to better understand and control networked systems [5]. Moreover, new subdisciplines of control theory have emerged, including networked control systems (where plants, sensors, and actuators are connected by communication networks) and control of cyberphysical systems [6]-[8].