Paper Info
Title
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.
Year
DOI
Venue
2005
10.1109/ACC.2005.1470321
american control conference
Keywords
DocType
ISSN
oscillators,laplacian matrix,percolation theory,complex networks,random matrices,intelligent networks,small world networks,phase transition,robustness,algebraic connectivity,complex network,network design,consensus problem,graph laplacian,scale free network,control systems,small world network,graph theory
Conference
0743-1619 E-ISBN : 0-7803-9099-7
ISBN
Citations 
PageRank 
0-7803-9099-7
134
20.38
References 
Authors
9
1
Search Limit
100134
Name
Order
Citations
PageRank
Reza Olfati-Saber18066549.43