Consensus and synchronization problems on small-world networks

In this paper, it is discovered that the statistical property of the consensus and synchronization of the small-world networks, that is, the Cheeger constant, is a major determinant to measure the convergence rate of the consensus and synchronization of the small-world networks. Further, we give a mathematical rigorous estimation of the lower bound for the algebraic connectivity of the small-world networks, which is much larger than the algebraic connectivity of the regular circle. This result explains why the consensus problems on the small-world network have an ultrafast convergence rate and how much it can be improved. Moreover, it also characterizes quantitatively what kind of the small-world networks can be synchronized.