(Received 16 November 2005; revised 6 November 2006; published 21 February 2007)

A regular array of oscillators with random coupling exhibits a transition from synchronized motion to desynchronized but ordered waves as a global coupling parameter is increased, due to the spread of localized instability of eigenvectors of the Laplacian matrix. We find that shortcuts, which make a regular network small-world, can destroy ordered desynchronization wave patterns. Wave patterns in a small-world network are usually destroyed gradually as the degree of regularity in the network deteriorates. No ordered wave patterns are observed in scale-free and random networks. The formation of ordered wave patterns in a coupled oscillator network can be explained by considering the time evolution of phase in each oscillator. We derive a general type of the Kardar-Parisi-Zhang equation for phase evolution in a prototype oscillator network. The equation demonstrates well the ordered desynchronized wave patterns found in the network with and without shortcuts. Our results provide a qualitative justification for the requirement of certain degree of regularity in the network for ordered wave patterns to arise.