Small-world topology can significantly improve the performance of noisy consensus in a complex network

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

17 Scopus Citations
View graph of relations


Related Research Unit(s)


Original languageEnglish
Pages (from-to)3242-3254
Journal / PublicationComputer Journal
Issue number12
Publication statusPublished - 20 Nov 2014


In this paper, we study the first-order consensus algorithm in the small-world Farey graph where agents are driven by white noise, aiming to unveil the effect of small-world topology on the robustness of the consensus algorithm. We characterize the coherence of the Farey graph in terms of the $H-2$-norm of the system, the square of which equals the steady-state variance and thus captures how closely agents track the consensus value. Based on the particular network structure, we derive an exact expression for the coherence in the Farey graph, whose dominant behavior scales logarithmically with the system size. To uncover the role of small-world topology, we also derive an analytical solution for the coherence of first-order consensus in the regular ring lattice sharing the same average degree as the Farey graph, whose dominant term grows linearly with the system size, implying that the small-world structure strongly affects the performance of the consensus algorithm.

Research Area(s)

  • distributed average consensus, graph Laplacian, networked control system, small-world network