Ultrafast consensus in small-world networks

被引:390
作者
Olfati-Saber, R [1 ]
机构
[1] CALTECH, Pasadena, CA 91125 USA
来源
ACC: PROCEEDINGS OF THE 2005 AMERICAN CONTROL CONFERENCE, VOLS 1-7 | 2005年
关键词
small-world networks; networked systems; consensus algorithms; phase transition; graph Laplacians; algebraic connectivity; network robustness; random matrices;
D O I
10.1109/ACC.2005.1470321
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
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 ultrafast 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.
引用
收藏
页码:2371 / 2378
页数:8
相关论文
共 43 条
  • [1] [Anonymous], 1998, GRAD TEXT M, DOI 10.1007/978-1-4612-0619-4_7
  • [2] Scale-free characteristics of random networks:: the topology of the World-Wide Web
    Barabási, AL
    Albert, R
    Jeong, H
    [J]. PHYSICA A, 2000, 281 (1-4): : 69 - 77
  • [3] Emergence of scaling in random networks
    Barabási, AL
    Albert, R
    [J]. SCIENCE, 1999, 286 (5439) : 509 - 512
  • [4] Network robustness and fragility: Percolation on random graphs
    Callaway, DS
    Newman, MEJ
    Strogatz, SH
    Watts, DJ
    [J]. PHYSICAL REVIEW LETTERS, 2000, 85 (25) : 5468 - 5471
  • [5] CHANG DE, 2003, P IEEE C DEC CONTR D
  • [6] Coverage control for mobile sensing networks
    Cortés, J
    Martínez, S
    Karatas, T
    Bullo, F
    [J]. IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, 2004, 20 (02): : 243 - 255
  • [7] EIGENVALUES AND CONDITION NUMBERS OF RANDOM MATRICES
    EDELMAN, A
    [J]. SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 1988, 9 (04) : 543 - 560
  • [8] ERDOS P, 1960, B INT STATIST INST, V38, P343
  • [9] Estrin D., 1999, P MOBICOM, DOI DOI 10.1145/313451.313556
  • [10] FARKAS I, 2004, CONDMAT0303106, P1