Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Synchronization&--44; small worlds and algebraic graph theory

The analysis and design of networks draws from a long history, especially in the context of communications, transportation, and computer technology. Traditional graph-theoretical analyses have focused on static properties, but recent applications in physics, computer networks and biology have prompted a re-examination of graph properties in the light of the dynamical processes taking place on the network. However, the intuitive connection between graph structure and collective dynamics is difficult to pinpoint mathematically. For instance, networks of neurons, computers or people are often based on a strong backbone of local connections which leads to large distances between arbitrary nodes. Watts and Strogatz have shown that very few random, long-range connections produce a ‘small-world’ where distances are drastically reduced. But what about the collective behavior of a network made up of individuals with their own dynamics, like circuits or neurons? The conjecture is that small-worlds would lead to easier synchronization of the individual elements, if that were part of their dynamical behavior. In this talk, we will look at the dynamical implications of the small-world phenomenon for the generic synchronization of oscillator networks of arbitrary topology. By linking the linear stability of the synchronous state to an algebraic condition of the Laplacian matrix of the network, we show numerically and analytically how the addition of random shortcuts translates into improved network synchronizability. Applied to networks with few local connections, the small-world route produces synchronizability more efficiently than purely random graphs, various standard deterministic graphs, and ideal constructive schemes such as hypercubes. We also find that the small-world property does not guarantee synchronizability; this shows that the distance (a static property of the graph) is not a good measure of the synchronization properties of a network.
Type of Seminar:
Public Seminar
Dr. Mauricio Barahona
Dept of Bioengineering Bagrit Centre Imperial College London South Kensington Campus London SW7 2BX - UK
Feb 03, 2003   17:15

ETH Zentrum, Gloriastrasse 35, Building ETZ, Room E9
Contact Person:

Prof. P.Parrilo
File Download:

Request a copy of this publication.
Biographical Sketch:
Dr. Mauricio Barahona is a lecturer in the Dept of Bioengineering at Imperial College London. He obtained a PhD in Theoretical Physics (Condensed Matter and Dynamical Systems) from MIT under the supervision of Steve Strogatz (Mathematics) and Mehran Kardar (Physics). His thesis dealt with the spatio-temporal dynamics of arrays of Josephson junctions—superconducting electronic devices which can be described as coupled nonlinear oscillators. Concurrently, he developed algorithms for sensitive nonlinear data analysis. He then conducted postdoctoral research at Stanford University and the California Institute of Technology. At Stanford, he worked on generic properties of array synchronization with applications to pattern detection. In the Department of Control and Dynamical Systems at Caltech, he concentrated on rigorous bounds of model reduction techniques, and on the analysis of network dynamics using graph-theoretical concepts. He is broadly interested in mathematical applications in biomedical, physical and engineering systems.