In this paper, we study the relationship between two crucial properties in linear dynamical networks of diffusively coupled agents, that is controllability and robustness to noise and structural changes in the network. In particular, for any given network size and diameter, we identify networks that are maximally robust and then analyze their strong structural controllability. We do so by determining the minimum number of leaders to make such networks completely controllable with arbitrary coupling weights between agents. Similarly, we design networks with the same given parameters that are completely controllable independent of coupling weights through a minimum number of leaders, and then also analyze their robustness. We utilize the notion of Kirchhoff index to measure network robustness to noise and structural changes. Our controllability analysis is based on novel graph-theoretic methods that offer insights on the important connection between network robustness and strong structural controllability in such networks.
To quantify controllability, several approaches have been adapted, including determining the minimum number of inputs (leader nodes) needed to (structurally or strong structurally) control a network, determining the worst-case control energy, metrics based on controllability Gramians, and so on (e.g., see @cite_7 @cite_5 ). Strong structural controllability, due to its independence on coupling weights between nodes, is a generalized notion of controllability with practical implications. There have been recent studies providing graph-theoretic characterizations of this concept @cite_20 @cite_13 @cite_17 . There are numerous other studies regarding leader selection to optimize network performance measures under various constraints, such as to minimize the deviation from consensus in a noisy environment @cite_4 @cite_2 , and to maximize various controllability measures, for instance @cite_15 @cite_18 @cite_25 @cite_14 . Recently, optimization methods are also presented to select leader nodes that exploit submodularity properties of performance measures for network robustness and structural controllability @cite_5 @cite_3 .
@cite_18 @cite_14 @cite_4 @cite_7 @cite_3 @cite_2 @cite_5 @cite_15 @cite_13 @cite_25 @cite_20 @cite_17
2111725629 1938602245 2315383458 2049708951 2763583074
This paper studies the problem of controlling complex networks, i.e., the joint problem of selecting a set of control nodes and of designing a control input to steer a network to a target state. For this problem, 1) we propose a metric to quantify the difficulty of the control problem as a function of the required control energy, 2) we derive bounds based on the system dynamics (network topology and weights) to characterize the tradeoff between the control energy and the number of control nodes, and 3) we propose an open-loop control strategy with performance guarantees. In our strategy, we select control nodes by relying on network partitioning, and we design the control input by leveraging optimal and distributed control techniques. Our findings show several control limitations and properties. For instance, for Schur stable and symmetric networks: 1) if the number of control nodes is constant, then the control energy increases exponentially with the number of network nodes; 2) if the number of control nodes is a fixed fraction of the network nodes, then certain networks can be controlled with constant energy independently of the network dimension; and 3) clustered networks may be easier to control because, for sufficiently many control nodes, the control energy depends only on the controllability properties of the clusters and on their coupling strength. We validate our results with examples from power networks, social networks and epidemics spreading. 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. In this technical note, we study the controllability of diffusively coupled networks from a graph theoretic perspective. We consider leader-follower networks, where the external control inputs are injected to only some of the agents, namely the leaders. Our main result relates the controllability of such systems to the graph distances between the agents. More specifically, we present a graph topological lower bound on the rank of the controllability matrix. This lower bound is tight, and it is applicable to systems with arbitrary network topologies, coupling weights, and number of leaders. An algorithm for computing the lower bound is also provided. Furthermore, as a prominent application, we present how the proposed bound can be utilized to select a minimal set of leaders for achieving controllability, even when the coupling weights are unknown. This paper examines strong structural controllability of linear-time-invariant networked systems. We provide necessary and sufficient conditions for strong structural controllability involving constrained matchings over the bipartite graph representation of the network. An O(n2) algorithm to validate if a set of inputs leads to a strongly structurally controllable network and to find such an input set is proposed. The problem of finding such a set with minimal cardinality is shown to be NP-complete. Minimal cardinality results for strong and weak structural controllability are compared. Characterization of network controllability through its topology has recently gained a lot of attention in the systems and control community. Using the notion of balancing sets, in this note, such a network-centric approach for the controllability of certain families of undirected networks is investigated. Moreover, by introducing the notion of a generalized zero forcing set, the structural controllability of undirected networks is discussed; in this direction, lower bounds on the dimension of the controllable subspace are derived. In addition, a method is proposed that facilitates synthesis of structural and strong structural controllable networks as well as examining preservation of network controllability under structural perturbations.