Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published August 1, 2005 | public
Book Section - Chapter Open

Ultrafast Consensus in Small-World Networks

Abstract

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.

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.

Files

OLFacc05.pdf
Files (432.7 kB)
Name Size Download all
md5:7a78e3553ae4a9f3b6a6b5bb24b5891a
432.7 kB Preview Download

Additional details

Created:
August 22, 2023
Modified:
October 16, 2023