Formation of robust multi-Agent networks through self-organizing random regular graphs

A. Yasin Yazicioǧlu, Magnus Egerstedt, Jeff S. Shamma

Research output: Contribution to journalArticlepeer-review

31 Scopus citations


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 ϵ [k+k ] 2. Accordingly, the agents improve the robustness of the network while maintaining a similar number of links as the initial configuration by locally adding or removing some edges.

Original languageEnglish (US)
Article number7337422
Pages (from-to)139-151
Number of pages13
JournalIEEE Transactions on Network Science and Engineering
Issue number4
StatePublished - 2015

Bibliographical note

Publisher Copyright:
© 2015 IEEE.


  • Multi-Agent systems
  • robust networks
  • self-organization

Cite this