Passivity-Based Distributed Strategies for Stochastic Stackelberg Security Games
From MaRDI portal
Publication:3455892
DOI10.1007/978-3-319-25594-1_7zbMATH Open1453.91019arXiv1412.3868OpenAlexW2275740409MaRDI QIDQ3455892
Author name not available (Why is that?)
Publication date: 11 December 2015
Published in: (Search for Journal in Brave)
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/1412.3868
No records found.
No records found.
This page was built for publication: Passivity-Based Distributed Strategies for Stochastic Stackelberg Security Games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3455892)
