×

zbMATH — the first resource for mathematics

Synchronization in random networks with given expected degree sequences. (English) Zbl 1138.93050
Summary: Synchronization in random networks with given expected degree sequences is studied. We also investigate in details the synchronization in networks whose topology is described by classical random graphs, power-law random graphs and hybrid graphs when \(N \rightarrow \infty \). In particular, we show that random graphs almost surely synchronize. We also show that adding small number of global edges to a local graph makes the corresponding hybrid graph to synchronize.

MSC:
93D21 Adaptive or robust stabilization
37D45 Strange attractors, chaotic dynamics of systems with hyperbolic behavior
37N35 Dynamical systems in control
PDF BibTeX XML Cite
Full Text: DOI Link
References:
[1] Barabási, A.L., Linked: the new science of networks, (2002), Perseus Publishing Cambridge, Massachusetts
[2] Cohen, J.E.; Briand, F.; Newman, C.M., Community food webs: data and theory, (1990), Springer Berlin · Zbl 0719.92022
[3] Williams, R.J.; Martinez, N.D., Simple rules yield complex food webs, Nature, 404, 180-183, (2000)
[4] Broder, A.; Kumar, R.; Maghoul, F.; Raghavan, P.; Rajagopalan, S.; Stata, R., Graph structure in the web, Comput networks, 33, 309-320, (2000)
[5] Faloutsos, M.; Faloutsos, P.; Faloutsos, C., On power-law relationships of the Internet topology, Comput commun rev, 29, 4, 251-262, (1999)
[6] Watts, D.J.; Strogatz, S.H., Collective dynamics of ‘small-world’ networks, Nature, 393, 440-442, (1998) · Zbl 1368.05139
[7] Barabási, A.L.; Albert, R., Emergence of scaling in random networks, Science, 286, 509-512, (1999) · Zbl 1226.05223
[8] Albert, R.; Barabási, A.L., Statistical mechanics of complex networks, Rev mod phys, 74, 47-97, (2002) · Zbl 1205.82086
[9] Fujisaka, H.; Yamada, T., Stability theory of synchronized motion in coupled-oscillator systems, Progr theor phys, 69, 1, 32-47, (1983) · Zbl 1171.70306
[10] Strogatz, S., Sync: the emerging science of spontaneous order, (2003), Hyperion New York
[11] Wu, C.W.; Chua, L.O., Synchronization in an array of linearly coupled dynamical systems, IEEE trans circ syst I, 42, 430-447, (1995) · Zbl 0867.93042
[12] Wu, C.W., Synchronization in arrays of coupled chaotic circuits and systems: theory and applications, (), [chapter 23]
[13] Wu, C.W., Synchronization in arrays of coupled nonlinear systems: passivity, circle criterion, and observer design, IEEE trans circ syst I, 48, 1257-1261, (2001) · Zbl 0999.94577
[14] Wu, C.W., Synchronization in coupled chaotic circuits and systems, (2002), World Scientific Singapore · Zbl 1007.34044
[15] Wu, C.W., Synchronization in coupled arrays of chaotic oscillators with nonreciprocal coupling, IEEE trans circ syst I, 50, 294-297, (2003) · Zbl 1368.34051
[16] Wu, C.W., Perturbation of coupling matrices and its effect on the synchronizability in arrays of coupled chaotic systems, Phys lett A, 319, 495-503, (2003) · Zbl 1029.37018
[17] Pecora, L.; Carroll, T., Master stability functions for synchronized coupled systems, Phys rev lett, 80, 10, 2109-2112, (1998)
[18] Fink, K.S.; Johnson, G.; Carroll, T.; Mar, D.; Pecora, L., Three coupled oscillators as a universal probe of synchronization stability in coupled oscillator arrays, Phys rev E, 61, 5, 5080-5090, (2000)
[19] Barahona, M.; Pecora, L.M., Synchronization in small-world systems, Phys rev lett, 89, 5, (2002), 054101(1-4)
[20] Ott, E., Chaos in dynamical systems, (1993), Cambridge University Press Cambridge, UK · Zbl 0792.58014
[21] Wang, X.F.; Chen, G., Synchronization in scale-free dynamical networks: robustness and fragility, IEEE trans circ syst I, 49, 1, 54-62, (2002) · Zbl 1368.93576
[22] Nishikawa, T.; Motter, A.E.; Lai, Y-C.; Hoppensteadt, F.C., Heterogeneity in oscillator networks: are smaller worlds easier to synchronize?, Phys rev lett, 91, 014101, (2003)
[23] Li, X.; Chen, G., Synchronization and desynchronization of complex dynamical networks: an engineering viewpoint, IEEE trans circ syst I, 50, 11, 1381-1390, (2003) · Zbl 1368.37087
[24] Lu, J.; Yu, X.; Chen, G.; Cheng, D., Characterizing the synchronizability of small-world dynamical networks, IEEE trans circ syst I: regular papers, 51, 4, 787-796, (2004) · Zbl 1374.34220
[25] Zhou, C.; Motter, A.E.; Kurths, J., Universality in the synchronization of weighted random networks, Phys rev lett, 96, 034101, (2006)
[26] Belykh, V.N.; Belykh, I.V.; Hasler, M., Connection graph stability method for synchronized coupled chaotic systems, Physica D, 195, 159-187, (2004) · Zbl 1098.82622
[27] Belykh, I.V.; Belykh, V.N.; Hasler, M., Blinking model and synchronization in small-world networks with a time-varying coupling, Physica D, 195, 188-206, (2004) · Zbl 1098.82621
[28] Rugh, W.J., Linear system theory, (1996), Prentice Hall Upper Saddle River (NJ), USA · Zbl 0892.93002
[29] Checco, P.; Kocarev, L.; Maggio, G.M.; Biey, M., On the synchronization region in networks of coupled oscillators, Iscas, IV, 800-803, (2004)
[30] Stojanovski, T.; Kocarev, L.; Parlitz, U.; Harris, R., Sporadic driving of dynamical systems, Phys rev E, 55, 4035-4048, (1997)
[31] Madan, R.N., Chua’s circuit: a paradigm for chaos, (1993), World Scientific Singapore · Zbl 0861.58026
[32] Biggs, N., Algebraic graph theory, (1993), Cambridge University Press
[33] Chung, F., Spectral graph theory, (1997), AMS Publications
[34] Chung, F.; Lu, L.; Vu, V., The spectra of random graphs with given expected degrees, Proc natl acad sci, 100, 11, 6313-6318, (2003) · Zbl 1064.05138
[35] Erdös, P.; Rényi, A., On random graphs, Publ math debrecen, 6, 290-291, (1959)
[36] Bollobás, B., Graph theory: an introductory course, (1979), Springer-Verlag New York · Zbl 0411.05032
[37] Bollobás, B., Random graphs, (2001), Cambridge University Press Cambridge · Zbl 0997.05049
[38] Juvan, M.; Mohar, B., Laplace eigenvalues and bandwidth-type invariants of graphs, J. graph theory, 17, 393-407, (1993) · Zbl 0785.05077
[39] Bender, E.A.; Canfield, E.R., The asymptotic number of labelled graphs with given degree sequences, J combinat theory (A), 24, 296-307, (1978) · Zbl 0402.05042
[40] Molloy, M.; Reed, B., A critical point for random graphs with a given degree sequence, Rand struct algorith, 6, 2-3, 161-179, (1995) · Zbl 0823.05050
[41] Molloy, M.; Reed, B., The size of the giant component of a random graph with a given degree sequence, Combinat probab comput, 7, 3, 295-305, (1998) · Zbl 0916.05064
[42] Bollobás, B.; Riordan, O.; Spencer, J.; Tusnady, G., The degree sequence of a scale-free random graph process, Rand struct algorith, 18, 3, 279-290, (2001) · Zbl 0985.05047
[43] Kumar R, Raghavan P, Rajagopalan S, Sivakumar D, Tomkins A, Upfal E, Stochastic models for the web graph. In: Proceedings of the 41st annual symposium on foundations of computer science, 2000. p. 57-65.
[44] Aiello, W.; Chung, F.; Lu, L., Random evolution in massive graphs, (), 97-122 · Zbl 1024.68073
[45] Cooper C, Frieze A. A general model of web graphs. In: Proceedings of ESA 2001, 2001. p. 500-11. · Zbl 1006.68541
[46] Chung, F.; Lu, L., Connected components in random graphs with given expected degree sequences, Ann combinat, 6, 125-145, (2001) · Zbl 1009.05124
[47] Aiello W, Chung F, Lu L. A random graph model for massive graphs. In: Proceedings of the thirty-second annual ACM symposium on theory of computing, 2000. p. 171-80. · Zbl 1296.05172
[48] Fiedler, M., Algebraic connectivity of graphs, Czech math J, 23, 98, 298-305, (1973) · Zbl 0265.05119
[49] Mohar, B., Isoperimetric numbers of graphs, J combinat theo ser B, 47, 274-291, (1989) · Zbl 0719.05042
[50] Bollobás, B., The isoperimetric number of random regular graphs, Euro J combinat, 9, 241-244, (1988) · Zbl 0673.05086
[51] Chung, F.; Lu, L., The small world phenomenon in hybrid power law graphs, (), 91-106
[52] F. Chung, personal communication.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.