A Arenas et aL / Physics Reports 469(2008)93-153 the entrainment breaks down at a value that depends exponentially on the depth of the network. this result also holds for other complex networks, as for instance in WS or SF networks, although the analytical explanation is only valid for ER networks 3. 2. Pulse-coupled models In parallel to the studies described so far, some other approaches to synchronization in networks have invoked models where the interaction between units takes the form of a pulse. In particular, much attention has been devoted to models akin to reproduce the dynamics of neurons, e.g. integrate-and-fire oscillators(IFOs). The basics of an IFO system is as follows. The phase dynamics of any oscillator i is linear in time doi (t)/dt= 1 in absence of external perturbations. However, when the oscillator i reaches the threshold i (t)= 1 it sends a signal (or pulse) to the rest of the oscillators to which it is connected and relaxes to i(t)=0. The pulse can be considered to propagate instantaneously or with a certain time delay t, and when it reaches other oscillators induces a phase jump i-j+A(i). The effects of the topology on the synchronization phenomena emerging in a network of IFOs are at least as rich as those presented in Section 3. 1, although far more difficult to revealed analytically. The main problem here is that the dynamics presents discontinuities in the variable states that are difficult to deal with. Nevertheless, many insights are recovered from direct simulations and clever mappings of the system. From direct simulations the first insights pointed directly to certain scaling relations between the synchronization time and topological parameters of networks. In ER networks, the scaling relation between the time needed to achieve complete synchronization T, the number of nodes N, and the number of links M, was found to be T (42) with a= 1.30(5)and B= 1.50(5). Comparing this synchronization process with the same system on a regular square lattice, one realizes that the time needed to synchronize a random network is larger, especially in sparse networks (64 In between these two extremal topologies, some wS networks with a rewiring probability p were studied and were found to expand the synchronization time more than the original regular lattice. However, it was first pointed out that ar ppropriate normalization of the pulses received by each oscillator, rescales the time to very short values. This phenomenon of normalization of the total input signal received by each oscillator has been repeatedly used to homogenize the dynamics in heterogeneous substrates. FOs in Sw networks were revisited later in [65 to study the possibility of self-sustained activity induced by the topology itself. Considering a unidirectional ring of IFOs with density p of random long-range directed connections, the authors showed that periodical patterns persist at low values of p, while long-transients of disordered activity patterns are observed for high values of p. Responsible for this behavior is a tradeoff between the average path length and the speed of activity propagation. For low p configurations, the distances in the networks decrease logarithmically with size, while the superposition of activities is almost the same than in the regular configuration, i.e. the same activity occurs but in a"smaller" network able to self-sustain its excitation. However for large p, the superposition of activity between excited domains also plays an important role, and then both effects make the synchronized self-sustained activity collapse, leading to disordered In [66], networks of nonidentical Hodgkin-Huxley [67] elements coupled by excitatory synapses in random, regular nd Sw topologies, were investigated for the first time. The parameters of the model neurons were kept to stay below the bifurcation point, until the input arrives and forces the system to undergo a saddle-node bifurcation on a limit cycle. The dynamics of the system ends up in a coherent oscillation or in the activation of asynchronous states. In absence of a detailed analysis of the mechanism that generates coherence, the simulations showed several effects of the topology on the dynamics. he most interesting of which is that achieving synchronization in regular networks takes longer compared to sw, where the existence of short-cuts favors faster synchronization. The results obtained in all cases show that the randomness of the topology has strong effects on the dynamics of these models, in particular the average connectivity is a control parameter for the transition between asynchronous and synchronous states In Fig. 5 we present a phase diagram for the Hodgkin-Huxley model in SW networks with varying average degree k)and rewiring probability p. a detailed analysis of sparse random networks of general IFOs was exposed in[ 68]. Their analytic results are in agreement with the previous observations. Very recently [69 a SW network of non-identical Hodgkin-Huxley units in which some of the couplings could be negative was nalyzed they surprisingly found that a small fraction of such phase-repulsive links can enhance synchronization. In a slightly different scenario [70 a system of pulse-coupled Bonhoeffer-van der pol-FitzHugh-Nagumo oscillators [71 in WS networks was studied numerically. This study reports a major influence of the average path length of the network on the degree of synchronization, whereas local properties characterized by clustering and loop coefficients seem to play a inor role. In any case, the authors warn that the results are far from being conclusive, since single characteristics of the network are not easily isolated We will come back to this issue in the next section, when dealing with the stability of the synchronized state. The works reviewed so far in this subsection are based on the assumption that the coupling is fixed, and that the only ource of topological complexity is embedded in the connectivity matrix. The authors in [72] showed that for networks of pulse-coupled oscillators with complex connectivity, coupling heterogeneity induces periodic firing patterns, which replace
108 A. Arenas et al. / Physics Reports 469 (2008) 93–153 the entrainment breaks down at a value that depends exponentially on the depth of the network. This result also holds for other complex networks, as for instance in WS or SF networks, although the analytical explanation is only valid for ER networks. 3.2. Pulse-coupled models In parallel to the studies described so far, some other approaches to synchronization in networks have invoked models where the interaction between units takes the form of a pulse. In particular, much attention has been devoted to models akin to reproduce the dynamics of neurons, e.g. integrate-and-fire oscillators (IFOs). The basics of an IFO system is as follows. The phase dynamics of any oscillator i is linear in time dφi(t)/dt = 1 in absence of external perturbations. However, when the oscillator i reaches the threshold φi(t) = 1 it sends a signal (or pulse) to the rest of the oscillators to which it is connected, and relaxes to φi(t) = 0. The pulse can be considered to propagate instantaneously or with a certain time delay τ , and when it reaches other oscillators induces a phase jump φj → φj + ∆(φj). The effects of the topology on the synchronization phenomena emerging in a network of IFOs are at least as rich as those presented in Section 3.1, although far more difficult to be revealed analytically. The main problem here is that the dynamics presents discontinuities in the variable states that are difficult to deal with. Nevertheless, many insights are recovered from direct simulations and clever mappings of the system. From direct simulations the first insights pointed directly to certain scaling relations between the synchronization time and topological parameters of networks. In ER networks, the scaling relation between the time needed to achieve complete synchronization T , the number of nodes N, and the number of links M, was found to be T N2α−β ∼ M N2 α , (42) with α = 1.30(5) and β = 1.50(5). Comparing this synchronization process with the same system on a regular square lattice, one realizes that the time needed to synchronize a random network is larger, especially in sparse networks [64]. In between these two extremal topologies, some WS networks with a rewiring probability p were studied and were found to expand the synchronization time more than the original regular lattice. However, it was first pointed out that an appropriate normalization of the pulses received by each oscillator, rescales the time to very short values. This phenomenon of normalization of the total input signal received by each oscillator has been repeatedly used to homogenize the dynamics in heterogeneous substrates. IFOs in SW networks were revisited later in [65] to study the possibility of self-sustained activity induced by the topology itself. Considering a unidirectional ring of IFOs with density p of random long-range directed connections, the authors showed that periodical patterns persist at low values of p, while long-transients of disordered activity patterns are observed for high values of p. Responsible for this behavior is a tradeoff between the average path length and the speed of activity propagation. For low p configurations, the distances in the networks decrease logarithmically with size, while the superposition of activities is almost the same than in the regular configuration, i.e. the same activity occurs but in a ‘‘smaller’’ network able to self-sustain its excitation. However for large p, the superposition of activity between excited domains also plays an important role, and then both effects make the synchronized self-sustained activity collapse, leading to disordered patterns. In [66], networks of nonidentical Hodgkin–Huxley [67] elements coupled by excitatory synapses in random, regular, and SW topologies, were investigated for the first time. The parameters of the model neurons were kept to stay below the bifurcation point, until the input arrives and forces the system to undergo a saddle-node bifurcation on a limit cycle. The dynamics of the system ends up in a coherent oscillation or in the activation of asynchronous states. In absence of a detailed analysis of the mechanism that generates coherence, the simulations showed several effects of the topology on the dynamics, the most interesting of which is that achieving synchronization in regular networks takes longer compared to SW, where the existence of short-cuts favors faster synchronization. The results obtained in all cases show that the randomness of the topology has strong effects on the dynamics of these models, in particular the average connectivity is a control parameter for the transition between asynchronous and synchronous states. In Fig. 5 we present a phase diagram for the Hodgkin–Huxley model in SW networks with varying average degree hki and rewiring probability p. A detailed analysis of sparse random networks of general IFOs was exposed in [68]. Their analytic results are in agreement with the previous observations. Very recently [69], a SW network of non-identical Hodgkin–Huxley units in which some of the couplings could be negative was analyzed; they surprisingly found that a small fraction of such phase-repulsive links can enhance synchronization. In a slightly different scenario [70] a system of pulse-coupled Bonhoeffer–van der Pol–FitzHugh–Nagumo oscillators [71] in WS networks was studied numerically. This study reports a major influence of the average path length of the network on the degree of synchronization, whereas local properties characterized by clustering and loop coefficients seem to play a minor role. In any case, the authors warn that the results are far from being conclusive, since single characteristics of the network are not easily isolated. We will come back to this issue in the next section, when dealing with the stability of the synchronized state. The works reviewed so far in this subsection are based on the assumption that the coupling is fixed, and that the only source of topological complexity is embedded in the connectivity matrix. The authors in [72] showed that for networks of pulse-coupled oscillators with complex connectivity, coupling heterogeneity induces periodic firing patterns, which replace
A Arenas et aL/Physics Reports 469(2008)93-153 109 5.5 4 log p (clear)and nonoscillatory (dark] activity of the network in the(k, p) plane. The island that ght side indicates that the sw(fo range of values of k)is the only regime capable of producing fast coherent oscillations in the the state of global synchrony The coupling heterogeneity has a critical value from which the periodic firing patterns become nchronous aperiodic states. These results are in agreement with the observations described in previous works and allow us to state that a certain degree of complexity in the interaction between pulse coupled oscillators is needed to observe regular (or ordered)patterns. However, once a critical level of complexity is surpassed, asynchronous aperiodic states dominate the dynamic phenomena. 3.3. Coupled maps Maps represent simple realizations of dynamical systems exhibiting chaotic behavior. At first sight they can represent discrete versions of continuous oscillators Coupled populations of such rather simple dynamical systems have been one of the paradigmatic models to explain the emergence and self-organization in complex systems due to the rich variety of global qualitative behavior to which they give rise From a more practical point of view coupled map systems have found a widespread range of applications, ranging from fluid dynamics and turbulence to stock markets or ecological systems [1] Since these systems are nowadays known to have complex topologies, populations of maps coupled through a complex pattern of interactions are natural candidates to study the onset of synchronization as an overall characteristic of the population. t. Coupled maps have been widely analyzed in regular lattices, trees and also in global connectivity schemes. The first tempt to consider connectivities in between these extreme cases is done [73. He proposed a system formed by units, whose individual dynamics are given by the logistic map, that are connected to a fixed number k of other units randomly chosen(multiple and self-links are permitted). The evolution rule for the units is x(+1)=∑(() (43) A linear stability analysis of this system is performed in terms of the eigenvalues of the matrix A For the logistic map it is shown that for k 4 the maps synchronize. The time the system needs to synchronize decreases with the connectivity k and also with the system size although in the latter case the time saturates for large values of the system size. when the connectivity pattern is changed to a modified wS model(by adding long-range short-cuts but not rewiring). the authors in [74 showed that just a nonzero value of the addition probability is enough to guarantee synchronization in the thermodynamic limit. In another early attempt to include non-regular topologies in chaotic dynamics [75, a Sw network was analyzed, in B(t+1)=(1-a)f((t)+ ai;f(@ (t) (44) where K is the number of shortcuts in the network, and o the coupling constant. Each unit evolves according to a sine-circle map[76] f()=6+g_ sin(2t0)(mod 1)
A. Arenas et al. / Physics Reports 469 (2008) 93–153 109 Fig. 5. Phase diagram which shows the regions of oscillatory (clear) and nonoscillatory (dark) activity of the network in the (k, p) plane. The island that appears on the right side indicates that the SW (for some range of values of k) is the only regime capable of producing fast coherent oscillations in the average activity after the presentation of the stimulus. From [66]. the state of global synchrony. The coupling heterogeneity has a critical value from which the periodic firing patterns become asynchronous aperiodic states. These results are in agreement with the observations described in previous works and allow us to state that a certain degree of complexity in the interaction between pulse coupled oscillators is needed to observe regular (or ordered) patterns. However, once a critical level of complexity is surpassed, asynchronous aperiodic states dominate the dynamic phenomena. 3.3. Coupled maps Maps represent simple realizations of dynamical systems exhibiting chaotic behavior. At first sight they can represent discrete versions of continuous oscillators. Coupled populations of such rather simple dynamical systems have been one of the paradigmatic models to explain the emergence and self-organization in complex systems due to the rich variety of global qualitative behavior to which they give rise. From a more practical point of view coupled map systems have found a widespread range of applications, ranging from fluid dynamics and turbulence to stock markets or ecological systems [1]. Since these systems are nowadays known to have complex topologies, populations of maps coupled through a complex pattern of interactions are natural candidates to study the onset of synchronization as an overall characteristic of the population. Coupled maps have been widely analyzed in regular lattices, trees and also in global connectivity schemes. The first attempt to consider connectivities in between these extreme cases is done [73]. He proposed a system formed by units, whose individual dynamics are given by the logistic map, that are connected to a fixed number k of other units randomly chosen (multiple and self-links are permitted). The evolution rule for the units is xi(t + 1) = 1 k X j aijf xj(t) . (43) A linear stability analysis of this system is performed in terms of the eigenvalues of the matrix A. For the logistic map it is shown that for k > 4 the maps synchronize. The time the system needs to synchronize decreases with the connectivity k and also with the system size, although in the latter case the time saturates for large values of the system size. When the connectivity pattern is changed to a modified WS model (by adding long-range short-cuts but not rewiring), the authors in [74] showed that just a nonzero value of the addition probability is enough to guarantee synchronization in the thermodynamic limit. In another early attempt to include non-regular topologies in chaotic dynamics [75], a SW network was analyzed, in which θi(t + 1) = (1 − σ )f (θi(t)) + σ 4 + κ XN j=1 aijf θj(t) , (44) where κ is the number of shortcuts in the network, and σ the coupling constant. Each unit evolves according to a sine-circle map [76] f(θ ) = θ + Ω − K 2π sin(2πθ ) (mod 1), (45)
110 A Arenas et aL / Physics Reports 469(2008)93-153 hich provides a simple example for describing the dynamics of a phase oscillator perturbed by a time-periodic force. here K is a constant related to the external force amplitude and0<$2< 1 is the ratio between the natural oscillator frequency and the forcing frequency. It is observed that synchronization, in terms of a pa related to the winding number dispersion is induced by long-range coupling in a system that, in the absence of the shortcuts, does not synchronize a slightly different approach was conducted in [7]. who considered a population of units evolving according to x(+1)=(1-o)(x()+∑f() They obtain the stability condition of the synchronized state in terms of the eigenvalues of the normalized laplacian matrix (&- ai/ki)and the Lyapunov exponent of the map f(x). Furthermore, they also find a sufficient condition for the system to synchronize independently of the initial conditions, namely where A2 is the smallest non-zero eigenvalue of the normalized Laplacian matrix. They demonstrate their results for regular onnectivity patterns as global coupling and one-dimensional rings with a varying number of nearest neighbors, since in these cases the eigenvalues can be computed analytically Complexity in the connectivity pattern is introduced in different ys. In these cases one needs numerical estimates of the eigenvalues to compare the synchronization condition(47)with the simulation of the model(46). By using a quadratic map f(x)=l-ax[76 and choosing the free parameter a in a range where different regimes are realized, they find that in a random network the system synchronizes for an arbitrary large number of units, whenever the number of neighbors is larger than some threshold determined by the maximal Lyapunov exponent. This implies a remarkable difference to the one-dimensional case where synchronization is not possible when the number of units is large enough. For a WS model their main finding is that a quite high value of the rewiring probability (p >0.8)is needed to achieve complete synchronization. Finally for Ba networks the behavior is comparable to the random ER case Following a similar line, in 78 the behavior of a model where the interaction between the units can be strengthene x+1=(1-0)(1)+x∑灯(x here i= ier ki is the appropriate normalizing constant. Here the function f(x) is also a quadratic map. The authors study first BAnetworks When a=0 the model is equivalent to that discussed previously: in this case they find the existence of a first-order transition between the coherent and the noncoherent phases that depends on both the mean connectivity nd the coupling o. As varying a, the parameter of the quadratic map they find that these two critical values are related by the power law ac a ke The effect of a being larger than zero is only quantitative, since in this case the transition appears at smaller values of the interaction as compared with the usual case. Additionally, the authors studied two types of deterministic SF networks: a pseudofractal SF network introduced in [79 and the apollonian network introduced in 80J In both cases, there is no coherence when a =0 and a 2 this fact leads the authors to conclude that some degree of andomness that shortens the mean distance between units is needed for achieving a synchronized state since in these networks the sf nature is not related to a short mean distance. Nevertheless this situation is avoided if the contributions from the hubs are strengthened by making a>0 Another set of papers deals with units that are coupled with some transmission delay [81-83. For instance in[81 the luthors propose a model in which all units have the same time delay (in discrete units with respect to the unit considered xt+1)=f(x()+∑[rw(t-t)-(x() (49) For a uniform delay ti t vi, j, they show analytically, and numerically, that the delay facilitates synchronization for general topologies. In any case, this fact confirms the results obtained in [77 that ER and sF networks are easier to synchronize than regular or SW ones. Furthermore, one of the implications of connection delays is the possibility of the emergence of new collective phenomena In 82, 83 the authors considered uniform distributions of(discrete )time delays. Their main result is that in the presence of random delays the synchronization depends mainly on the average number of links per node, whereas for fixed delays there is also a dependence on other topological characteristics In a more general framework [ 84-86 the following problem is considered x(t+1)=(1-a)f(x(1)+a∑g(x(t) For a logistic map g(x)= ux(1-x)(although analyses on other maps as the circle map and the tent map have also been performed)the authors show a phase diagram in which the different stationary configurations are obtained as a function of the coupling strength o and the parameter of the map u. the stationary configurations are classified in the
110 A. Arenas et al. / Physics Reports 469 (2008) 93–153 which provides a simple example for describing the dynamics of a phase oscillator perturbed by a time-periodic force. Here K is a constant related to the external force amplitude and 0 ≤ Ω < 1 is the ratio between the natural oscillator frequency and the forcing frequency. It is observed that synchronization, in terms of a parameter related to the winding number dispersion, is induced by long-range coupling in a system that, in the absence of the shortcuts, does not synchronize. A slightly different approach was conducted in [77], who considered a population of units evolving according to xi(t + 1) = (1 − σ )f (xi(t)) + σ ki X j∈Γi f xj(t) . (46) They obtain the stability condition of the synchronized state in terms of the eigenvalues of the normalized Laplacian matrix (δij − aij/ki) and the Lyapunov exponent of the map f(x). Furthermore, they also find a sufficient condition for the system to synchronize independently of the initial conditions, namely (1 − σ λ2) sup |f 0 | < 1, (47) where λ2 is the smallest non-zero eigenvalue of the normalized Laplacian matrix. They demonstrate their results for regular connectivity patterns as global coupling and one-dimensional rings with a varying number of nearest neighbors, since in these cases the eigenvalues can be computed analytically. Complexity in the connectivity pattern is introduced in different ways. In these cases one needs numerical estimates of the eigenvalues to compare the synchronization condition (47) with the simulation of the model (46). By using a quadratic map f(x) = 1−ax2 [76] and choosing the free parameter a in a range where different regimes are realized, they find that in a random network the system synchronizes for an arbitrary large number of units, whenever the number of neighbors is larger than some threshold determined by the maximal Lyapunov exponent. This implies a remarkable difference to the one-dimensional case where synchronization is not possible when the number of units is large enough. For a WS model their main finding is that a quite high value of the rewiring probability (p > 0.8) is needed to achieve complete synchronization. Finally for BA networks the behavior is comparable to the random ER case. Following a similar line, in [78] the behavior of a model where the interaction between the units can be strengthened according to the degree is studied. In this case xt+1,i = (1 − σ )f(xt,i) + σ Ni X j∈Γi k α j f(xt,j), (48) where Ni = P j∈Γi k α j is the appropriate normalizing constant. Here the function f(x) is also a quadratic map. The authors study first BA networks. When α = 0 the model is equivalent to that discussed previously; in this case they find the existence of a first-order transition between the coherent and the noncoherent phases that depends on both the mean connectivity and the coupling σ. As varying a, the parameter of the quadratic map, they find that these two critical values are related by the power law σc ∝ k −µ c . The effect of α being larger than zero is only quantitative, since in this case the transition appears at smaller values of the interaction as compared with the usual case. Additionally, the authors studied two types of deterministic SF networks: a pseudofractal SF network introduced in [79] and the Apollonian network introduced in [80]. In both cases, there is no coherence when α = 0 and a = 2. This fact leads the authors to conclude that some degree of randomness that shortens the mean distance between units is needed for achieving a synchronized state, since in these networks the SF nature is not related to a short mean distance. Nevertheless, this situation is avoided if the contributions from the hubs are strengthened, by making α > 0. Another set of papers deals with units that are coupled with some transmission delay [81–83]. For instance, in [81] the authors propose a model in which all units have the same time delay (in discrete units) with respect to the unit considered: xi(t + 1) = f (xi(t)) + σ ki X j∈Γi f(xj t − τij) − f (xi(t)) . (49) For a uniform delay τij = τ ∀i, j, they show analytically, and numerically, that the delay facilitates synchronization for general topologies. In any case, this fact confirms the results obtained in [77] that ER and SF networks are easier to synchronize than regular or SW ones. Furthermore, one of the implications of connection delays is the possibility of the emergence of new collective phenomena. In [82,83] the authors considered uniform distributions of (discrete) time delays. Their main result is that in the presence of random delays the synchronization depends mainly on the average number of links per node, whereas for fixed delays there is also a dependence on other topological characteristics. In a more general framework [84–86], the following problem is considered xi(t + 1) = (1 − σ )f (xi(t)) + σ 1 ki X j∈Γi g xj(t) . (50) For a logistic map g(x) = µx(1 − x) (although analyses on other maps as the circle map and the tent map have also been performed) the authors show a phase diagram in which the different stationary configurations are obtained as a function of the coupling strength σ and the parameter of the map µ. The stationary configurations are classified in the
A Arenas et aL/Physics Reports 469(2008)93-153 111 ●● thecal pairs tree dusters ic4 #NEo 0.4 02 Fig. 6.(color online)Left: Distribution of the topological distances for a tree with 1000 nodes(bullets)and the distance inside the synchronized clusters 0.017 and different initial conditions. Right: visualization of the tree with five in arked by different colors From[871- following way: turbulence (all units behave chaotically ) partially ordered states(few synchronized clusters with some isolated nodes), ordered states(two or more synchronized clusters with no isolated nodes), coherent states(nodes form a single synchronized cluster), and variable states(nodes form different states depending strongly on initial conditions). The critical value of the coupling above where phase synchronized clusters are observed depends on the type of network and the coupling function. As a remarkable point, it is found that two different mechanisms of cluster formation(partial synchronization) can be distinguished: self-organized and driven clusters In the first case, the nodes of a cluster get synchronized because of intracluster coupling In the latter case, however, synchronization is due to intercluster coupling now the nodes of one cluster are driven by those of the others. For a linear coupling function g(x)=x, self-organization clusters dominates at weak coupling: when increasing the coupling strength, a transition to driven-type clusters, almost of independent of the type of network, appears. However, for a nonlinear coupling function the driven type dominates for weak coupling, and only networks with a tree-like structure show some cluster formation for strong coupling. Finally, it is worth mentioning Ref [87, in which the authors consider a SF tree(preferential-attachment growing network with one link per node)of two-dimensional standard maps: x=x+y+usin(2x)(mod 1) (51) The nodes are coupled through the angle coordinate(x)so that the complete time-step of the node i is x(+1)=(1-()+∑(x()-x(t) yt+1)=(1-E)y;(t) Here, ()denotes the next iteration of the(uncoupled )standard map(51)and t denotes the global discrete time. The update of each node is the sum of a contribution given by the updates of the nodes, the part, plus a coupling contribution given by the sum of differences, taking into account a delay in the coupling from the neighbors. By keeping u=0.9 such that the individual dynamics is in the strongly chaotic regime, the authors analyze the dependence on the interaction strength a. For small values of the coupling the motion of the individual units is still chaotic, but the trajectories are contained in bounded region. With further increments of the coupling, the units follow periodic motions which are highly synchronized In this case, however, synchronization takes place in clusters, each cluster having a common value of the band center around of dynamical regularity affecting mainly nodes at distances 2, 3, and 4, as shown in Fig. 6(left). In fact, the histograms of distances between nodes along the tree and between nodes belonging to the same synchronized cluster have different statistical weights only for these values of the distances All previously discussed chaotic models are discrete time maps, which are appropriate discrete versions of chaotic oscillators. Nevertheless, we also notice a couple of works dealing with time continuous maps. In 88 the authors analyze a WS network of Rossler oscillators, where the parameters are chosen to ensure that the system generates chaotic dynamics The basic observation is that the network synchronizes when the coupling strength is increased, as expected. Another interesting result is that the mean phase difference among the chaotic oscillators decreases with the increasing of the probability of adding long-range random short-cuts. Along the same line, in [89 it is considered a system of rossler
A. Arenas et al. / Physics Reports 469 (2008) 93–153 111 Fig. 6. (color online) Left: Distribution of the topological distances for a tree with 1000 nodes (bullets) and the distance inside the synchronized clusters (other symbols) for σ = 0.017 and different initial conditions. Right: visualization of the tree with five interconnected clusters of synchronized nodes marked by different colors. From [87]. following way: turbulence (all units behave chaotically), partially ordered states (few synchronized clusters with some isolated nodes), ordered states (two or more synchronized clusters with no isolated nodes), coherent states (nodes form a single synchronized cluster), and variable states (nodes form different states depending strongly on initial conditions). The critical value of the coupling above where phase synchronized clusters are observed depends on the type of network and the coupling function. As a remarkable point, it is found that two different mechanisms of cluster formation (partial synchronization) can be distinguished: self-organized and driven clusters. In the first case, the nodes of a cluster get synchronized because of intracluster coupling. In the latter case, however, synchronization is due to intercluster coupling; now the nodes of one cluster are driven by those of the others. For a linear coupling function g(x) = x, self-organization of clusters dominates at weak coupling; when increasing the coupling strength, a transition to driven-type clusters, almost independent of the type of network, appears. However, for a nonlinear coupling function the driven type dominates for weak coupling, and only networks with a tree-like structure show some cluster formation for strong coupling. Finally, it is worth mentioning Ref. [87], in which the authors consider a SF tree (preferential-attachment growing network with one link per node) of two-dimensional standard maps: x 0 = x + y + µsin(2πx) (mod 1) y 0 = y + µsin(2πx). (51) The nodes are coupled through the angle coordinate (x) so that the complete time-step of the node i is xi(t + 1) = (1 − ε)x 0 i (t) + ε ki X j∈Γi xj(t) − x 0 i (t) yi(t + 1) = (1 − ε)y 0 i (t). (52) Here, (0 ) denotes the next iteration of the (uncoupled) standard map (51) and t denotes the global discrete time. The update of each node is the sum of a contribution given by the updates of the nodes, the 0 part, plus a coupling contribution given by the sum of differences, taking into account a delay in the coupling from the neighbors. By keeping µ = 0.9 such that the individual dynamics is in the strongly chaotic regime, the authors analyze the dependence on the interaction strength σ. For small values of the coupling the motion of the individual units is still chaotic, but the trajectories are contained in a bounded region. With further increments of the coupling, the units follow periodic motions which are highly synchronized. In this case, however, synchronization takes place in clusters, each cluster having a common value of the band center around which the periodic motion occurs, and center values appear in a discrete set of possible values. These clusters form patterns of dynamical regularity affecting mainly nodes at distances 2, 3, and 4, as shown in Fig. 6(left). In fact, the histograms of distances between nodes along the tree and between nodes belonging to the same synchronized cluster have different statistical weights only for these values of the distances. All previously discussed chaotic models are discrete time maps, which are appropriate discrete versions of chaotic oscillators. Nevertheless, we also notice a couple of works dealing with time continuous maps. In [88] the authors analyze a WS network of Rössler oscillators, where the parameters are chosen to ensure that the system generates chaotic dynamics. The basic observation is that the network synchronizes when the coupling strength is increased, as expected. Another interesting result is that the mean phase difference among the chaotic oscillators decreases with the increasing of the probability of adding long-range random short-cuts. Along the same line, in [89] it is considered a system of Rössler
A Arenas et aL / Physics Reports 469(2008)93-153 oscillators on BA networks. The only tuning parameter of the Ba networks is m, the number of links that a newly added node has For m= 1(SF trees) there is no synchronized state for a large number of oscillators. Increasing m synchronization is favored. The topological effect of increasing m is to create loops but it is shown that this is not the only fact that improves Finally, a different and interesting proposal was made in[90] where a fixed 1-d connectivity pattern is complemented by a set of switching long-range connections. In this case, it is proven that interactions between nodes that are only sporadic and of short duration are very efficient for achieving synchronization. As a summary, we can say that most of the works deal with particular models of coupled maps(logistic maps, sine circle maps, quadratic maps, ..) Thus, it is possible, to obtain in some cases not only the conditions of local stability of the completely synchronized state but the conditions for the synchronization independently of the initial conditions. In general the addition of short-cuts to regular lattices improves synchronization. There are even some cases, for which synchronization is only attainable when a small fraction of randomness is added to the system. On the contrary, in the next section we will discuss the linear stability of the synchronized state for general dynamical systems. 4. Stability of the synchronized state in complex networks In the previous section we have reviewed the synchronization of various types of oscillators on complex networks. Another line of research on synchronization in complex networks, developed in parallel to the studies of synchronization in networks of phase oscillators, is the investigation of the stability of the completely synchronized state of populations of identical oscillators. The seminal work by Barahona and Pecora 91 initiated this research line by analyzing the stability of synchronization in Sw networks using the Master Stability Function(MSF). The framework of MSF was developed earlier for the study of synchronization of identical oscillators on regular or other simple network configurations 92, 93]. The extension of the framework to complex topologies is natural and important, because it relates the stability of the fully synchronized state to the spectral properties of the underlying structure. It provides an objective criterion to characterize the stability of the global synchronization state, from now on called synchronizability of networks independently of the particularities of the In this section, we review the MSF formalism and the main results obtained so far. Note that the msf approach assesses the linear stability of the completely synchronized state which is a necessary but not a sufficient condition for synchronization. 4.1. Master stability function formalism To introduce the MSF formalism, we start with an arbitrary connected network of coupled oscillators. The assumption here for the stability analysis of synchronization is that all the oscillators are identical, represented by the state vector x in an m-dimensional space. The equation of motion is described by the general form X=F(X) For simplicity, we consider time-continuous systems. However, the formalism applies also to time-discrete maps. We will also assume an identical output function H(x)for all the oscillators, which generates the signal from the state x and sends it to other oscillators in the networks. In this representation, H is a vector function of dimension m. For example, for the 3- dimensional system x=(x, y, z). we can take H(x)=(x, 0, 0), which means that the oscillators are coupled only through the component x. H(x) can be any linear or nonlinear mapping of the state vector x. The n oscillators, i= 1,..., N,are coupled in a network specified by the adjacency matrix a =(aij). We have x=F(x)+a∑Hx)-H(x F(x)-a>Gu H(x ), (55) being wi>0 the connection weights, i. e the network is, in general, weighted. The coupling matrix G is Gi=-dijWij ifij and Gi= sai Wi. When the coupling strength is uniform for all the connections (w= 1), the network is unweighted, d the coupling matrix G is just the usual Laplacian matrix L. by definition, the coupling matrix G has zero row-sum. Thus there exists a completely synchronized state in this network of identical oscillators, i.e., x1(t)=x2(t) =XN()=s(t), which is a solution of Eq (55 ). In this synchronized state, s(t) also approaches the solution of Eq. (53), i.e., S= F(s). This subspace in the state space of Eq (55), where all the oscillators evolve synchronously on the same solution of the isolated oscillator F, is called the synchronization manifole
112 A. Arenas et al. / Physics Reports 469 (2008) 93–153 oscillators on BA networks. The only tuning parameter of the BA networks is m, the number of links that a newly added node has. For m = 1 (SF trees) there is no synchronized state for a large number of oscillators. Increasing m synchronization is favored. The topological effect of increasing m is to create loops, but it is shown that this is not the only fact that improves synchronization. Finally, a different and interesting proposal was made in [90] where a fixed 1-d connectivity pattern is complemented by a set of switching long-range connections. In this case, it is proven that interactions between nodes that are only sporadic and of short duration are very efficient for achieving synchronization. As a summary, we can say that most of the works deal with particular models of coupled maps (logistic maps, sinecircle maps, quadratic maps, . . . ). Thus, it is possible, to obtain in some cases not only the conditions of local stability of the completely synchronized state but the conditions for the synchronization independently of the initial conditions. In general, the addition of short-cuts to regular lattices improves synchronization. There are even some cases, for which synchronization is only attainable when a small fraction of randomness is added to the system. On the contrary, in the next section we will discuss the linear stability of the synchronized state for general dynamical systems. 4. Stability of the synchronized state in complex networks In the previous section we have reviewed the synchronization of various types of oscillators on complex networks. Another line of research on synchronization in complex networks, developed in parallel to the studies of synchronization in networks of phase oscillators, is the investigation of the stability of the completely synchronized state of populations of identical oscillators. The seminal work by Barahona and Pecora [91] initiated this research line by analyzing the stability of synchronization in SW networks using the Master Stability Function (MSF). The framework of MSF was developed earlier for the study of synchronization of identical oscillators on regular or other simple network configurations [92,93]. The extension of the framework to complex topologies is natural and important, because it relates the stability of the fully synchronized state to the spectral properties of the underlying structure. It provides an objective criterion to characterize the stability of the global synchronization state, from now on called synchronizability of networks independently of the particularities of the oscillators. Relevant insights about the structure–dynamics relationship has been obtained using this technique. In this section, we review the MSF formalism and the main results obtained so far. Note that the MSF approach assesses the linear stability of the completely synchronized state, which is a necessary, but not a sufficient condition for synchronization. 4.1. Master stability function formalism To introduce the MSF formalism, we start with an arbitrary connected network of coupled oscillators. The assumption here for the stability analysis of synchronization is that all the oscillators are identical, represented by the state vector x in an m-dimensional space. The equation of motion is described by the general form x˙ = F(x). (53) For simplicity, we consider time-continuous systems. However, the formalism applies also to time-discrete maps. We will also assume an identical output function H(x) for all the oscillators, which generates the signal from the state x and sends it to other oscillators in the networks. In this representation, H is a vector function of dimension m. For example, for the 3- dimensional system x = (x, y, z), we can take H(x) = (x, 0, 0), which means that the oscillators are coupled only through the component x. H(x) can be any linear or nonlinear mapping of the state vector x. The N oscillators, i = 1, . . . , N, are coupled in a network specified by the adjacency matrix A = (aij). We have x˙i = F(xi) + σ XN i=1 aijwij[H(xj) − H(xi)] (54) = F(xi) − σ XN j=1 GijH(xj), (55) being wij ≥ 0 the connection weights, i.e., the network is, in general, weighted. The coupling matrix G is Gij = −aijwij if i 6= j and Gii = PN j=1 aijwij. When the coupling strength is uniform for all the connections (wij = 1), the network is unweighted, and the coupling matrix G is just the usual Laplacian matrix L. By definition, the coupling matrix G has zero row-sum. Thus there exists a completely synchronized state in this network of identical oscillators, i.e., x1(t) = x2(t) = · · · = xN (t) = s(t), (56) which is a solution of Eq. (55). In this synchronized state, s(t) also approaches the solution of Eq. (53), i.e., s˙ = F(s). This subspace in the state space of Eq. (55), where all the oscillators evolve synchronously on the same solution of the isolated oscillator F, is called the synchronization manifold