Search

In a network consisting of n nodes, our goal is to identify the most central k nodes with respect to the proposed definitions of centrality. Depending on the specific application, there exist several metrics for quantifying k-centrality, and the subset of the best k nodes naturally varies based on the chosen metric. In this paper, we propose two metrics and establish connections to a well-studied metric from the literature (specifically for stochastic matrices). We prove these three notions match for path graphs. We then list a few more control-theoretic notions and compare these various notions for a general randomly generated graph. Our first metric involves maximizing the shift in the smallest eigenvalue of the Laplacian matrix. This shift can be interpreted as an improvement in the time constant when the RC circuit experiences leakage at certain k capacitors. The second metric focuses on minimizing the Perron root of a principal sub-matrix of a stochastic matrix, an idea proposed and interpreted in the literature as manufacturing consent. The third one explores minimizing the Perron root of a perturbed (now super-stochastic) matrix, which can be seen as minimizing the impact of added stubbornness. It is important to emphasize that we consider applications (for example, facility location) when the notions of central ports are such that the set of the best k ports does not necessarily contain the set of the best k-1 ports. We apply our k-port selection metric to various network structures. Notably, we prove the equivalence of three definitions for a path graph and extend the concept of central port linkage beyond Fiedler vectors to other eigenvectors associated with path graphs.

Algebraic connectivity is one way to quantify graph connectivity, which in turn gauges robustness as a network. In this paper, we consider the problem of maximising algebraic connectivity both local and globally over all simple, undirected, unweighted graphs with a given number of vertices and edges. We pursue this optimization by equivalently minimizing the largest eigenvalue of the Laplacian of the 'complement graph'. We establish that the union of complete subgraphs are largest eigenvalue "local" minimizer graphs. Further, under sufficient conditions satisfied by the edge/vertex counts we prove that this union of complete components graphs are, in fact, Laplacian largest eigenvalue "global" maximizers; these results generalize the ones in the literature that are for just two components. These sufficient conditions can be viewed as quantifying situations where the component sizes are either 'quite homogeneous' or some of them are relatively 'negligibly small', and thus generalize known results of homogeneity of components. We finally relate this optimization with the Discrete Fourier Transform (DFT) and circulant graphs/matrices., Comment: 21 pages, 8 figures

SISO passive systems with just one type of memory/storage element (either only inductive or only capacitative) are known to have real poles and zeros, and further, with the zeros interlacing poles (ZIP). Due to a variety of definitions of the notion of a system zero, and due to other reasons described in the paper, results involving ZIP have not been extended to MIMO systems. This paper formulates conditions under which MIMO systems too have interlaced poles and zeros. This paper next focusses on the notion of a `spectral zero' of a system, which has been well-studied in various contexts: for example, spectral factorization, optimal charging/discharging of a dissipative system, and even model order reduction. We formulate conditions under which the spectral zeros of a MIMO system are real, and further, conditions that guarantee that the system-zeros, spectral zeros, and the poles are all interlaced. The techniques used in the proofs involve new results in Algebraic Riccati equations (ARE) and Hamiltonian matrices, and these results help in formulating new notions of positive-real balancing, and inter-relations with the existing notion of positive-real balancing; we also relate the positive-real singular values with the eigenvalues of the extremal ARE solutions in the proposed `quasi-balanced' forms.

In this paper, we study structural controllability of a linear time invariant (LTI) composite system consisting of several subsystems. We assume that the neighbourhood of each subsystem is unconstrained, i.e., any subsystem can interact with any other subsystem. The interaction links between subsystems are referred as interconnections. We assume the composite system to be structurally controllable if all possible interconnections are present, and our objective is to identify the minimum set of interconnections required to keep the system structurally controllable. We consider structurally identical subsystems, i.e., the zero/non-zero pattern of the state matrices of the subsystems are the same, but dynamics can be different. We present a polynomial time optimal algorithm to identify the minimum cardinality set of interconnections that subsystems must establish to make the composite system structurally controllable.

This paper deals with a complete bipartite matching problem with the objective of finding an optimal matching that maximizes a certain generic predefined utility function on the set of all matchings. After proving the NP-hardness of the problem using reduction from the 3-SAT problem, we propose a randomized algorithm based on Markov Chain Monte Carlo (MCMC) technique for solving this. We sample from Gibb's distribution and construct a reversible positive recurrent discrete time Markov chain (DTMC) that has the steady state distribution same as the Gibb's distribution. In one of our key contributions, we show that the constructed chain is `rapid mixing', i.e., the convergence time to reach within a specified distance to the desired distribution is polynomial in the problem size. The rapid mixing property is established by obtaining a lower bound on the conductance of the DTMC graph and this result is of independent interest.

This paper solves the sparsest feedback selection problem for linear time invariant structured systems, a long-standing open problem in structured systems. We consider structurally cyclic systems with dedicated inputs and outputs. We prove that finding a sparsest feedback selection is of linear complexity for the case of structurally cyclic systems with dedicated inputs and outputs. This problem has received attention recently but key errors in the hardness-proofs have resulted in an erroneous conclusion there. This is also elaborated in this brief paper together with a counter-example., Comment: 5 pages, 2 figures

This paper addresses optimal feedback selection for generic arbitrary pole placement of structured systems when each feedback edge is associated with a cost. Given a structured system and a feedback cost matrix, our aim is to find a feasible feedback matrix of minimum cost that guarantees arbitrary pole placement of the closed-loop structured system. We first give a polynomial time reduction of the weighted set cover problem to an instance of the feedback selection problem and thereby show that the problem is NP-hard. Then we prove the inapproximability of the problem by showing that constant factor approximation for the problem does not exist unless the set cover problem can be approximated within a constant factor. Since the problem is hard, we study a subclass of systems whose directed acyclic graph constructed using the strongly connected components of the state digraph is a line graph and the state bipartite graph has a perfect matching. We propose a polynomial time optimal algorithm based on dynamic programming for solving the problem on this class of systems. Further, over the same class of systems we relax the perfect matching assumption, and provide a polynomial time 2-optimal solution based on dynamic programming and a minimum cost perfect matching algorithm., Comment: 10 Pages, 4 Figures

This paper is about minimum cost constrained selection of inputs and outputs for generic arbitrary pole placement. The input-output set is constrained in the sense that the set of states that each input can influence and the set of states that each output can sense is pre-specified. Our goal is to optimally select an input-output set that the system has no structurally fixed modes. Polynomial algorithms do not exist for solving this problem unless P=NP. To this end, we propose an approximation algorithm by splitting the problem in to three sub-problems: a) minimum cost accessibility problem, b) minimum cost sensability problem and c) minimum cost disjoint cycle problem. We prove that problems a) and b) are equivalent to a suitably defined weighted set cover problems. We also show that problem c) is equivalent to a minimum cost perfect matching problem. Using these we give an approximation algorithm which solves the minimum cost generic arbitrary pole placement problem. The proposed algorithm incorporates an approximation algorithm to solve the weighted set cover problem for solving a) and b) and a minimum cost perfect matching algorithm to solve c). Further, we show that the algorithm is polynomial time an gives an order optimal solution to the minimum cost input-output selection for generic arbitrary pole placement problem., Comment: 11 pages, 2 figures

This paper looks at two problems, minimum constrained input selection and minimum cost constrained input selection for state space structured systems. The input matrix is constrained in the sense that the set of states that each input can influence is pre-specified and each input has a cost associated with it. Our goal is to optimally select an input set from the set of inputs given that the system is controllable. These problems are known to be NP-hard. Firstly, we give a new necessary and sufficient graph theoretic condition for checking structural controllability using flow networks. Using this condition we give a polynomial reduction of both these problems to a known NP-hard problem, the minimum cost fixed flow problem (MCFF). Subsequently, we prove that an optimal solution to the MCFF problem corresponds to an optimal solution to the original controllability problem. We also show that approximation schemes of MCFF directly applies to minimum cost constrained input selection problems. Using the special structure of the flow network constructed for the structured system, we give a polynomial approximation algorithm based on minimum weight bipartite matching and a greedy selection scheme for solving MCFF on system flow network. The proposed algorithm gives a $\Delta$-approximate solution to MCFF, where $\Delta$ denotes the maximum in-degree of input vertices in the flow network of the structured system., Comment: 12 Pages, 4 Figures

The problem of distributed controller synthesis for formation control of multi-agent systems is considered. The agents (single integrators) communicate over a communication graph and a decentralized linear feedback structure is assumed. One of the agents is designated as the leader. If the communication graph contains a directed spanning tree with the leader node as the root, then it is possible to place the poles of the ensemble system with purely local feedback controller gains. Given a desired formation, first one of the poles is placed at the origin. Then it is shown that the inter-agent weights can be independently adjusted to assign an eigenvector corresponding to the formation positions, to the zero eigenvalue. Then, only the leader input is enough to bring the agents to the desired formation and keep it there with no further inputs. Moreover, given a formation, the computation of the inter-agent weights that encode the formation information, can be calculated in a decentralized fashion using only local information., Comment: 7 pages, 12 figures. Submitted to the CDC 2013 (Italy)

The theory of dissipativity has been primarily developed for controllable systems/behaviors. For various reasons, in the context of uncontrollable systems/behaviors, a more appropriate definition of dissipativity is in terms of the dissipation inequality, namely the {\em existence} of a storage function. A storage function is a function such that along every system trajectory, the rate of increase of the storage function is at most the power supplied. While the power supplied is always expressed in terms of only the external variables, whether or not the storage function should be allowed to depend on unobservable/hidden variables also has various consequences on the notion of dissipativity: this paper thoroughly investigates the key aspects of both cases, and also proposes another intuitive definition of dissipativity. We first assume that the storage function can be expressed in terms of the external variables and their derivatives only and prove our first main result that, assuming the uncontrollable poles are unmixed, i.e. no pair of uncontrollable poles add to zero, and assuming a strictness of dissipativity at the infinity frequency, the dissipativities of a system and its controllable part are equivalent. We also show that the storage function in this case is a static state function. We then investigate the utility of unobservable/hidden variables in the definition of storage function: we prove that lossless autonomous behaviors require storage function to be unobservable from external variables. We next propose another intuitive definition: a behavior is called dissipative if it can be embedded in a controllable dissipative {\em super-behavior}. We show that this definition imposes a constraint on the number of inputs and thus explains unintuitive examples from the literature in the context of lossless/orthogonal behaviors., Comment: 26 pages, one figure. Partial results appeared in an IFAC conference (World Congress, Milan, Italy, 2011)

This paper addresses questions regarding controllability for `generic parameter' dynamical systems, i.e. the question whether a dynamical system is `structurally controllable'. Unlike conventional methods that deal with structural controllability, our approach uses an undirected graph: the behavioral approach to modelling dynamical systems allows this. Given a system of linear, constant coefficient, ordinary differential equations of any order, we formulate necessary and sufficient conditions for controllability in terms of weights of the edges in a suitable bipartite graph constructed from % components with equal bipartite cardinality in the differential-algebraic system. % of equations. A key notion that helps formulate the conditions is that of a `redundant edge'. Removal of all redundant edges makes the inferring of structural controllability a straightforward exercise. We use standard graph algorithms as ingredients to check these conditions and hence obtain an algorithm to check for structural controllability. We provide an analysis of the running time of our algorithm. When our results are applied to the familiar state space description of a system, we obtain a novel necessary and sufficient condition to check structural controllability for this description., Comment: 17 pages, 2 figures