Collective Relaxation Dynamics of Small-World Networks

Abstract

Complex networks exhibit a wide range of collective dynamic phenomena, including synchronization, diffusion, relaxation, and coordination processes. Their asymptotic dynamics is generically characterized by the local Jacobian, graph Laplacian or a similar linear operator. The structure of networks with regular, small-world and random connectivities are reasonably well understood, but their collective dynamical properties remain largely unknown. Here we present a two-stage mean-field theory to derive analytic expressions for network spectra. A single formula covers the spectrum from regular via small-world to strongly randomized topologies in Watts-Strogatz networks, explaining the simultaneous dependencies on network size N, average degree k and topological randomness q. We present simplified analytic predictions for the second largest and smallest eigenvalue, and numerical checks confirm our theoretical predictions for zero, small and moderate topological randomness q, including the entire small-world regime. For large q of the order of one, we apply standard random matrix theory thereby overarching the full range from regular to randomized network topologies. These results may contribute to our analytic and mechanistic understanding of collective relaxation phenomena of network dynamical systems.

arXiv comment12 pages, 10 figures, published in PRE

References in corpus (24)

• Synchronization in complex networks
• Synchronization in small-world systems
• Clustering in Complex Directed Networks
• Network Synchronization, Diffusion, and the Paradox of Heterogeneity
• Spectra of "Real-World" Graphs: Beyond the Semi-Circle Law
• Mean-field solution of the small-world network model
• Revealing Network Connectivity From Dynamics
• Enhancing complex-network synchronization
• Spectral Properties and Synchronization in Coupled Map Lattices
• Diffusion, localization and dispersion relations on ``small-world'' lattices
• Revealing networks from dynamics: an introduction
• On the spectra of nonsymmetric Laplacian matrices
• Sparse random matrices: the eigenvalue spectrum revisited
• Laplacian spectra of complex networks and random walks on them: Are scale-free architectures really important?
• Topological Speed Limits to Network Synchronization
• Laplacian Spectra as a Diagnostic Tool for Network Structure and Dynamics
• The circular law for random matrices
• Optimal network topologies: Expanders, Cages, Ramanujan graphs, Entangled networks and all that
• Speed of synchronization in complex networks of neural oscillators Analytic results based on Random Matrix Theory
• Kuramoto dynamics in Hamiltonian systems
• Do Small Worlds Synchronize Fastest?
• Small-world spectra in mean field theory
• Speed of complex network synchronization
• Spectra of Modular and Small-World Matrices

Cited by in corpus (7)

• The Kuramoto model in complex networks
• Collective frequency variation in network synchronization and reverse PageRank
• Dynamics of "comb-of-comb" networks
• Synchronization of fluctuating delay-coupled chaotic networks
• Reconstruction of evolved dynamic networks from degree correlations
• Diffusion dynamics and synchronizability of hierarchical products of networks
• Efficient Learning-based Graph Simulation for Temporal Graphs