Chaos
Feedback | Help | Exit
Chaos
   
 
 
 
Previous Article
Efficient rewirings for enhancing synchronizability of dynamical networks
In this paper, we present an algorithm for optimizing synchronizability of complex dynamical networks. Starting with an undirected and unweighted network, we end up with an undirected and unweighted n...
Next Article
Cluster synchronization in oscillatory networks
Synchronous behavior in networks of coupled oscillators is a commonly observed phenomenon attracting a growing interest in physics, biology, communication, and other fields of science and technology. ...

Rewiring networks for synchronization

Chaos 18, 037105 (2008); doi:10.1063/1.2975842

Published 22 September 2008

You are not logged in to this journal. Log in

Aric Hagberg1 and Daniel A. Schult2
1Mathematical Modeling and Analysis, Theoretical Division, Los Alamos National Laboratory, Los Alamos, New Mexico 87545, USA
2Department of Mathematics, Colgate University, Hamilton, New York 13346, USA
We study the synchronization of identical oscillators diffusively coupled through a network and examine how adding, removing, and moving single edges affects the ability of the network to synchronize. We present algorithms which use methods based on node degrees and based on spectral properties of the network Laplacian for choosing edges that most impact synchronization. We show that rewiring based on the network Laplacian eigenvectors is more effective at enabling synchronization than methods based on node degree for many standard network models. We find an algebraic relationship between the eigenstructure before and after adding an edge and describe an efficient algorithm for computing Laplacian eigenvalues and eigenvectors that uses the network or its complement depending on which is more sparse. ©2008 American Institute of Physics
History: Received 25 May 2008; accepted 1 August 2008; published 22 September 2008
Permalink: http://link.aip.org/link/?CHAOEH/18/037105/1
BUY THIS ARTICLE   (US$28)
Download PDF (300 kB) View Cart

EDITORIALLY RELATED

  1. Comment on “Rewiring networks for synchronization” [Chaos 18, 037105 (2008)]
    Mahdi Jalili et al.
    Chaos 19, 028101 (2009)

KEYWORDS and PACS

Keywords
PACS
  • 05.45.Xt
    Synchronization; coupled oscillators (nonlinear dynamical systems)
  • YEAR: 2008

RELATED DATABASES


To view database links for this article,
you need to log in.
To view database links for this article,
you need to log in.

PUBLICATION DATA

ISSN:
1054-1500 (print)   1089-7682 (online)
Publisher:
AIP is a member of CrossRef AIP

REFERENCES (43)
View in Separate Window/Tab
For access to fully linked references, you need to log in. For access to fully linked references, you need to Log in.
  1. S. H. Strogatz, Sync: The Emerging Science of Spontaneous Order (Hyperion, New York, 2003).
  2. S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D.-U. Hwang, Phys. Rep. 424, 175 (2006).
  3. J. A. Acebrón, L. L. Bonilla, P. C. J. Vicente, F. Ritort, and R. Spigler, Rev. Mod. Phys. 77, 137 (2005).
  4. S. H. Strogatz, Physica D 143, 1 (2000).
  5. M. E. J. Newman, SIAM Rev. 45, 167 (2003).
  6. M. Barahona and L. M. Pecora, Phys. Rev. Lett. 89, 054101 (2002).
  7. L. M. Pecora and T. L. Carroll, Phys. Rev. Lett. 80, 2109 (1998).
  8. K. S. Fink, G. Johnson, T. Carroll, D. Mar, and L. Pecora, Phys. Rev. E 61, 5080 (2000).
  9. D. J. D. Earn, S. A. Levin, and P. Rohani, Science 290, 1360 (2000).
  10. L. M. Pecora, T. L. Carroll, G. A. Johnson, D. J. Mar, and J. F. Heagy, Chaos 7, 520 (1997).
  11. M. A. Aon, S. C. Cortassa, and B. O'Rourke, Biophys. J. 91, 4317 (2006).
  12. A. Schnitzler and J. Gross, Nat. Rev. Neurosci. 6, 285 (2005).
  13. W. Singer, Neuron 24, 49 (1999).
  14. T. Nishikawa, A. E. Motter, Y. C. Lai, and F. C. Hoppensteadt, Phys. Rev. Lett. 91, 014101 (2003).
  15. F. M. Atay, T. B[dotless i]y[dotless i]koğlu, and J. Jost, IEEE Trans. Circuits Syst., I: Regul. Pap. 53, 92 (2006).
  16. A. E. Motter, C. Zhou, and J. Kurths, Phys. Rev. E 71, 016116 (2005).
  17. F. M. Atay, T. B[dotless i]y[dotless i]koğlu, and J. Jost, Physica D 224, 35 (2006).
  18. D.-H. Kim and A. E. Motter, Phys. Rev. Lett. 98, 248701 (2007).
  19. S. Guan, X. Wang, K. Li, B.-H. Wang, and C.-H. Lai, Chaos 18, 013120 (2008).
  20. F. M. Atay and T. Biyikoğlu, Phys. Rev. E 72, 016217 (2005).
  21. C. Y. Yin, W. X. Wang, G. Chen, and B. H. Wang, Phys. Rev. E 74, 047102 (2006).
  22. J. G. Restrepo, E. Ott, and B. R. Hunt, Phys. Rev. Lett. 97, 094102 (2006).
  23. H. Sorrentino, G. di Bernardo, S. Huerta Cuéllar, and S. Boccaletti, Physica D 224, 123 (2006).
  24. A. Hagberg, P. J. Swart, and D. A. Schult, Phys. Rev. E 74, 056116 (2006).
  25. L. Donetti, P. I. Hurtado, and M. A. Muñoz, Phys. Rev. Lett. 95, 188701 (2005).
  26. R. M. Memmesheimer and M. Timme, Physica D 224, 182 (2006).
  27. T. Nishikawa and A. E. Motter, Physica D 224, 77 (2006).
  28. A. E. Motter, New J. Phys. 9, 182 (2007).
  29. B. Wang, T. Zhou, Z. L. Xiu, and B. J. Kim, Eur. Phys. J. B 60, 89 (2007).
  30. F. Sorrentino and E. Ott, Phys. Rev. Lett. 100, 114101 (2008).
  31. T. Nishikawa and A. E. Motter, Phys. Rev. E 73, 065106 (2006).
  32. J. G. Restrepo, E. Ott, and B. R. Hunt, Chaos 16, 015107 (2006).
  33. P. N. McGraw and M. Menzinger, Phys. Rev. E 75, 027104 (2007).
  34. D. Gfeller and P. D. L. Rios, Phys. Rev. Lett. 100, 174104 (2008).
  35. The Laplacian L=D−A, where D is a diagonal degree matrix and A is the adjacency matrix for the network. Alternatively the normalized Laplacian [script L]=I−D−1/2LD−1/2 is sometimes used. In both cases, networks with weighted edges can be considered. Appropriate adjustments to our analysis work for these models of connectivity and produce similar results.
  36. We denote the sorted Laplacian eigenvalues 0=lambda1<=lambda2<=…<=lambdan and corresponding eigenvectors v1,v2,…vN. The eigenvalue lambda1=0 corresponds to spatially uniform perturbations v1=[1,…,1].
  37. R. Merris, Linear Algebr. Appl. 198, 143 (1994).
  38. R. Merris, Linear Algebr. Appl. 278, 221 (1998).
  39. R. Grone, R. Merris, and V. S. Sunder, SIAM J. Math. Anal. 11, 218 (1990).
  40. B. Mohar, Graph Theory, Combinatorics, and Applications, edited by Y. Alavi, G. Chartrand, O. R. Oellermann, and A. J. Schwenk (Wiley, New York, 1991), Vol. 2, pp. 871.
  41. F. R. K. Chung, “Spectral Graph Theory,” Vol. 92 in Regional Conference Series in Mathematics (American Mathematical Society, New York, 1997).
  42. A. Ghosh and S. Boyd, “Growing well-connected graphs,” in Proceedings of the 45th IEEE Conference on Decision and Control (IEEE, San Diego, CA, 2006), pp. 6605–6611.
  43. Y. Saad, Numerical Methods for Large Eigenvalue Problems (Manchester University Press, Manchester, UK, 1992).

CITING ARTICLES
For access to citing articles, you need to log in.
For access to citing articles, you need to Log in.


Copyright © American Institute of Physics