Small world phenomenon, rapidly mixing Markov chains, and average consensus algorithms

Alireza Tahbaz-Salehi*, Ali Jadbabaie

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

33 Scopus citations

Abstract

In this paper, we demonstrate the relationship between the diameter of a graph and the mixing time of a symmetric Markov chain defined on it. We use this relationship to show that graphs with the small world property have dramatically small mixing times. Based on this result, we conclude that addition of independent random edges with arbitrarily small probabilities to a cycle significantly increases the convergence speed of average consensus algorithms, meaning that small world networks reach consensus orders of magnitude faster than a cycle. Furthermore, this dramatic increase happens for any positive probability of random edges. The same argument is used to draw a similar conclusion for the case of addition of a random matching to the cycle.

Original languageEnglish (US)
Title of host publicationProceedings of the 46th IEEE Conference on Decision and Control 2007, CDC
Pages276-281
Number of pages6
DOIs
StatePublished - Dec 1 2007
Event46th IEEE Conference on Decision and Control 2007, CDC - New Orleans, LA, United States
Duration: Dec 12 2007Dec 14 2007

Publication series

NameProceedings of the IEEE Conference on Decision and Control
ISSN (Print)0191-2216

Other

Other46th IEEE Conference on Decision and Control 2007, CDC
CountryUnited States
CityNew Orleans, LA
Period12/12/0712/14/07

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization

Fingerprint Dive into the research topics of 'Small world phenomenon, rapidly mixing Markov chains, and average consensus algorithms'. Together they form a unique fingerprint.

Cite this