

Preprint 39/2004
Synchronization of networks with prescribed degree distributions
Fatihcan M. Atay, Türker Biyikoglu, and Jürgen Jost
Contact the author: Please use for correspondence this email.
Submission date: 17. Jun. 2004 (revised version: May 2005)
Pages: 17
published in: IEEE transactions on circuits and systems / 1, 53 (2006) 1, p. 92-98
DOI number (of the published article): 10.1109/TCSI.2005.854604
Bibtex
with the following different title: On the synchronization of networks with prescribed degree distributions
Keywords and phrases: synchronization, networks, graph theory, Laplacian
Download full preprint: PDF (215 kB), PS ziped (195 kB)
Abstract:
We show that the degree distributions of graphs do not suffice to characterize
the synchronization of systems evolving on them. We prove that, for any given
degree sequence satisfying certain conditions, a connected graph having that
degree sequence exists for which the first nontrivial eigenvalue of the graph
Laplacian is arbitrarily close to zero. Consequently, dynamical systems
defined on such graphs have poor synchronization properties. The result holds
under quite mild assumptions, and shows that there exists classes of random,
scale-free, regular, small-world, and other common network architectures which
impede synchronization. The proof is based on a construction that also serves
as an algorithm for building non-synchronizing networks having a prescribed
degree distribution.