Synchronization of networks with prescribed degree distributions

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, there exists a connected graph having that degree sequence for which the first nontrivial eigenvalue of the graph Laplacian is arbitrarily close to zero. Consequently, complex 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.

v2: A new theorem and a numerical example added. To appear in IEEE Trans. Circuits and Systems I: Fundamental Theory and Applications

References in corpus (9)

• Emergence of scaling in random networks
• The structure and function of complex networks
• Lethality and centrality in protein networks
• Synchronization in small-world systems
• Renormalization group analysis of the small-world network model
• Heterogeneity in oscillator networks: Are smaller worlds easier to synchronize?
• Spectral Properties and Synchronization in Coupled Map Lattices
• Delays, connection topology, and synchronization of coupled chaotic maps
• Evolving networks with distance preferences

Cited by in corpus (18)

• Synchronization in complex networks
• Evolving functional network properties and synchronizability during human epileptic seizures
• Comparing the Topological and Electrical Structure of the North American Electric Power Infrastructure
• Synchronization processes in complex networks
• Network synchronization: Spectral versus statistical properties
• Ensemble averageability in network spectra
• Synchronization and modularity in complex networks
• Distinct scalings for mean first-passage time of random walks on scale-free networks with the same degree sequence
• Spectral plots and the representation and interpretation of biological data
• Random matrix analysis of network Laplacians
• Deformed Gaussian Orthogonal Ensemble description of Small-World networks
• A PMU Scheduling Scheme for Transmission of Synchrophasor Data in Electric Power Systems
• Diffusion-annihilation proecesses in weighted scale-free networks with identical degree sequence
• On Synchronization of Interdependent Networks
• Electrical Structure-Based PMU Placement in Electric Power Systems
• A Unifying Framework for the Electrical Structure-Based Approach to PMU Placement in Electric Power Systems
• An Electrical Structure-Based Approach to PMU Placement in the Electric Power Grid
• Equitable Decompositions of Graphs