TY - GEN

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

AU - Tahbaz-Salehi, Alireza

AU - Jadbabaie, Ali

PY - 2007/12/1

Y1 - 2007/12/1

N2 - 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.

AB - 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.

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

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

U2 - 10.1109/CDC.2007.4434174

DO - 10.1109/CDC.2007.4434174

M3 - Conference contribution

AN - SCOPUS:62749195633

SN - 1424414989

SN - 9781424414987

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 276

EP - 281

BT - Proceedings of the 46th IEEE Conference on Decision and Control 2007, CDC

T2 - 46th IEEE Conference on Decision and Control 2007, CDC

Y2 - 12 December 2007 through 14 December 2007

ER -