Rewiring networks for synchronization

We study the synchronization of identical oscillators diffusively coupled through a network and examine how adding, removing, and moving single edges affects the ability of the network to synchronize. We present algorithms which use methods based on node degrees and based on spectral properties of the network Laplacian for choosing edges that most impact synchronization. We show that rewiring based on the network Laplacian eigenvectors is more effective at enabling synchronization than methods based on node degree for many standard network models. We find an algebraic relationship between the eigenstructure before and after adding an edge and describe an efficient algorithm for computing Laplacian eigenvalues and eigenvectors that uses the network or its complement depending on which is more sparse. (C) 2008 American Institute of Physics.