A Caltech Library Service

Ultrafast Consensus in Small-World Networks

Olfati-Saber, Reza (2005) Ultrafast Consensus in Small-World Networks. In: Proceedings of the American Control Conference, 2005 -- June 8-10, 2005, Portland, OR, USA. Vol.4. IEEE , Los Alamitos, CA, pp. 2371-2378. ISBN 0-7803-9098-9.

See Usage Policy.


Use this Persistent URL to link to this item:


In this paper, we demonstrate a phase transition phenomenon in algebraic connectivity of small-world networks. Algebraic connectivity of a graph is the second smallest eigenvalue of its Laplacian matrix and a measure of speed of solving consensus problems in networks. We demonstrate that it is possible to dramatically increase the algebraic connectivity of a regular complex network by 1000 times or more without adding new links or nodes to the network. This implies that a consensus problem can be solved incredibly fast on certain small-world networks giving rise to a network design algorithm for ultra fast information networks. Our study relies on a procedure called "random rewiring" due to Watts & Strogatz (Nature, 1998). Extensive numerical results are provided to support our claims and conjectures. We prove that the mean of the bulk Laplacian spectrum of a complex network remains invariant under random rewiring. The same property only asymptotically holds for scale-free networks. A relationship between increasing the algebraic connectivity of complex networks and robustness to link and node failures is also shown. This is an alternative approach to the use of percolation theory for analysis of network robustness. We also show some connections between our conjectures and certain open problems in the theory of random matrices.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© Copyright 2005 IEEE. Reprinted with permission. This research was supported in part by ARO under the grant #W911NF–04–1–0316, by AFOSR under the grant #49620–01–1–0361, and by DARPA under the grant #33615–98–C–3816. I would like to thank Jeff Shamma for our discussions on complex economic & social networks and Richard M. Murray for his continued support.
Subject Keywords:small-world networks, networked systems, consensus algorithms, phase transition, graph Laplacians, algebraic connectivity, network robustness, random matrices
Record Number:CaltechAUTHORS:OLFacc05
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:5147
Deposited By: Archive Administrator
Deposited On:03 Oct 2006
Last Modified:08 Nov 2021 20:23

Repository Staff Only: item control page