Title:
On the Synchronization of Networks with Prescribed Degree Distributions
Author(s):
Fatihcan Atay, Tuerker Biyikoglu, Jürgen Jost
Paper #:
04-06-019
Date:
June 1, 2004
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 exist 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.
Facebook
Twitter
Email Newsletter
SFI News Feed
Google+
YouTube
iTunes U