  Multi-agent networks are often modeled as interaction graphs, where the nodes
represent the agents and the edges denote some direct interactions. The
robustness of a multi-agent network to perturbations such as failures, noise,
or malicious attacks largely depends on the corresponding graph. In many
applications, networks are desired to have well-connected interaction graphs
with relatively small number of links. One family of such graphs is the random
regular graphs. In this paper, we present a decentralized scheme for
transforming any connected interaction graph with a possibly non-integer
average degree of k into a connected random m-regular graph for some m in [k, k
+ 2]. Accordingly, the agents improve the robustness of the network with a
minimal change in the overall sparsity by optimizing the graph connectivity
through the proposed local operations.

Multiagent Systems;Social and Information Networks;Systems and Control;Combinatorics