Consensus dynamics and coherence in hierarchical small-world networks

The hierarchical small-world network effectively models the benefit transmission web of pyramid schemes in China and many other countries. In this paper, by applying spectral graph theory, we studied three important aspects of the consensus problem in such networks: convergence speed, communication time-delay robustness, and network coherence. First, we explicitly determined the Laplacian eigenvalues of the network by making use of its tree-like structure. Second, we found that the consensus algorithm on the hierarchical small-world network converges faster than on some well studied sparse networks but is less robust to time delays. We also derived a closed-form for the first-order network coherence. Our results show that the hierarchical small-world network has an optimal structure of noisy consensus dynamics. Finally, we argued that some network structure characteristics, such as a large maximum degree, small average path length, and high vertex and edge connectivity, are responsible for the strong robustness against external perturbations.