Determining Redundant Links of Multiagent Systems in Keeping or Improving Consensus Convergence Rates

For a multiagent system (MAS), some redundant links can be removed without reducing its convergence rate. The deletion of redundant links is of benefit to an MAS in improving its lifetime, resources usage efficiency, and so on. In this article, the problem of determining redundant links of MASs is addressed. Based on the theory of graph spectra, necessary and sufficient conditions for determining a redundant link are given for an MAS under the first-order and the second-order consensus protocols. It is surprising to find that the convergence rate of the second-order protocol can even be improved by removing some redundant links, which can be determined by the proposed condition. Moreover, algorithms with running time $O(N^5)$ are designed to determine a maximal set of redundant links for MASs with $N$ agents. Numerical simulations are given to illustrate the effectiveness of the algorithms.