6 : 703?, [76 82],. [83 85],, [86 91]., (pinning control) [92 96].,,, [97 100], Laplace.,, [ ],, [ ], [ ], [129].,,,,,,.,, (scale-fr

Transcription

1 38 6 Vol. 38 No ADVANCES IN MECHANICS Nov. 25, 2008 *,, ,,,.,.,.,,..,,,,, 1 21 [1 7],..,,.,,,. 10, [8 21]., [22 28],,,,.,,, (scale-free) [8,9].,, [10 12,29 36], [8,9,37,38], [39 42]., [43 50] Huygens( ), [43 49].,, [50], [51 64], [54 64], [65,66], [67 69], [70 72], [73 75]., :,,,, Laplace,, : , : ( ) (107110) duanzs@pku.edu.cn

2 6 : 703?, [76 82],. [83 85],, [86 91]., (pinning control) [92 96].,,, [97 100], Laplace.,, [ ],, [ ], [ ], [129].,,,,,,.,, (scale-free)., Laplace,.,,, [11,12,130,131]., 1736,, Erdös Rényi [132],,,,., Laplace,, Laplace [ ],, [ ].. 2 N ẋ = f(x) (diffusively coupled dynamical network) ẋ i = f(x i ) c N a ij Γ (x j ), i = 1, 2,, N (1) j=1, f : D R n R n ( ), x i D i, c > 0, Γ : D R n, A = [a ij ] R N N,, j a ij = 0, i = 1, 2,, N, A,, (1). A Laplace, A, a ij = a ji = 1 i j (i j), a ij = a ji = 0 (i j), A N N a ii = a ij = a ji = k i, i = 1, 2,, N j=1 j i j=1 j i i., A,. A,, A 0 = λ 1 < λ 2 λ 3 λ N (2) [11,50,58,148],, Laplace,. Laplace,., (, α 1 ), A λ 2

3 λ 2,. (α 2, α 1 ), A λ 2 /λ N λ 2 /λ N,., λ 2 /λ N, λ 2 /λ N λ 2, λ 2 /λ N, r., Laplace. N G, d max d min, [135,142] G, 2d max λ N d max +1, d max +1 N 1, λ 2 d min N/(N 1). [151] G G c ( G G ), λ 2 λ 2 < d min. G G c, r(g) < d min /d max. e(g) G ( G ), λ 2 2e(G)(1 cos(π/n)), Praha [133] λ 2. D G ( ), l G, λ 2 4/(ND), 1/λ 2 0.5(N 1) l 0.25(N 2) [151].,, [80].,, B max, λ 2 [151] d max d 2 max (N/(B max + 2)) 2 λ 2 d max + d 2 max (N/(B max + 2)) 2 Comellas [151],. Duan [149],, 1 Γ 1. Γ 1 6 (bipartite) [135,149], [149] r(γ 1 ) 2/9. r(γ 1 )= / [149]. 1 Γ 1, r(γ 1) 2/9,, 2, 2 Γ 2 (community), 2 Γ 2 3 6, Γ 2 e{3, 6},, (Γ 2 e{3, 6}) c (bipartite), (Γ 2 e{3, 6}) c [136] v = (1/ 8, 1/ 8, 1/ 8, 1/ 8, 1/ 8, 1/ 8, 1/ 8, 1/ 8) T 2 Γ 2, r(γ 2) < 0.5/5, Γ 2 Γ 2 e{3, 6}, v λ 2 (Γ 2 ), Γ 2 Laplace L, Releigh, λ 2 (Γ 2 ) v T Lv = 0.5. Γ 2 5, r(γ 2 ) < 0.5/5. [149]., [11,33]. 3 ( 3). 3(a)(b)

4 6 : 705, 3;, 7/5;, 2., Laplace : λ 2 (G 1 )=3, λ 6 (G 1 )=6, r(g 1 )=0.5; λ 2 (G 2 )=2, λ 6 (G 2 )=5, r(g 2 )=0.4. G 1 G 2. (a) G 1 (b) G 2 3 3(a)(b) N = 2n(n > 1), G 1 2n bipartite [135,136,148], n, n, n >1 r(g 1 )=0.5; G 2 n,, [135,136] n, r(g 2 ) 0.,,. [76 82], 3(a)(b),, Atay [147],,., [135]. 1: N G, (2). G, G + e,,, λ i (G) λ i (G + e), i = 2,, N, λ 2, λ 2., 3(b) G 2 1, 3, G 2 + e{1,3},, r(g 2 + e{1,3})= < r(g 2 )=0.4,. 1, 4 r(g 2 + e{1,3}+e{1,4})= , r(g 2 +e{1,3}), r(g 2 ).,. G 1,, G 1 G 2, G c 1 G c 2. [135,136]. 2: N G, : (1) G λ N (G) λ N (G) N; (2) λ N (G) = N G c ; (3) G c q, λ N (G) = N G q 1 ; (4) λ i (G c ) + λ N i+2 (G) = N, i = 2,, N. 4(a)(b) G 1, G 2. 2 G 1 6. G 1,,, G 1,. G 1, G 1 3,, G 1, 4. G 1 G 2, [148].,? [150]. (a) G c 1 (b) G c 2 4 3: N 5 C N, r(c N + e) < r(c N ).

5 C 6, 5(a)(b). r(c 6 ) = 0.25, r(c 6 + e{1,3})= < C 6 + e{1,3}, C 6 + e{1,3} 5(c) C 6o, r(c 6o )= >r(C 6 )..,?, [150]., , Γ 3,,,,,. N, r,?. (a) C 6 (b) C 6 + e{1,3} (c) C 6o 5 4: G, r(g) < 2/5 = , Γ 3 ( 6), 0.4. Γ 3,. Donetti [78] 6 Γ 3, r(γ 3)=2/5=0.4,,,,,. Γ 4 ( 7, ), Γ 3, Γ 3 [150]. [80] 7 Γ 4, r(γ 4) = / < r(γ 3) = 2/5 4 Atay [146]., G H, G H, [135,146],, 3(b) G 2 C 3 P 2 ( 8). λ 2 (G H) = min{λ 2 (G), λ 2 (H)}, λ max (G H) = λ max (G) + λ max (H). C 3 P 2 G 2 ( 3(b)),, G 2 2n ( n P 2 ),. r(g H) < min {r(g), r(h)}. Duan [149].,. G H, G H, G H. 3 O 3, 3(a) G 1 O 3 O 3. G H

6 6 : 707 n, m, [135,146], λ 2 (G H)=min{λ 2 (G)+m,λ 2 (H)+n}, λ max (G H) = n + m. G H r(g H) 0.5. G 1 2n n.. 8 C 3 P 2 (coalescence), G H, G H, G H, λ 2 (G H) min {λ 2 (G), λ 2 (H)}, λ max (G H) max {λ max (G), λ max (H)}, r(g H) min {r(g), r(h)}.,. 9 Γ 5 P 4 ( 10) P 2 ( 8), 5 P 5 P 4 P 2. [146],,. [149] 1,. 9 Γ 5 5,. N,?,?,,,,,., [97 100],,,.?,,.,,, [83], [84,85]., [85,158]. multi-agent [ ],. multi-agent,,.,,, [22 27]., multi-agent,, [169,170]. [28,162] :.., P 4 2,.

7 ,. :, ,,,.., 2005, 22(4): , 2005, 2(1): Chua L O. CNN: A Paradigm for Complexity. Singapore: World Scientific, , 2003, 20(1): 1 3 7,,.., 2004, 1(2): Watts D J, Strogatz S H. Collective dynamics of smallworld networks. Nature, 1998, 393(6684): Barabási A L, Albert R. Emergence of scaling in random networks. Science, 1999, 286(5439): Barabási A L. The New Science of Networks. Massachusetts: Persus Publishing, ,,. :. :, ,.. :, Wang X F. Complex networks: Topology, dynamics, and synchronization. Int J of Bifurcation and Chaos, 2002, 5(12): Boccaletti S, Latora V, Moreno Y, et al. Complex networks: structure and dynamics. Physics Reports, 2006, 424: Dorogovtsev S N, Mendes J F F. Evolution of networks, Adv Phys, 2002, 51: Yuan B S, Wang B H. Growing directed networks: organization and dynamics. New Journal of Physics, 2007, 9: Albert R, Barabasi A L. Statistical mechanics of complex networks. Reviews of Modern Physics, 2002, 74: Costa L F, Rodrigues A, Travieso G, Villas Boas P R. Characterization of complex networks: A survey of measurements. Advances in Physics, 2007, 56(1): Newman M E J. The structure and function of complex networks. SIAM Review, 2003, 45: Strogatz S H. Exploring complex networks. Nature, 2001, 410: Wang X F, Chen G. Complex networks: small world, scale-free and beyond. IEEE Circuits and System Magazine, 2003, 3(1): Siljak D D. Decentralized Control of Complex Systems. New York: Academic, ,.. :, Ikeda M, Siljak D D, Yasuda K. Optimality of decentralized control for large scale systems. Automatica, 1983, 19: Shi Z C, Gao W B. Stabilization by decentralized control for large scale interconnected systems. Large Scale Systems, 1986, 10: :, Yang G H, Wang J L, Soh Y C. Decentrralized control of symmetric systems. Systems and Control Letters, 2001, 42: Duan Z S, Wang J Z, Chen G, Huang L. Stability analysis and decentralized control of a class of complex dynamical networks. Automatica, 2008, 44: Bianconi G, Gulbahce N, Motter A E. Local structure of directed networks. Phys Rev Lett, 2008, 100(11): Fang J Q, Li Y, Bi Q. From a harmonious unifying hybrid preferential model towards a large unifying hybrid network model. Int J Modern Physics B, 2007, 21(30): Fang J Q, Bi Q, Li Y, et al. Toward a harmonious unifying hybrid model for any evolving complex networks. Advances in Complex Systems, 2007, 10(2): Chen M, Yu B, Xu P, Chen J. A new deterministic complex network model with hierarchical structure. Phys A, 2007, 385: Fortunatoa S, Castellano C. Community structure in graphs. 2007, arxiv: Li X, Chen G. A local-world evolving network model. Physica A, 2003, 328: Zhang Z Z, Zhou S G, Fang L J, et al. Maximal planar scale-free Sierpinski networks with small worlds effect and power law strength-degree correlation. European Physics Letters, 2007, 79: Zhang Z Z, Zhou S G, Wang Z Y, Shen Z. A geometric growth model interpolating between regular and small-world networks. J Phys A: Math Theor, 2007, 40: Jezewski W. On the emergence of scaling in weighted networks, Phys A, 2007, 379: Nykter M, Price N D, Larjo A, et al. Critical networks exhibit maximal information diversity in structure-dynamics relationships. Phys Rev L, 2008, 100: Albert R, Jeong H, Barabasi A L. Attack and error tolerance in complex networks. Nature, 2000, 406: Callway D S, Newman M E J, Strogatz S H, Watts D J. Network robustness and fragility: Percolation on random graphs. Phys Rev Lett, 2000, 85(16): Lestas I C, Vinnicombe G. Scalable robust stability for nonsymmetric heterogeneous networks. Automatica, 2007, 43: Sun S W, Liu Z X, Chen Z Q, Yuan Z Z. Error and attack tolerance of evolving networks with local preferential attachment. Phys A, 2007, 373: Pikovsky A, Rossenblum M, Kurths J. Synchronization, A Uuniversal Concept in Nonlinear Sciences. New York: Cambridge University Press, 2001

8 6 : Strogatz S H, Stewart I. Coupled oscillators and biological synchronization. Scientific American, 1993, 12: Neda Z, Ravasz E, Vicsek T, et al. The sound of many hands clapping. Nature, 2000, 403: Blekhman I I. Synchronization in Science and Technology. ASME Press, Wu C W, Chua L O. Synchronization in an array of linearly coupled dynamical systems. IEEE Trans Circuits & Systems I, 1995, 42: Wu C W. Synchronization in Coupled Chaotic Circuits and Systems. Singapore: World Scientific, Ashwin P, Buescu J, Stewart I. Bubbling of attractors and synchronization of chaotic oscillators. Phys Lett A, 1994, 193: Pecora L M, Carroll T L. Master stability functions for synchronized coupled systems. Phys Rev Lett, 1998, 80(10): Arenas A, Afaz-Guilera A, Kurths J, et al. Synchronization in complex networks. Review of Modern Physics, 2008, doi: /j.physrep Guan S G, Wang X G, Li K, et al. Synchronizability of network ensembles with prescribed statistical properties. Chaos, 2008, 18(1): Boccaletti S, Kurths J, Osipov G, et al. The synchronization of chaotic systems. Physics Reports, 2002, 366(1-2): Barahona M, Pecora L M. Synchronization in small-world systems. Phys Rev Lett, 2002, 89(5): Belykh I V, Belykh V N, Hasler M. Blinking model and synchronization in small-world networks with a timevarying coupling. Physica D, 2004, 195: Checco P, Biey M, Kocarev L. Synchronization in random networks with given expected degree sequences. Chaos, Solitons & Fractals, 2008, 35(3): Hong H, Choi M Y, Kim B J. Synchronization on smallworld networks. Phys Rev E, 2002, 65: Lü J H, Yu X H, Chen G, Cheng D Z. Characterizing the synchronizability of small-world dynamical networks. IEEE Trans Circuits Syst-I, 2004, 51(4): Kocarev L, Amato P. Synchronization in power-law networks. Chaos, 2005, 15: Moreno Y, Pacheco A F. Synchronization of Kuramoto oscillators in scale-free networks. Europhysics Letters, 2004, 68: Wang X F, Chen G. Synchronization in scale-free dynamical networks: robustness and fragility. IEEE Trans Circuits Syst-I, 2002, 49(1): Gong B, Yang L, Yang K. Synchronization on Erdos-Renyi network. Phys Rev E, 2005, 72: Fan J, Wang X F. On synchronization in scale-free dynamical networks. Physica A, 2005, 349: Li C G, Chen G. Phase synchronization in small-world networks of chaotic oscillators. Physica A, 2004, 341: Jalan S, Amritkar R E. Self-organized and driven phase synchronization in coupled maps. Phys Rev Lett, 2003, 90(1): Ichinomiya T. Frequency synchronization in random oscillator network. Phys Rev E, 2004, 70: Li Z, Lee J. New eigenvalue based approach to synchronization in asymmetrically coupled networks. Chaos, 2007, 17: Chavez M, Hwang D U, Amann A, et al. Synchronization is enhanced in weighted complex networks. Phys Rev Lett, 2005, 94: Wu C W. Synchronization in networks of nonlinear dynamical systems via a directed graph. Nonlinearity, 2005, 18: Chen L, Lu J. Cluster synchronization in a complex dynamical network with two nonidentical clusters. J Syst Sci & Complexity, 2008, 21(1): Wu X, Wang B H, Zhou T, et al. Synchronizability of highly clustered scale-free networks. Chinese Phys Lett, 2006, 23: Ma Z J, Liu Z R, Zhang G. A new method to realize cluster synchronization in connected chaotic networks. Chaos, 2006, 16(2): Wang Q Y, Chen G, Lu Q S, Hao F. Novel criteria of synchronization stability in complex networks with coupling delays. Physica A, 2007, 378(2): Wang L, Dai H, Sun Y. Synchronization criteria for a generalized complex delayed dynamical network model. Physica A, 2007, 383(2): Li C G, Chen G. Synchronization in general complex dynamical networks with coupling delays. Physica A, 2004, 343: Belykh I V, Lange E, Hasler M. Synchronization of bursting neurons: what matters in the network topology. Phys Rev Lett, 2005, 94: Bernardo M D, Garofalo F, Sorrentino F. Effects of degree correlation on the synchronization of networks of oscillators. Int J of Bifurcation and Chaos, 2007, 17(10): Donetti L, Hurtado P I, Muñoz M A. Entangled networks, synchronization, and optimal network topology. Phys Rev Lett, 2005, 95: Gomez-Gardenes J, Moreno Y, Arenas A. Paths to synchronization on complex networks. Phys Rev Lett, 2007, 98: Hong H, Kim B J, Choi M Y. Park H.Factors that predict better synchronizability on complex networks. Phys Rev E, 2004, 69: Nishikawa T, Motter A E, Lai Y C. Hoppensteadt F C. Heterogeneity in oscillator netwroks: Are smaller worlds easier to synchronize? Phys Rev Lett, 2003, 91(1): Zhao M, Zhou T, Wang B H, et al. Relations between average distance, heterogeneity and network synchronizability. Physica A, 2006, 371(2):

9 Nishikawa T, Motter A E. Maximum peformance at minimum cost in network synchronization. Physica D, 2006, 224: Yang H, Zhao F, Wang B. Synchronizabilities of networks: A new index. Chaos, 2006, 16: Liu C, Duan Z S, Chen G, Huang L. L2-norm performance index of synchronization and optimal control synthesis of complex networks. 2007, arxiv: v1 86 Zhao M, Zhou T, Chen G, Wang B H. Enhancing the network synchronizability. Front Phys China, 2007, 2(4): Zhao M, Zhou T, Wang B H, Wang W-X. Enhance synchronizability by small structural perturbations. Phys Rev E, 2005, 72: Lu Y, Zhao M, Zhou T, Wang B. Enhanced synchronizability via age-based coupling. Phys Rev E, 2007, 76: Motter A E, Zhou C, Kurths J. Enhancing complexnetwork synchronization. Europhysics Letters, 2005, 69: Wang X, Lai Y, Lai C H. Enhancing synchronization based on complex gradient networks. Phys Rev E, 2007, 75: Xu D, Li Y, Wu T. Improving consensus and synchronizability of networks of coupled systems via adding links. Physica A, 2007, 382(2): Chen T P, Liu X W, Lu W L. Pinning complex networks by a single controller. IEEE Trans on Circuits and Systems-I, 2007, 54(6): Li X, Wang X F, Chen G. Pinning a complex dynamical network to its equilibrium. IEEE Trans. on Circuits and Systems-I, 2004, 51(10): Liu Z X, Chen Z Q, Yuan Z Z. Pinning control of weighted general complex dynamical networks with time delay. Phys A, 2007, 375: Wang X F, Chen G. Pinning control of scale-free dynamical networks. Phys A, 2002, 310: Li R, Duan Z S, Chen G. Cost and effects of pinning control for network synchronization. 2007, arxiv: v1 97 Stefaǹski A, Perlikowski P, Kapitaniak T. Ragged synchronizability of coupled oscillators. Phys Rev E, 2007, 75: Liu C, Duan Z S, Chen G, Huang L. Analyzing and controlling the network synchronization regions. Physica A, 2007, 386: Duan Z S, Chen G, Huang L. Disconnected synchronized regions of complex dynamical networks. 2007, arxiv: v1 100 Duan Z S, Chen G, Huang L. Synchronization of weighted networks and complex synchronized regions. Physics letters A, 2008, 372: Liu Z R, Luo J G. From lag synchronization to pattern formation in one-dimensional open flow models. Chaos Solitons & Fractals, 2006, 30(5): Bassett D S, Bullmore E. Small-world brain networks. Neuroscientist, 2006, 12: Couzin L, Collective minds. Nature, 2007, 445: Eguiluz V M, Dante R C, Guillermo A C, et al. Scale-free brain functional networks. Phy Rev Lett, 2005, 94: Hasegawa H. Synchronization in small-world networks of spiking neurons: Diffusive versus sigmoid couplings. Phys Rev E, 2005, 72: Motter A E, Gulbahce N, Almaas E, Barabási AL. Predicting synthetic rescues in metabolic networks. Molecular Systems Biology, 2008, 4 (168): Rossoni E, Chen Y H, Ding M Z, et al.. Stability of synchronous oscillations in a system of Hodgkin-Huxley neurons with delayed diffusive and pulsed coupling. Phys Rev E, 2005, 71: Wang Q Y, Lu Q S, Chen G, Guo D H. Chaos synchronization of coupled neurons with gap junction. Phys Lett A, 2006, Wang Q Y, Duan Z S, Huang L, Chen G, Lu Q S. Pattern formation and firing synchronization in networks of map neurons. New Journal of Physics, 2007, 9(383): Boguna M, Pastor-Satorras R. Epidemic spreading in correlated complex networks. Phys Rev E, 2002, 66(4): Boguna M, Pastorras R, Vespignani V. Absence of epidemic threshold in scale-free networks with degree correlations. Phys Rev Lett, 2003, 90(2): Cohen R, Havlin S, Avraham D. Efficient immunization strategies for computer networks and populations. Phys Rev Lett, 2003, 91(24): Moreno Y, Pastor-Satorras R, Vespignani A. Epidemic outbreaks in complex heterogeneous networks. Euro Phys J B, 2002, 26(4): Newman M E J. Spread of epidemic disease on networks. Phys Rev E, 2002, 66(1): Pastor-Satorras R, Vespignani A. Immunization of complex networks. Phys Rev E, 2002, 65(3): Wang J Z, Liu Z R, Xu J H. Epidemic spreading on uncorrelated heterogenous networks with non-uniform transmission. Physica A, 2007, 382: Guo W P, Li X, Wang X F. Epidemics and immunization on euclidean distance preferred small-world networks. Physica A, Shi H J, Duan Z S, Chen G. An SIS model with infective medium on complex networks. Physica A, 2008, 387: Cai S M, Yan G, Zhou T, et al. Scaling behavior of an artificial traffic model on scale-free networks. Phys Lett A, 2007, 366: Zhou T, Ren J, Medo M, Zhang Y. Bipartite network projection and personal recommendation. Phy Rev Lett, 2007, 76:

10 6 : Zhu C P, Zhou T, Yang H, et al. The process of coevolutionary competitive exclusion: speciation, multifractality and power-laws in correlations. New Journal of Physics, 2008, 10: Li P, Wang B H. Extracting hidden fluctuation patterns of Hang Seng stock index from network topologies. Phys A, 2007, 378: Xia Y, Hill D J. Attack vulnerability of complex communication networks. IEEE Trans Circuits and Systems II, 2008, 55(1): Xia Y, Tse C K, Lau F C, et al. Scale-free user-network approach to telephone network traffic analysis. Phy Rev Lett, 2005, 72: Akyildiz I F, Su W, Sanakarasubramaniam Y, et al. Wireless sensor networks: A survey. Computer Networks, 2002, 38(4): Dimakis A G, Sarwate A D, Wainwright M J. Geographic gossip: efficient averaging for sensor networks. IEEE Transactions on Signal Processing, 2008, 56(3): ,,.. :, Li Q, Rus D. Grobal clock synchronization in sensor networks. IEEE Trans on Computers, 2006, 55(2): da Fontoura Costa L, Oliveira Jr. O N, Travieso R, et al. Analyzing and modelling real-world phenomena: A survey of applications. 2007, arxiv: v1 130,,.., 2004, 34(4): West D B. Introduction to Graph Theory. NJ: Prentice Hall, Erdös P, Rényi A. On the evolution of random graphs. Publ Math Inst Hung Acad Sci, 1960, 5: Praha M F. Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 1973, 23(98): Pan Y L. Sharp upper bounds for the Laplacian graph eigenvalues. Linear Algebra and its Applications, 2002, 355: Merris R. Laplacian matrices of graph: a survey. Linear Algebra and its Applications, 1994, : Merris R. Laplacian graph eigenvectors. Linear Algebra and its Applications, 1998, 278: de Abreu N M M. Old and new results on algebraic connectivity of graphs. Linear Algebra and its Applications, 2007, 423: Comellas F, Gago S. Spectral bounds for the betweenness of a graph. Linear Algebra and its Applications, 2007, 423: Nikiforov V. Bounds on graph eigenvalues I. Linear Algebra and its Applications, 2007, 420: Nikiforov V. Eigenvalues and extremal degrees of graphs. Linear Algebra and its Applications, 2006, 419: Das K Ch. Sharp lower bounds on the Laplacian eigenvalues of trees. Linear Algebra and its Applications, 2004, 184: Biggs N. Algebraic Graph Theory. Second ed. Cambridge: Cambridge Mathematical Library, Wu C W, Chua L O. Application of graph theory to the synchronization in an array of coupled nonlinear oscillators. IEEE Trans Circuits & Systems-I, 1995, 42: Wu C W. Synchronizability of networks of chaotic systems coupled via a graph with a prescribed degree sequence. Phys Lett A, 2005, 346: Wu C W. Perturbation of coupling matrices and its effect on the synchronization in arrays of coupled chaotic systems. Phys Lett A, 2003, 319: Atay F M, Biyikoglu T. Graph operations and synchronization of complex networks. Phys Rev E, 2005, 72: Atay F M, Biyikoglu T, Jost J. Network synchronization: Spectral versus statistical properties. Physica D, 2006, 224: Duan Z S, Chen G, Huang L. Complex network synchronizability: Analysis and control. Physical Review E, 2007, 76: Duan Z S, Liu C, Chen G. Network synchronizability analysis: The theory of subgraphs and complementary graphs. Physica D, 2008, 237: Duan Z S, Liu C, Wang W X, Chen G. Are networks with more edges easier to synchronize? 2007, arxiv: v1 151 Comellas F, Gago S. Synchronizability of complex network. Journal of Physics A: Mathematical and Theoretical, 2007, 40: Zhou T, Yan G, Wang B H. Maximal planar networks with large clustering coefficient and power-law degree distribution. Physical Review E, 2005, 71: Jalili M, Rad A A, H M. Enhancing synchronizability of dynamical networks using the connection graph stability method. Int J Circ Theor Appl, 2007, 35(5-6): Belykh I V, Belykh V N, Hasler M. Connection graph stability method for synchronized coupled chaotic systems. Physica D, 2004, 195: Belykh I, Hasler M, Laurent M, Nijmeijer H. Synchronization and graph topology. Int J Bifurcation and Chaos, 2005, 15(11): Kim D H, Motter A E. Ensemble averageability in network spectra. Phys Rev Lett, 2007, 98: Motter A E. Bounding network spectra for network design. N J Phys, 2007, 9: :, Bauso D, Giarre L, Pesenti R. Non-linear protocols for optimal distributed consensus in networks of dynamic agents. Systems & Control Letters, 2006, 55: Fax J A, Murray R M. Information flow and cooperative control of vehicle formations. IEEE Trans Automatic

11 Control, 2004, 49(9): Jadbabaie A, Lin J, Morse A S. Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Trans Autom Contr, 2003, 48(6): Lafferriere G, Williams A, Caughman J, Veerman J J P. Decentralized control of vehicle formations. Systems and Control Letters, 2005, 54: Moreau L. Stability of multiagent systems with timedependent communication links. IEEE Trans Autom Contr, 2005, 50(2): Olfati-Saber R, Murray R M. Consensus problems in networks of agents with switching topology and time delays. IEEE Trans Autom Contr, 2004, 49(9): Porfiri M, Stilwell D J. Consensus seeking over random weighted directed graphs. IEEE Trans Autom Contr, 2007, 52(9): Ren W, Beard R W. Consensus seeking in multiagent systems under dynamically changing interaction topologies. IEEE Trans Autom Contr, 2005, 50(5): Ren W, Beard R W, Atkins E M. Information consensus in multivehicle cooperative control. IEEE Control Systems Magazine, 2007, 27(2): Xiao F, Wang L. State consensus for multi-agent systems with switching topologies and time-varying delays. Int J Control, 2006, 79(10): :, Yang G H, Zhang S Y. Structural properties of large-scale systems possessing similar structures. Automatica, 1995, 31(7): GRAPH THEORY AND COMPLEX NETWORKS * DUAN Zhisheng State Key Laboratory for Turbulence and Complex Systems, Department of Mechanics and Aerospace Engineering, College of Engineering, Peking University, Beijing , China Abstract In the past ten years, the fast development of complex network theory has provided a good support for the study of complexity and complex systems, since they describe clearly the important characteristics of complex systems, and show bright prospects in theory and applications. This paper presents mainly the application of graph theory to complex networks, especially to the synchronization problem of complex networks. First, its application to the estimations of smallest nonzero, largest eigenvalues and synchronizability index of certain graphs are commented, followed by the effects of subgraph and graph eigenvector in the estimation of synchronizability index. Furthermore, the complexity between the relationships of synchronizability and network structural parameters are discussed via two simple graphs, and the effects of complementary graph, edge-addition and graph operation on the synchronization of complex networks are elaborated. Finally, some possible development directions in complex networks are predicted from the viewpoint of graph and control theory. Keywords complex network, synchronization, graph theory, subgraph, complementary graph, graph operation The project supported by the National Natural Science Foundation of China ( ) and the Key Projects of Educational Ministry (107110) duanzs@pku.edu.cn