Skip navigation
Please use this identifier to cite or link to this item:
Title: Optimal Leader Selection in Multi-agent Networks: Joint Centrality, Robustness and Controllability
Authors: Fitch, Katherine Elisabeth
Advisors: Leonard, Naomi E
Contributors: Mechanical and Aerospace Engineering Department
Keywords: Controllability
Leader Selection Problem
Multi-agent systems
Networked systems
Subjects: Mechanical engineering
Applied mathematics
Issue Date: 2011
Publisher: Princeton, NJ : Princeton University
Abstract: In many engineered and natural multi-agent networked systems, a limited subset of agents, called leaders, have access to external information, while the remaining agents, called followers, obtain information through network connections. In this dissertation, we connect measures of group-level performance with properties of the underlying network. Specifically, we determine which nodes in the network should be selected as leader nodes to maximize controllability and robustness of the leader-follower consensus dynamics to noise. Maximizing robustness of the leader-follower consensus dynamics to noise is equivalent to minimizing steady-state system error defined in terms of variance about consensus. We define a new notion of centrality of a set of nodes, called joint centrality, that will be maximized by the optimal leader set for robustness to noise. We demonstrate that the optimal selection of a single leader for robustness to noise is the most information central agent. We show that, in general, node sets with high joint centrality balance high individual information centralities with coverage over the network. For unweighted path and cycle graphs, we explicitly solve the optimal leader selection problem for robustness to noise. For unweighted tree graphs, we provide a simplification of two- and three-node joint centrality and present provable bounds for computationally efficient leader selection. Centrality of a set of nodes is significant to a variety of network applications. We explore and illustrate the use of joint centrality in an example of synthetic lethality in Saccharomyces cerevisiae (baker's yeast), in an example of clustering in a Facebook social network, and in a network of political books frequently purchased together on Amazon. In leader selection for controllability, we study average controllability, which measures the difficulty in controlling agents to any state in finite time, and volume of the subspace reachable with one unit of control input. We prove that average controllability is maximized when the leader set is composed of the least information central nodes. We demonstrate that reachable volume is dependent on the left eigenvectors of the graph Laplacian corresponding to the leader nodes. We explore the fundamental trade-off between leader selection for robustness and leader selection for controllability.
Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog:
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Mechanical and Aerospace Engineering

Files in This Item:
File Description SizeFormat 
Fitch_princeton_0181D_11959.pdf1.46 MBAdobe PDFView/Download

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.