Network synchronizability analysis: A graph-theoretic approach

This paper addresses the fundamental problem of complex network synchronizability from a graphtheoretic approach. First, the existing results are briefly reviewed. Then, the relationships between the network synchronizability and network structural parameters (e. g., average distance, degree distribution, and node betweenness centrality) are discussed. The effects of the complementary graph of a given network and some graph operations on the network synchronizability are discussed. A basic theory based on subgraphs and complementary graphs for estimating the network synchronizability is established. Several examples are given to show that adding new edges to a network can either increase or decrease the network synchronizability. To that end, some new results on the estimations of the synchronizability of coalescences are reported. Moreover, a necessary and sufficient condition for a network and its complementary network to have the same synchronizability is derived. Finally, some examples on Chua circuit networks are presented for illustration. (C) 2008 American Institute of Physics.