On Submodularity and Controllability in Complex Dynamical Networks
Open accessThe DOI matches its Crossref record; 40 of the 40 references it cites were found in a registry or an index.
Abstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Power System Stability and Control
Kundur, P. (1994) · Cited by 19,639
Maximizing the spread of influence through a social network
Kempe, D., Kleinberg, J., & Tardos, É. (2003) · Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/956750.956769 · Cited by 7,326
Newman, M. (2010) · doi:10.1093/acprof:oso/9780199206650.001.0001 · Cited by 6,595
An analysis of approximations for maximizing submodular set functions—I
Nemhauser, G. L., Wolsey, L. A., & Fisher, M. L. (1978) · Mathematical Programming · doi:10.1007/bf01588971 · Cited by 4,412
Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images
Boykov, Y. Y., & Jolly, M.-P. (2002) · Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001 · doi:10.1109/iccv.2001.937505 · Cited by 3,674
Controllability of complex networks
Liu, Y.-Y., Slotine, J.-J., & Barabási, A.-L. (2011) · Nature · doi:10.1038/nature10011 · Cited by 3,215
A threshold of ln n for approximating set cover
Feige, U. (1998) · Journal of the ACM · doi:10.1145/285055.285059 · Cited by 3,086
(2011) · Choice Reviews Online · doi:10.5860/choice.48-3328 · Cited by 2,736
Algorithm 432 [C2]: Solution of the matrix equation AX + XB = C [F4]
Bartels, R. H., & Stewart, G. W. (1972) · Communications of the ACM · doi:10.1145/361573.361582 · Cited by 1,932
Contributions to the theory of optimal control
Kalman, R. E. (1960) · Cited by 1,730
Petersen, K. B., & Pedersen, M. S. (2012) · doi:10.5281/zenodo.8002926 · Cited by 1,434
Lin, C.-T. (1974) · IEEE Transactions on Automatic Control · doi:10.1109/tac.1974.1100557 · Cited by 1,397
On the general theory of control systems
Kalman, R. E. (1960) · IFAC Proceedings Volumes · doi:10.1016/s1474-6670(17)70094-8 · Cited by 1,222
Maximizing the spread of influence through a social network
Kempe, D., Kleinberg, J. M., & Tardos, É. (2003) · ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/956755.956769 · Cited by 1,034
Submodular functions and convexity
Lovász, L. (1983) · Mathematical Programming The State of the Art · doi:10.1007/978-3-642-68874-4_10 · Cited by 964
KrauseAndreas, SinghAjit, & GuestrinCarlos (2008) · Journal of Machine Learning Research · doi:10.5555/1390681.1390689 · Cited by 815
Controllability of Multi-Agent Systems from a Graph-Theoretic Perspective
Rahmani, A., Ji, M., Mesbahi, M., & Egerstedt, M. (2009) · SIAM Journal on Control and Optimization · doi:10.1137/060674909 · Cited by 767
Submodular Function Maximization
Krause, A., & Golovin, D. (2014) · Tractability · doi:10.1017/cbo9781139177801.004 · Cited by 751
Controllability Metrics, Limitations and Algorithms for Complex Networks
Pasqualetti, F., Zampieri, S., & Bullo, F. (2014) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2014.2310254 · Cited by 594
Controllability of complex networks via pinning
Sorrentino, F., di Bernardo, M., Garofalo, F., & Chen, G. (2007) · Physical Review E · doi:10.1103/physreve.75.046103 · Cited by 439
Controlling edge dynamics in complex networks
Nepusz, T., & Vicsek, T. (2012) · Nature Physics · doi:10.1038/nphys2327 · Cited by 430
Controlling Complex Networks: How Much Energy Is Needed?
Yan, G., Ren, J., Lai, Y.-C., Lai, C.-H., & Li, B. (2012) · Physical Review Letters · doi:10.1103/physrevlett.108.218703 · Cited by 413
Accelerated greedy algorithms for maximizing submodular set functions
Minoux, M. (2005) · Springer eBooks · doi:10.1007/bfb0006528 · Cited by 411
On the general theory of control systems
Kalman, R. (1959) · IRE Transactions on Automatic Control · doi:10.1109/tac.1959.1104873 · Cited by 392
Low Rank Solution of Lyapunov Equations
Li, J., & White, J. (2002) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479801384937 · Cited by 333
Minimal Controllability Problems
Olshevsky, A. (2014) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2014.2337974 · Cited by 322
Cowan, N. J., Chastain, E. J., Vilhena, D. A., Freudenberg, J. S., & Bergstrom, C. T. (2012) · PLoS ONE · doi:10.1371/journal.pone.0038398 · Cited by 273
Optimizing controllability of complex networks by minimum structural perturbations
Wang, W.-X., Ni, X., Lai, Y.-C., & Grebogi, C. (2012) · Physical Review E · doi:10.1103/physreve.85.026115 · Cited by 246
Controllability Transition and Nonlocality in Network Control
Sun, J., & Motter, A. E. (2013) · Physical Review Letters · doi:10.1103/physrevlett.110.208701 · Cited by 192
Evolutionary Pinning Control and Its Application in UAV Coordination
Tang, Y. S., Gao, H., Kurths, J., & Fang, J. (2012) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2012.2187911 · Cited by 154
Clark, A., Bushnell, L. G., & Poovendran, R. (2013) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2013.2281473 · Cited by 148
Numerical Solution of the Stable, Non-negative Definite Lyapunov Equation
Hammarling, S. J. (2005) · Cited by 142
Optimal Sensor and Actuator Placement in Complex Dynamical Networks
Summers, T. H., & Lygeros, J. (2014) · IFAC Proceedings Volumes · doi:10.3182/20140824-6-za-1003.00226 · Cited by 122
Self-citationFew inputs can reprogram biological networks
Müller, F.-J., & Schuppert, A. (2011) · Nature · doi:10.1038/nature10543 · Cited by 109
Dynamics and control of state-dependent networks for probing genomic organization
Rajapakse, I., Groudine, M. T., & Mesbahi, M. (2011) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1113249108 · Cited by 74
A submodular optimization framework for leader selection in linear multi-agent systems
Clark, A., & Poovendran, R. (2011) · doi:10.1109/cdc.2011.6160248 · Cited by 58
On leader selection for performance and controllability in multi-agent systems
Clark, A., Bushnell, L. G., & Poovendran, R. (2012) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2012.6426973 · Cited by 52
Semi-Autonomous Consensus: Network Measures and Adaptive Trees
Chapman, A., & Mesbahi, M. (2012) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2012.2205429 · Cited by 49
Rigid Network Design Via Submodular Set Function Optimization
Shames, I., & Summers, T. H. (2015) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2015.2480247 · Cited by 30
Self-citationSystem Theoretic Aspects of Influenced Consensus: Single Input Case
Chapman, A., & Mesbahi, M. (2011) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2011.2179345 · Cited by 14
Cited by
A Survey on Aerial Swarm Robotics
Chung, S.-J., Paranjape, A. A., Dames, P., Shen, S., & Kumar, V. (2018) · IEEE Transactions on Robotics · doi:10.1109/tro.2018.2857475 · Cited by 672
Control principles of complex systems
Liu, Y.-Y., & Barabási, A.-L. (2016) · Reviews of Modern Physics · doi:10.1103/revmodphys.88.035006 · Cited by 654
Spectrum of controlling and observing complex networks
Yan, G., Tsekenis, G., Barzel, B., Slotine, J.-J., Liu, Y.-Y., & Barabási, A.-L. (2015) · Nature Physics · doi:10.1038/nphys3422 · Cited by 279
Dynamic causal brain circuits during working memory and their functional controllability
Cai, W., Ryali, S., Pasumarthy, R., Talasila, V., & Menon, V. (2021) · Nature Communications · doi:10.1038/s41467-021-23509-x · Cited by 105
A control theoretic approach to evaluate and inform ecological momentary interventions
Fechtelpeter, J., Rauschenberg, C., Jamalabadi, H., Boecking, B., van Amelsvoort, T., Reininghaus, U., Durstewitz, D., & Koppe, G. (2023) · doi:10.31234/osf.io/97teh · Cited by 16
“It is assessed here via the so - called controllability Gramian W T as with T ¼ M (Pasqualetti et al., 2014; Summers et al., 2015).”
Method
Metadata
- Authors
- Summers, T. H., Cortesi, F. L., & Lygeros, J.
- Venue
- IEEE Transactions on Control of Network Systems
- Published
- 2016-03
- Volume
- 3
- Issue
- 1
- Pages
- 91-101
- ISSN
- 2325-5870 (ISSN-L)
- OpenAlex
- W1938602245
- Cited by
- 482
- References
- 40
- FWCI
- 34.64
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.