Optimal Leader Selection for Dynamic Networks Modeled as Mark as Jump Linear Systems

Abstract

The analysis of dynamic networks provides frameworks through which researchers can investigate biological phenomena, analyze complex human interactions, and design man-made systems like robotic swarms. The distributed consensus problem studies the behavior of net-works in which all agents seek to estimate the same reference signal and reach agreement on its value. The conditions for which networks achieve consensus are well established, and researchers have begun to apply the consensus problem to different network constructions, such as leader-follower systems. A leader invests in the costly measurement of the external signal while a follower adapts its estimate based on the information it gathers from its neighbors. This strategy is motivated by evidence of its occurrence in nature and the potential to reduce energy costs. Previous research found a direct connection between the optimal leader set and the joint information centrality of the agents for static networks. The leader selection problem has been extended to dynamic networks, but due to the combinatoric nature of the problem, the main contributions have been the proposal of efficient greedy algorithms. In this work, we explore the leader selection problem for dynamic networks modeled as Markov jump linear systems with the objective of analytically solving for the optimal leader set based on the graph topologies and the switching behavior of the system. We provide system-certainty and node-certainty indices for both discrete- and continuous-time dynamic networks, from which the optimal leader set can be derived. However, the selection of leader sets with cardinality greater than one still poses computational challenges. We therefore further investigate the system behavior in order to develop an intuitive understanding of the results that may improve leader selection algorithms. We determine that conventional centrality measures are unsuitable for dynamic networks, and the local structure of an agent’s neighborhood most significantly affects its leader potential.