Decentralized formation of random regular graphs for robust multi-agent networks

A. Yasin Yazicioglu; Magnus Egerstedt; Jeff S. Shamma

doi:10.1109/CDC.2014.7039446

Decentralized formation of random regular graphs for robust multi-agent networks

A. Yasin Yazicioglu, Magnus Egerstedt, Jeff S. Shamma

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Multi-agent networks are often modeled via interaction graphs, where the nodes represent the agents and the edges denote direct interactions between the corresponding agents. Interaction graphs have significant impact on the robustness of networked systems. One family of robust graphs is the random regular graphs. In this paper, we present a locally applicable reconfiguration scheme to build random regular graphs through self-organization. For any connected initial graph, the proposed scheme maintains connectivity and the average degree while minimizing the degree differences and randomizing the links. As such, if the average degree of the initial graph is an integer, then connected regular graphs are realized uniformly at random as time goes to infinity.

Original language	English (US)
Title of host publication	53rd IEEE Conference on Decision and Control,CDC 2014
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	595-600
Number of pages	6
Edition	February
ISBN (Electronic)	9781479977468
DOIs	https://doi.org/10.1109/CDC.2014.7039446
State	Published - 2014
Externally published	Yes
Event	2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014 - Los Angeles, United States Duration: Dec 15 2014 → Dec 17 2014

Publication series

Name	Proceedings of the IEEE Conference on Decision and Control
Number	February
Volume	2015-February
ISSN (Print)	0743-1546
ISSN (Electronic)	2576-2370

Other

Other	2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014
Country/Territory	United States
City	Los Angeles
Period	12/15/14 → 12/17/14

ASJC Scopus subject areas

Control and Systems Engineering
Modeling and Simulation
Control and Optimization

Online availability

10.1109/CDC.2014.7039446

Library availability

Discover UIUC Full Text

Cite this

Yazicioglu, A. Y., Egerstedt, M., & Shamma, J. S. (2014). Decentralized formation of random regular graphs for robust multi-agent networks. In 53rd IEEE Conference on Decision and Control,CDC 2014 (February ed., pp. 595-600). [7039446] (Proceedings of the IEEE Conference on Decision and Control; Vol. 2015-February, No. February). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CDC.2014.7039446

Decentralized formation of random regular graphs for robust multi-agent networks. / Yazicioglu, A. Yasin; Egerstedt, Magnus; Shamma, Jeff S.

53rd IEEE Conference on Decision and Control,CDC 2014. February. ed. Institute of Electrical and Electronics Engineers Inc., 2014. p. 595-600 7039446 (Proceedings of the IEEE Conference on Decision and Control; Vol. 2015-February, No. February).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Yazicioglu, AY, Egerstedt, M & Shamma, JS 2014, Decentralized formation of random regular graphs for robust multi-agent networks. in 53rd IEEE Conference on Decision and Control,CDC 2014. February edn, 7039446, Proceedings of the IEEE Conference on Decision and Control, no. February, vol. 2015-February, Institute of Electrical and Electronics Engineers Inc., pp. 595-600, 2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014, Los Angeles, United States, 12/15/14. https://doi.org/10.1109/CDC.2014.7039446

Yazicioglu AY, Egerstedt M, Shamma JS. Decentralized formation of random regular graphs for robust multi-agent networks. In 53rd IEEE Conference on Decision and Control,CDC 2014. February ed. Institute of Electrical and Electronics Engineers Inc. 2014. p. 595-600. 7039446. (Proceedings of the IEEE Conference on Decision and Control; February). https://doi.org/10.1109/CDC.2014.7039446

@inproceedings{101f4688ddca40739566bd798917ae19,

title = "Decentralized formation of random regular graphs for robust multi-agent networks",

abstract = "Multi-agent networks are often modeled via interaction graphs, where the nodes represent the agents and the edges denote direct interactions between the corresponding agents. Interaction graphs have significant impact on the robustness of networked systems. One family of robust graphs is the random regular graphs. In this paper, we present a locally applicable reconfiguration scheme to build random regular graphs through self-organization. For any connected initial graph, the proposed scheme maintains connectivity and the average degree while minimizing the degree differences and randomizing the links. As such, if the average degree of the initial graph is an integer, then connected regular graphs are realized uniformly at random as time goes to infinity.",

author = "Yazicioglu, {A. Yasin} and Magnus Egerstedt and Shamma, {Jeff S.}",

note = "Publisher Copyright: {\textcopyright} 2014 IEEE.; 2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014 ; Conference date: 15-12-2014 Through 17-12-2014",

year = "2014",

doi = "10.1109/CDC.2014.7039446",

language = "English (US)",

series = "Proceedings of the IEEE Conference on Decision and Control",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "February",

pages = "595--600",

booktitle = "53rd IEEE Conference on Decision and Control,CDC 2014",

address = "United States",

edition = "February",

}

TY - GEN

T1 - Decentralized formation of random regular graphs for robust multi-agent networks

AU - Yazicioglu, A. Yasin

AU - Egerstedt, Magnus

AU - Shamma, Jeff S.

PY - 2014

Y1 - 2014

N2 - Multi-agent networks are often modeled via interaction graphs, where the nodes represent the agents and the edges denote direct interactions between the corresponding agents. Interaction graphs have significant impact on the robustness of networked systems. One family of robust graphs is the random regular graphs. In this paper, we present a locally applicable reconfiguration scheme to build random regular graphs through self-organization. For any connected initial graph, the proposed scheme maintains connectivity and the average degree while minimizing the degree differences and randomizing the links. As such, if the average degree of the initial graph is an integer, then connected regular graphs are realized uniformly at random as time goes to infinity.

AB - Multi-agent networks are often modeled via interaction graphs, where the nodes represent the agents and the edges denote direct interactions between the corresponding agents. Interaction graphs have significant impact on the robustness of networked systems. One family of robust graphs is the random regular graphs. In this paper, we present a locally applicable reconfiguration scheme to build random regular graphs through self-organization. For any connected initial graph, the proposed scheme maintains connectivity and the average degree while minimizing the degree differences and randomizing the links. As such, if the average degree of the initial graph is an integer, then connected regular graphs are realized uniformly at random as time goes to infinity.

UR - http://www.scopus.com/inward/record.url?scp=84988290569&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84988290569&partnerID=8YFLogxK

U2 - 10.1109/CDC.2014.7039446

DO - 10.1109/CDC.2014.7039446

M3 - Conference contribution

AN - SCOPUS:84988290569

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 595

EP - 600

BT - 53rd IEEE Conference on Decision and Control,CDC 2014

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014

Y2 - 15 December 2014 through 17 December 2014

ER -

Decentralized formation of random regular graphs for robust multi-agent networks

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this