No data available.

Please log in to see this content.

You have no subscription access to this content.

No metrics data to plot.

The attempt to load metrics for this article has failed.

The attempt to plot a graph for these metrics has failed.

The full text of this article is not currently available.

Network synchronizability analysis: A graph-theoretic approach

### Abstract

This paper addresses the fundamental problem of complex network synchronizability from a graph-theoretic 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.

© 2008 American Institute of Physics

Received 29 February 2008
Accepted 09 July 2008
Published online 22 September 2008

Lead Paragraph:
First, two simple examples of regular symmetrical graphs are presented, to show that they have the same structural parameters (average distance, degree distribution, and node betweenness centrality) but have very different synchronizabilities. This demonstrates the intrinsic complexity of the network synchronizability problem. Several examples are then provided to show that adding new edges to a network can either increase or decrease the network synchronizability. However, it is found that for networks with disconnected complementary graphs, adding edges never decreases their synchronizability. On the other hand, adding one edge to a cycle of size definitely decreases the network sychronizability. Then, since sometimes the synchronizability can be enhanced by changing the network structures, the question of whether the networks with more edges are easier to synchronize is addressed. It is shown by examples that the answer is no. This reveals that generally there are redundant edges in a network, which not only make no contributions to synchronization but actually may reduce the synchronizability. Moreover, three types of graph operations are discussed, which may change the network synchronizability. Further, subgraphs and complementary graphs are used to analyze the network synchronizability. Some sharp and attainable bounds are provided for the eigenratio of the network structural matrix, which characterizes the network synchronizability especially when the network’s corresponding graph has cycles, bipartite graphs or product graphs as its subgraphs. Finally, by analyzing the effects of a newly added node, some results on estimating the synchronizability of coalescences are presented. It is found that a network and its complementary network have the same synchronizability when the sum of the smallest nonzero and largest eigenvalues of the corresponding graph is equal to the size of the network, i.e., the total number of its nodes. Some equilibrium synchronization examples are finally simulated for illustration.

Acknowledgments:
This work is jointly supported by the National Natural Science Foundation of China under Grant No. 60674093, the Key Projects of Educational Ministry under Grant No. 107110, and the NSFC-HK Joint Research Scheme under Grant No. N-CityU 107/07.

Article outline:

I. INTRODUCTION
II. RELATIONSHIPS BETWEEN THE NETWORK SYNCHRONIZABILITY AND NETWORK STRUCTURAL PARAMETERS
III. EFFECTS OF EDGE ADDITION AND COMPLEMENTARY GRAPHS
IV. EFFECTS OF GRAPH OPERATIONS
V. THEORY OF SUBGRAPHS AND COMPLEMENTARY GRAPHS FOR ESTIMATING THE NETWORK SYNCHRONIZABILITY
VI. MORE RESULTS ON THE SYNCHRONIZABILITY OF COALESCENCES
VII. CONDITIONS FOR A NETWORK AND ITS COMPLEMENTARY NETWORK TO HAVE THE SAME SYNCHRONIZABILITY
VIII. EQUILIBRIUM SYNCHRONIZATION OF A CHUA CIRCUIT NETWORK
IX. CONCLUSION

/content/aip/journal/chaos/18/3/10.1063/1.2965530

http://aip.metastore.ingenta.com/content/aip/journal/chaos/18/3/10.1063/1.2965530

Article metrics loading...

/content/aip/journal/chaos/18/3/10.1063/1.2965530

2008-09-22

2016-10-25

Full text loading...

###
Most read this month

Article

content/aip/journal/chaos

Journal

5

3

Commenting has been disabled for this content