Optimal Leader Selection in Multi-agent Networks: Joint Centrality, Robustness and Controllability

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.