# On Submodularity and Controllability in Complex Dynamical Networks

arXiv: https://arxiv.org/abs/1404.7665 · HTML: https://mlsanity.com/paper/1404.7665/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Apr 2014.

## Built on by (most cited first, 10 of 10)

- [Beyond Robustness: A Taxonomy of Approaches towards Resilient Multi-Robot Systems](https://mlsanity.com/paper/2109.12343/) (2021)
- [Greedy-Based Feature Selection for Efficient LiDAR SLAM](https://mlsanity.com/paper/2103.13090/) (2021)
- [Maximum diffusion reinforcement learning](https://mlsanity.com/paper/2309.15293/) (2023)
- [PySensors: A Python Package for Sparse Sensor Placement](https://mlsanity.com/paper/2102.13476/) (2021)
- [Communication Topology Co-Design in Graph Recurrent Neural Network Based Distributed Control](https://mlsanity.com/paper/2104.13868/) (2021)
- [Constrained optimization of sensor placement for nuclear digital twins](https://mlsanity.com/paper/2306.13637/) (2023)
- [Inadequacy of Linear Methods for Minimal Sensor Placement and Feature Selection in Nonlinear Systems; a New Approach Using Secants](https://mlsanity.com/paper/2101.11162/) (2021)
- [Control-based Graph Embeddings with Data Augmentation for Contrastive Learning](https://mlsanity.com/paper/2403.04923/) (2024)
- [Demarcating Endogenous and Exogenous Opinion Dynamics: An Experimental Design Approach](https://mlsanity.com/paper/2102.05954/) (2021)
- [Controllability of Coarsely Measured Networked Linear Dynamical Systems (Extended Version)](https://mlsanity.com/paper/2206.10569/) (2022)

## Abstract (arXiv)

Controllability and observability have long been recognized as fundamental structural properties of dynamical systems, but have recently seen renewed interest in the context of large, complex networks of dynamical systems. A basic problem is sensor and actuator placement: choose a subset from a finite set of possible placements to optimize some real-valued controllability and observability metrics of the network. Surprisingly little is known about the structure of such combinatorial optimization problems. In this paper, we show that several important classes of metrics based on the controllability and observability Gramians have a strong structural property that allows for either efficient global optimization or an approximation guarantee by using a simple greedy heuristic for their maximization. In particular, the mapping from possible placements to several scalar functions of the associated Gramian is either a modular or submodular set function. The results are illustrated on randomly generated systems and on a problem of power electronic actuator placement in a model of the European power grid.