Decentralized Degree Regularization for Multi-Agent Networks

Abstract

Networked multi-agent systems are widely modeled as graphs where the agents are represented as nodes and edges exist between the agents that interact directly. In this setting, the degree of a node is the number of edges incident to it. For such systems, degree regularity (uniformity of degree across the nodes) typically provides desirable properties such as robustness and fast mixing time. As such, a key task is to achieve degree regularization in a decentralized manner. In this paper, we present a locally applicable rule that achieves this task. For any connected initial graph, the proposed reconfiguration rule preserves the graph connectivity and the total number of edges in the system while minimizing the difference between the maximum and the minimum node degrees.