Chaos Nameplat
  • Volume/Page
  • Keyword
  • DOI
  • Citation
  • Advanced
   
 
 
 

You Tube Flickr Twitter iResearch App Facebook

Your access to this publication is provided through the subscription of Hochschule Darmstadt. Library Welcome Message Help

Library Welcome Message Help

close

Attention, institutional online journal administrators: if the institution name printed in this screen message is incorrect, you can request a change by sending an email to librarynames@aip.org.

Please include your institutional account number, the account administrator's email address and the preferred online display name.

Chaos / Volume 20 / Issue 4 / REGULAR ARTICLES

FULL-TEXT OPTIONS:

Chaos 20, 043119 (2010); http://dx.doi.org/10.1063/1.3515170 (6 pages)

Rewiring dynamical networks with prescribed degree distribution for enhancing synchronizability

Majid Dadashi, Iman Barjasteh, and Mahdi Jalili

Department of Computer Engineering, Sharif University of Technology, Tehran 11365-8639, Iran

View MapView Map

(Received 6 August 2010; accepted 21 October 2010; published online 17 November 2010)

In this paper, we present an algorithm for enhancing synchronizability of dynamical networks with prescribed degree distribution. The algorithm takes an unweighted and undirected network as input and outputs a network with the same node-degree distribution and enhanced synchronization properties. The rewirings are based on the properties of the Laplacian of the connection graph, i.e., the eigenvectors corresponding to the second smallest and the largest eigenvalues of the Laplacian. A term proportional to the eigenvectors is adopted to choose potential edges for rewiring, provided that the node-degree distribution is preserved. The algorithm can be implemented on networks of any sizes as long as their eigenvalues and eigenvectors can be calculated with standard algorithms. The effectiveness of the proposed algorithm in enhancing the network synchronizability is revealed by numerical simulation on a number of sample networks including scale-free, Watts–Strogatz, and Erdős–Rényi graphs. Furthermore, a number of network’s structural parameters such as node betweenness centrality, edge betweenness centrality, average path length, clustering coefficient, and degree assortativity are tracked as a function of optimization steps.

© 2010 American Institute of Physics

Lead Paragraph

Synchronizability of dynamical networks—the ease with which a network of dynamical systems synchronizes its activity—has been heavily investigated in recent years.1 , 2 , 3 , 4 , 5 , 6 Often, synchronization refers to time-correlated activity between two or more dynamical systems.7 Synchronization is not defined uniquely and a particular definition is adopted for each type of application;8 however, complete (identical) synchronization8 , 9 , 10—the strongest type of synchronization—is the most frequent concept that scholars adopt for their studies related to network synchronization. A network’s ability in synchronizing the activity of the dynamical systems placed in its nodes is referred to as synchronizability. There are a number of measures quantifying the synchronizability of dynamical networks.1 The most frequent measure of synchronizability is the eigenratio,2 , 3 , 11 , 12 , 13 i.e., the largest eigenvalue of the Laplacian of the connection graph divided by the second smallest eigenvalue, which is stimulated by the master-stability-function formalism.4 , 5 Based on this synchronizability measure, network N1 is more synchronizable than network N2 , if for a larger range of parameters, it is possible to synchronize N1 as compared to N2, i.e., smaller eigenratio of N1 than N2. In many applications, it is desired to have a network with high degrees of synchronization properties.14 , 15 One of the ways that can enhance a network’s synchronizability is link rewiring, i.e., removing an edge and creating another one, provided that duplication of edges is prohibited.16 , 17 , 18 , 19 However, other constraints such as node-degree distribution can also be considered in the optimization process. In this paper, we take the eigenratio as the synchronizability indicator and propose an algorithm for enhancing the synchronizability, i.e., minimizing the eigenratio, provided that the degree distribution is preserved during the optimization process.

Article Outline

  1. INTRODUCTION
  2. REWIRINGS FOR ENHANCING THE SYNCHRONIZABILITY OF DYNAMICAL NETWORKS
    1. The eigenratio as a measure of synchronizability
    2. Efficient rewirings preserving the degree distribution
  3. SIMULATION RESULTS
  4. CONCLUSIONS AND DISCUSSION

RELATED DATABASES

Scopus

View This Record in Scopus

Web of Science

View this record in Web of Science

View Web of Science related articles

KEYWORDS and PACS

Keywords

complex networks, eigenvalues and eigenfunctions, nonlinear dynamical systems, numerical analysis, synchronisation

PACS

  • 05.45.Xt

    Synchronization; coupled oscillators

  • 89.75.Hc

    Networks and genealogical trees

  • 02.60.Cb

    Numerical simulation; solution of equations

ARTICLE DATA

Digital Object Identifier
http://dx.doi.org/10.1063/1.3515170

PUBLICATION DATA

ISSN

1054-1500 (print)  
1089-7682 (online)

Publisher

$abstract.society.value is a Member of CrossRef American Institute of Physics

    References

  1. M. Jalili and A. Ajdari Rad, Int. J. Nonlinear Sci. Numer. Simul. 10, 1381 (2009).
  2. T. Nishikawa, A. E. Motter, Y. -C. Lai, and F. C. Hoppensteadt, Phys. Rev. Lett. 91, 014101 (2003). [MEDLINE]
  3. M. Chavez, D. -U. Hwang, A. Amann, H. G. E. Hentschel, and S. Boccaletti, Phys. Rev. Lett. 94, 218701 (2005). [MEDLINE]
  4. M. Barahona and L. M. Pecora, Phys. Rev. Lett. 89, 054101 (2002). [MEDLINE]
  5. L. M. Pecora and T. L. Carroll, Phys. Rev. Lett. 80, 2109 (1998).
  6. A. Arenas, A. Díaz-Guilera, J. Kurths, Y. Moreno, and C. Zhou, Phys. Rep. 469, 93 (2008).
  7. A. Pikovsky and Y. L. Maistrenko, Synchronization: Theory and Application (Kluwer Academic, Dordrecht, 2003).
  8. R. Brown and L. Kocarev, Chaos 10, 344 (2000)CHAOEH000010000002000344000001. [MEDLINE]
  9. S. Boccaletti, J. Kurths, G. Osipov, D. L. Valladares, and C. S. Zhou, Phys. Rep. 366, 1 (2002).
  10. S. Guan, X. Wang, Y. -C. Lai, and C. -H. Lai, Phys. Rev. E 77, 046211 (2008).
  11. L. Donetti, F. Neri, and M. A. Munoz, J. Stat. Mech.: Theory Exp. 8, P08007 (2006).
  12. A. E. Motter, C. Zhou, and J. Kurths, Phys. Rev. E 71, 016116 (2005).
  13. X. Wang, Y. -C. Lai, and C. H. Lai, Phys. Rev. E 75, 056205 (2007). [ISI]
  14. G. Korniss, M. A. Novotny, H. Guclu, Z. Toroczkai, and P. A. Rikvold, Science 299, 677 (2003). [MEDLINE]
  15. S. Barbarossa and G. Scutari, IEEE Trans. Signal Process. 55, 3456 (2007).
  16. A. Ajdari Rad, M. Jalili, and M. Hasler, Chaos 18, 037104 (2008)CHAOEH000018000003037104000001. [MEDLINE]
  17. A. Hagberg and D. A. Schult, Chaos 18, 037105 (2008)CHAOEH000018000003037105000001. [MEDLINE]
  18. M. Jalili and A. Ajdari Rad, Chaos 19, 028101 (2009)CHAOEH000019000002028101000001. [MEDLINE]
  19. L. Donetti, P. I. Hurtado, and M. A. Munoz, Phys. Rev. Lett. 95, 188701 (2005). [MEDLINE]
  20. G. Buzsáki, Rhythms of the Brain (Oxford University Press, New York, 2006).
  21. A. Pikovsky, M. Rosenblum, and J. Kurths, Synchronization: A Universal Concept in Nonlinear Sciences (Cambridge University Press, Cambridge, England, 2003).
  22. T. Nishikawa and A. E. Motter, Physica D 224, 77 (2006).
  23. M. Jalili, A. Ajdari Rad, and M. Hasler, IEEE International Symposium on Circuits and Systems, 2008, p. 2522.
  24. C. Zhou, A. E. Motter, and J. Kurths, Phys. Rev. Lett. 96, 034101 (2006). [MEDLINE]
  25. R. Olfati-Saber, J. A. Fax, and R. M. Murray, Proc. IEEE 95, 215 (2007).
  26. W. Singer, Annu. Rev. Physiol. 55, 349 (1993). [MEDLINE]
  27. W. Singer, Neuron 24, 49 (1999). [ISI] [MEDLINE]
  28. P. J. Uhlhaas and W. Singer, Neuron 52, 155 (2006). [MEDLINE]
  29. A. E. Motter, C. S. Zhou, and J. Kurths, Europhys. Lett. 69, 334 (2005).
  30. L. Donetti, P. I. Hurtado, and M. A. Munoz, J. Phys. A: Math. Theor. 41, 224008 (2008).
  31. L. M. Pecora and T. L. Carroll, Phys. Rev. Lett. 64, 821 (1990). [MEDLINE]
  32. M. Chen, IEEE Trans. Circuits Syst., I: Fundam. Theory Appl. 55, 1335 (2008).
  33. C. Zhou and J. Kurths, Phys. Rev. Lett. 96, 164102 (2006). [MEDLINE]
  34. J. -F. Zhu, M. Zhao, W. Yu, C. Zhou, and B. -H. Wang, Phys. Rev. E 81, 026201 (2010).
  35. H. Hong, B. J. Kim, M. Y. Choi, and H. Park, Phys. Rev. E 69, 067105 (2004). [MEDLINE]
  36. K. Li, M. Small, K. Wang, and X. Fu, Phys. Rev. E 79, 067201 (2009).
  37. B. Hao, H. Yu, Y. Jing, and S. Zhang, Physica A 388, 1939 (2009). [Inspec]
  38. H. Hong, M. Y. Choi, and B. J. Kim, Phys. Rev. E 65, 026139 (2002).
  39. X. F. Wang and G. Chen, IEEE Trans. Circuits Syst., I: Regul. Pap. 49, 54 (2002).
  40. X. F. Wang and G. Chen, Int. J. Bifurcation Chaos Appl. Sci. Eng. 12, 187 (2002).
  41. B. Wang, H. Tang, C. Guo, Z. Xiu, and T. Zhou, Physica A 368, 607 (2006).
  42. A. Ghosh and S. Boyd, IEEE Conference on Decision and Control, 2006, p. 6605.
  43. Y. Gu and J. Sun, Physica A 388, 3261 (2009). [Inspec]
  44. G. Davidoff, P. Sarnak, and A. Valette, Elementary Number Theory, Group Theory and Ramanujan Graphs (Cambridge University Press, Cambridge, England, 2003).
  45. T. J. P. Penna, Phys. Rev. E 51, R1 (1995). [MEDLINE]
  46. D. J. Watts and S. H. Strogatz, Nature (London) 393, 440 (1998). [MEDLINE]
  47. F. Sorrentino, M. di Bernardo, G. H. Cuéllar, and S. Boccaletti, Physica D 224, 123 (2006). [Inspec]
  48. F. Sorrentino, M. Di Bernardo, and F. Garofalo, Int. J. Bifurcation Chaos Appl. Sci. Eng. 17, 2419 (2007).
  49. J. W. Demmel, Applied Numerical Linear Algebra (SIAM, Philadelphia, 1997).
  50. U. Brandes, J. Math. Sociol. 25, 163 (2001).

View Scopus articles citing this one (2) Scopus Help

Figures (click on thumbnails to view enlargements)

FIG.1
The eigenratio λN/λ2 as a function of iteration steps for scale-free, Watts–Strogatz, and Erdős–Rényi networks. The scale-free networks are with N = 500, m = 2, and B = 0; the Watts–Strogatz networks are with N = 500, m = 2, and P = 0.5; and the Erdős–Rényi networks are with N = 500 and P = 0.07. The optimization target is to minimize the eigenratio λN/λ2 with the constraint of fixed degree distribution during the optimization process. Data are averaged over ten realizations.

FIG.1 Download High Resolution Image (.zip file) | Export Figure to PowerPoint

FIG.2
Profile of (a) maximum node betweenness centrality (MaxNBC), (b) maximum edge betweenness centrality (MaxEBC), (c) variance of node betweenness centrality (VarNBC), and (d) variance of edge betweenness centrality (VarEBC) as a function of iteration steps. The network parameters and optimization process are as in Fig. 1.

FIG.2 Download High Resolution Image (.zip file) | Export Figure to PowerPoint

FIG.3
Profile of (a) average path length and (b) clustering coefficient as a function of iteration steps. The network parameters and optimization process are as in Fig. 1.

FIG.3 Download High Resolution Image (.zip file) | Export Figure to PowerPoint

FIG.4
Profile of degree-degree correlation as a function of iteration steps. The network parameters and optimization process are as in Fig. 1.

FIG.4 Download High Resolution Image (.zip file) | Export Figure to PowerPoint



Close

Google Calendar

ADVERTISEMENT

Your Recent History Recent History Help

Recently Viewed

  1. Rewiring dynamical networks with prescribed degree distribution for enhancing synchronizability
  2. Efficient rewirings for enhancing synchronizability of dynamical networks
Go to AIP Home
Copyright © 2013 American Institute of Physics
close