Search

MiS Preprint Repository

We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.

MiS Preprint
39/2004

Synchronization of networks with prescribed degree distributions

Fatihcan M. Atay, Türker Biyikoglu and Jürgen Jost

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.

Received:
Jun 17, 2004
Published:
Jun 17, 2004
Keywords:
synchronization, networks, graph theory, Laplacian

Related publications

inJournal
2006 Repository Open Access
Fatihcan M. Atay, Türker Biyikoglu and Jürgen Jost

On the synchronization of networks with prescribed degree distributions

In: IEEE transactions on circuits and systems / 1, 53 (2006) 1, pp. 92-98