A. Arenas et aL Physics Reports 469(2008)93-153 Within the mean field theory, it is also possible to obtain the behavior of the order parameter r near the transition to nchronization Eq (29)was also independently derived in[48 starting from the differential equation(11). Using the weighted order parameter and assuming the same magnitude of the effective field of each pair of coupled oscillators one obtains (30) where we have set = 0. Now, it is considered again that in the stationary state the system divides into two groups of oscillators, which are either locked or rotating in a nonuniform manner. Following the same procedure employed in all the previous derivations, the only contribution to r comes from the former set of oscillators. After some algebra [48 it is shown that the critical coupling o is given by Eq (29)and that near criticality for y>3, with a critical exponent B =, if y >5, and B =v when 3<y<5. For the most common cases in real networks of 2<y <3, the critical coupling tends to zero in the thermodynamic limit so that r should be nonzero as soon as o+0. In this case, one gets xo/(3-y). Notably, the latter equation is exactly the same found for the absence of critical behavior in the region 2 3 for a model of epidemic spreading [49] One recent theoretical study in 50] is worth mentioning here. They have extended the mean field approach to the case in which the coupling is asymmetric and depends on the degree. In particular, they studied a system of oscillators arranged in a complex topology whose dynamics is given by sin(ej-ei) n= 1 corresponds to the symmetric, non-degree dependent, case. Extending the mean field formalism to the cases n# 1 they investigated the nature of the synchronization transition as a function of the magnitude and sign of the parameter n By exploring the whole parameter space(n, o), they found that for n=0 and SF networks with 2 <y < 3, a finite critical coupling ac is recovered in sharp contrast to the non-weighted coupling case for which we already know that c 0 This result seems phenomenologically meaningful, since setting n= 0 implies that the coupling in Eq (10)is oi=a/k], which, as discussed before[32]. might have the effect of partially destroying the heterogeneity inherent to the underlying graph by normalizing all the contributions 2i, aj sin(0-0) by k;=Ey, aij 3.1.4. Path towards synchronization in complex networks Up to now, we have discussed both numerically and theoretically the onset of synchronization In the next section, we shall also discuss how the structural properties of the networks influence the stability of the fully synchronized state. But That happens in the region where we are neither close to the onset of synchronization nor at complete synchronization? How is the latter state attained when different topologies are considered? As we have seen, the influence of the topology is not only given by the degree distribution, but also by how the oscillators interact locally. To reduce the number of degrees of freedom to a minimum, let us focus on the influence of heterogeneity and study the evolution of synchronization for a family of complex networks which are comparable in their clustering. average distance and correlations so that the only difference is due to the degree distribution. 4 For these networks, the revious theoretical approaches argued that the critical coupling a is proportional to( k)/( k), so that different topologies should give rise to distinct critical points. In particular, in [39, 40] the path towards synchronization in ER and SF networks was studied numerically. They also studied several networks whose degree of heterogeneity can be tuned between the two limiting cases[51. These authors put forward the question: How do SF networks compare with ER ones and what are the roots of the different behaviors observed Numerical simulations [39, 40 confirm qualitatively the theoretical predictions for the onset of synchronization, as summarized in Table 1. In fact, the onset of synchronization first occurs for SF networks. As the network substrate becomes more homogeneous, the critical point o shifts to larger values and the system seems to be less synchronizable. On the other hand they also showed that the route to complete synchronization, r 1, is sharper for homogeneous networks. No critical 4 This isolation of individual features of complex networks is essential to understand the interplay between topology and dy As we will discuss along the review, many times this aspect has not been properly controlled, raising results that are confusing. contradictory or even ind
A. Arenas et al. / Physics Reports 469 (2008) 93–153 103 Within the mean field theory, it is also possible to obtain the behavior of the order parameter r near the transition to synchronization. Eq. (29) was also independently derived in [48] starting from the differential equation (11). Using the weighted order parameter r¯(t)e iφ(¯ t) = PN i=1 PN j=1 aije iθj PN i=1 ki , and assuming the same magnitude of the effective field of each pair of coupled oscillators one obtains θ˙ i = ωi − σ hki kir¯ sin(θi), (30) where we have set φ¯ = 0. Now, it is considered again that in the stationary state the system divides into two groups of oscillators, which are either locked or rotating in a nonuniform manner. Following the same procedure employed in all the previous derivations, the only contribution to r comes from the former set of oscillators. After some algebra [48], it is shown that the critical coupling σc is given by Eq. (29) and that near criticality r ∼ (σ − σc ) β , (31) for γ > 3, with a critical exponent β = 1 2 if γ ≥ 5, and β = 1 γ −3 when 3 < γ ≤ 5. For the most common cases in real networks of 2 < γ < 3, the critical coupling tends to zero in the thermodynamic limit so that r should be nonzero as soon as σ 6= 0. In this case, one gets r ∼ σ 1/(3−γ ). Notably, the latter equation is exactly the same found for the absence of critical behavior in the region 2 < γ < 3 for a model of epidemic spreading [49]. One recent theoretical study in [50] is worth mentioning here. They have extended the mean field approach to the case in which the coupling is asymmetric and depends on the degree. In particular, they studied a system of oscillators arranged in a complex topology whose dynamics is given by θ˙ i = ωi + σ k 1−η i XN j=1 sin(θj − θi). (32) η = 1 corresponds to the symmetric, non-degree dependent, case. Extending the mean field formalism to the cases η 6= 1, they investigated the nature of the synchronization transition as a function of the magnitude and sign of the parameter η. By exploring the whole parameter space (η, σ ), they found that for η = 0 and SF networks with 2 < γ < 3, a finite critical coupling σc is recovered in sharp contrast to the non-weighted coupling case for which we already know that σc = 0. This result seems phenomenologically meaningful, since setting η = 0 implies that the coupling in Eq. (10) is σij = σ /ki , which, as discussed before [32], might have the effect of partially destroying the heterogeneity inherent to the underlying graph by normalizing all the contributions PN j=1 aij sin(θj − θi) by ki = PN j=1 aij. 3.1.4. Path towards synchronization in complex networks Up to now, we have discussed both numerically and theoretically the onset of synchronization. In the next section, we shall also discuss how the structural properties of the networks influence the stability of the fully synchronized state. But, what happens in the region where we are neither close to the onset of synchronization nor at complete synchronization? How is the latter state attained when different topologies are considered? As we have seen, the influence of the topology is not only given by the degree distribution, but also by how the oscillators interact locally. To reduce the number of degrees of freedom to a minimum, let us focus on the influence of heterogeneity and study the evolution of synchronization for a family of complex networks which are comparable in their clustering, average distance and correlations so that the only difference is due to the degree distribution.4 For these networks, the previous theoretical approaches argued that the critical coupling σc is proportional to hki/hk 2 i, so that different topologies should give rise to distinct critical points. In particular, in [39,40] the path towards synchronization in ER and SF networks was studied numerically. They also studied several networks whose degree of heterogeneity can be tuned between the two limiting cases [51]. These authors put forward the question: How do SF networks compare with ER ones and what are the roots of the different behaviors observed? Numerical simulations [39,40] confirm qualitatively the theoretical predictions for the onset of synchronization, as summarized in Table 1. In fact, the onset of synchronization first occurs for SF networks. As the network substrate becomes more homogeneous, the critical point σc shifts to larger values and the system seems to be less synchronizable. On the other hand, they also showed that the route to complete synchronization, r = 1, is sharper for homogeneous networks. No critical 4 This isolation of individual features of complex networks is essential to understand the interplay between topology and dynamics. As we will discuss along the review, many times this aspect has not been properly controlled, raising results that are confusing, contradictory or even incorrect
A Arenas et aL / Physics Reports 469(2008)93-153 Table 1 Topological properties of the networks and critical coupling strengths derived from a finite size scaling analyses, Eq (12) 00(SF) 111.6 16.8 1.0(ER) fferent values of x corresponds to grown networks whose degree of heterogeneity varies smoothly between the two limiting cases of ER and SF graphs. From[40. Fig 3. (color online)Synch mponents for several values of a for the two limiting cases of ER and SF networks. The figure clearly illustrates the in forming synchronization patterns for both types of networks: in the SF case links an nized clusters, while for the er network, what is added are links between nodes already to such cluster From [39. exponents for the behavior of r near the transition points have been reported yet for the er network, so that comparison with the mean field value B= 1/2 for a SF network with y 3 is not possible. Numerically, a detailed finite size scaling analysis in SF and ER topologies shows that the critical coupling strength corresponds in SF networks to o =0.051, and in random ER networks to o R=0. 122, a fairly significant numerical difference. The mechanisms behind the differences in the emergence of collective behavior for er and Sf topologies can be explored umerically by defining a local order parameter that captures and quantifies the way in which clusters of locked oscillators emerge. The main difference with respect to r is that one measures the degree of synchronization of nodes(r)with respect to the average phase and the other (ink )to the degree of synchronization between every pair of connected nodes. Thus, Tink gives the fraction of all possible links that are synchronized in the network as being tr the time the system needs to settle into the stationary state and At a large averaging time In [39, 40 the degree of synchronization of pairs of connected oscillators was measured in terms of the symmetric matrix ai/ lim/++ar which, once filtered using a threshold T such that the fraction of synchronized pairs equals rink, allows us to identify the synchronized links and reconstruct the clusters of synchrony for any value of o, as illustrated in Fig. 3. From a microscopic analysis, it turns out that for homogeneous topologies, many small clusters of synchronized pairs of oscillators are spread over the graph and merge together to form a giant synchronized cluster when the effective coupling is increased. On the contrary, in heterogeneous graphs, a central core containing the hubs first comes up driving the evolution of synchronization patterns by absorbing small clusters. Moreover, the evolution of rlink as o grows, explains why the transition is sharper for R networks: nodes are added first to the giant synchronized cluster and, later on, the links among these nodes that were issing in the original clusters of synchrony. In SF graphs, oscillators are added to the largest synchronized component together with most of their links, resulting in a much slower growth of rink. Finally, the probability that a node with degree k belongs to the largest synchronized cluster is also computed. This probability is an increasing function of k for every a, namely, the more connected a node is, the more likely it takes part in the cluster of synchronized links [ 39, 40 It is interesting to mention here that a similar dependence is obtained if one analyzes the stability of the synchronized state
104 A. Arenas et al. / Physics Reports 469 (2008) 93–153 Table 1 Topological properties of the networks and critical coupling strengths derived from a finite size scaling analyses, Eq. (12) χ hk 2 i kmax σc 0.0 (SF) 115.5 326.3 0.051 0.2 56.7 111.6 0.066 0.4 44.9 47.7 0.088 0.6 41.1 25.6 0.103 0.8 39.6 16.8 0.108 1.0 (ER) 39.0 14.8 0.122 Different values of χ corresponds to grown networks whose degree of heterogeneity varies smoothly between the two limiting cases of ER and SF graphs. From [40]. Fig. 3. (color online) Synchronized components for several values of σ for the two limiting cases of ER and SF networks. The figure clearly illustrates the differences in forming synchronization patterns for both types of networks: in the SF case links and nodes are incorporated together to the largest of the synchronized clusters, while for the ER network, what is added are links between nodes already belonging to such cluster. From [39]. exponents for the behavior of r near the transition points have been reported yet for the ER network, so that comparison with the mean field value β = 1/2 for a SF network with γ = 3 is not possible.5 Numerically, a detailed finite size scaling analysis in SF and ER topologies shows that the critical coupling strength corresponds in SF networks to σ SF c = 0.051, and in random ER networks to σ ER c = 0.122, a fairly significant numerical difference. The mechanisms behind the differences in the emergence of collective behavior for ER and SF topologies can be explored numerically by defining a local order parameter that captures and quantifies the way in which clusters of locked oscillators emerge. The main difference with respect to r is that one measures the degree of synchronization of nodes (r) with respect to the average phase φ and the other (rlink) to the degree of synchronization between every pair of connected nodes. Thus, rlink gives the fraction of all possible links that are synchronized in the network as rlink = 1 2Nl XN i,j=1 aij lim ∆t→∞ 1 ∆t Z tr+∆t tr e i[θi (t)−θj (t)]dt , (33) being tr the time the system needs to settle into the stationary state, and ∆t a large averaging time. In [39,40] the degree of synchronization of pairs of connected oscillators was measured in terms of the symmetric matrix Dij = aij lim ∆t→∞ 1 ∆t Z tr+∆t tr e i[θi (t)−θj (t)]dt , (34) which, once filtered using a threshold T such that the fraction of synchronized pairs equals rlink, allows us to identify the synchronized links and reconstruct the clusters of synchrony for any value of σ, as illustrated in Fig. 3. From a microscopic analysis, it turns out that for homogeneous topologies, many small clusters of synchronized pairs of oscillators are spread over the graph and merge together to form a giant synchronized cluster when the effective coupling is increased. On the contrary, in heterogeneous graphs, a central core containing the hubs first comes up driving the evolution of synchronization patterns by absorbing small clusters. Moreover, the evolution of rlink as σ grows, explains why the transition is sharper for ER networks: nodes are added first to the giant synchronized cluster and, later on, the links among these nodes that were missing in the original clusters of synchrony. In SF graphs, oscillators are added to the largest synchronized component together with most of their links, resulting in a much slower growth of rlink. Finally, the probability that a node with degree k belongs to the largest synchronized cluster is also computed. This probability is an increasing function of k for every σ, namely, the more connected a node is, the more likely it takes part in the cluster of synchronized links [39,40]. It is interesting to mention here that a similar dependence is obtained if one analyzes the stability of the synchronized state 5 The numerical value of β contradicts the prediction of the mean-field approach (see the discussion after Eq. (31)) The reason of such discrepancy is not clear yet
A Arenas et aL/Physics Reports 469(2008)93-153 under perturbations of nodes of degree k In [35 it was found that the average time([)a node needs to get back into the fully synchronized state is inversely proportional to its degree, i.e.(t) Very recently 52 the path towards synchronization was also studied, looking for the relation between the time needed for complete synchronization and the spectral properties of the laplacian matrix of the graph, The Laplacian matrix is symmetric with zero row-sum and hence all the eigenvalues are real and non-negative. Considering the case of identical Kuramoto oscillators, whose dynamics has only one attractor, the fully synchronized state, they found that the synchronization time scales with the inverse of the smallest nonzero eigenvalue of the laplacian matrix. Surprisingly, this relation qualitatively holds for very different networks where synchronization is achieved, indicating that this eigenvalue alone might be a relevant topological property for synchronization phenomena. The authors in 53 point out the role of this eigenvalue not only for synchronization purposes but also for the flow of random walkers on the network. 3.1.5 Kuramoto model on structured or modular networks explore the relation between dynamical and topological properties of complex networks. Many complex networks nature are modular, i.e. composed of certain subgraphs with differentiated internal and external connectivity that form communities [15, 19, 20). This is a limiting situation in which the local structure may greatly affect the dynamics, irrespective f whether or not we deal with homogeneous or heterogeneous networks Synchronization processes on modular networks have been recently studied as a mechanism for community detection [54-57 The situation in which a set of identical Kuramoto oscillators(i. o. Vi) with random initial conditions evolves after a transient to the synchronized state was addressed in [55, 56]6 Note that in this case full synchronization is always achieved as this state is the only attractor of the dynamics so that the coupling strength sets the time scale to attain full synchronization: the smaller o is, the longer the time scale. The authors in 55 guessed that if high densely interconnected motifs synchronize more easily than those with sparse connections [36]. then the synchronization of complex networks with community structure should behave differently at different time and spatial scales. In synthetic modular networks, starting from random initial phases, the highly connected units forming local clusters synchronize first and later on, in a sequential process, larger and larger topological structures do the same up to the point in which communities, from the microscale at very early stages up to the macroscale at the end of the time evolution s occurs at complete synchronization is achieved and the whole population of oscillators beat at the same pace. This proce different time scales and the dynamical route towards the global attractor reveals the topological structures that represent The authors studied the time evolution of pairs of oscillators defining the local order parameter p(t)=(cos{1(t)-6(t)》 averaged over different initial conditions, which measures the correlation between pairs of oscillators To identify the emergence of compact clusters reflecting communities, a binary dynamic connectivity matrix is introduced such that if pi (t)>T 2(T)=0in(t)<T, for a given threshold T. Changing the threshold T at fixed times reveals the correlations between the dynamics and the underlying structure, namely, for large enough T, one is left with a set of disconnected clusters or communities that are the innermost ones, while for smaller values of T inter-community connections show up. In other words, the inner community levels are the first to become synchronized. Subsequently the second level groups, and finally the whole system shows global synchronization. Note that since the function pi (t) is continuous and monotonic, we can define a new matrix (t). that takes into account the time evolution for a fixed threshold. The evolution of this matrix unravels the topological structure of the underlying network at different time scales. In the top panels of Fig 4 we plot the number of connected components corresponding to the binary connectivity matrix with a fixed threshold as a function of time for networks with two hierarchical levels of communities. There we can notice how this procedure shows the existence of two clear time scales corresponding to the two topological scales. It is also possible to go one step further and show that the evolution of the system to the global attractor is intimately linked to the whole spectrum of the Laplacian matrix(35). The bottom panels of Fig 4 show the ranked index of the eigenvalues of Li versus their inverse. As can be seen, both representations( top and bottom)are qualitatively equivalent. revealing the topological structure of the networks. The only difference is that one comes from a dynamical matrix and the other from the spectrum of the Laplacian, that fully characterizes the topology Thus, synchronization can be used to unveil topological scales when the architecture of the network is unknown. ity as it makes the analysis easier. Synchronization of non-identical oscillators also reveals the existence of community structures. See[40)
A. Arenas et al. / Physics Reports 469 (2008) 93–153 105 under perturbations of nodes of degree k. In [35] it was found that the average time hτ i a node needs to get back into the fully synchronized state is inversely proportional to its degree, i.e. hτ i ∼ k −1 . Very recently [52], the path towards synchronization was also studied, looking for the relation between the time needed for complete synchronization and the spectral properties of the Laplacian matrix of the graph, Lij = kiδij − aij. (35) The Laplacian matrix is symmetric with zero row-sum and hence all the eigenvalues are real and non-negative. Considering the case of identical Kuramoto oscillators, whose dynamics has only one attractor, the fully synchronized state, they found that the synchronization time scales with the inverse of the smallest nonzero eigenvalue of the Laplacian matrix. Surprisingly, this relation qualitatively holds for very different networks where synchronization is achieved, indicating that this eigenvalue alone might be a relevant topological property for synchronization phenomena. The authors in [53] point out the role of this eigenvalue not only for synchronization purposes but also for the flow of random walkers on the network. 3.1.5. Kuramoto model on structured or modular networks In this section, we discuss a context in which synchronization has turned out to be a relevant phenomenon to explore the relation between dynamical and topological properties of complex networks. Many complex networks in nature are modular, i.e. composed of certain subgraphs with differentiated internal and external connectivity that form communities [15,19,20]. This is a limiting situation in which the local structure may greatly affect the dynamics, irrespective of whether or not we deal with homogeneous or heterogeneous networks. Synchronization processes on modular networks have been recently studied as a mechanism for community detection [54–57]. The situation in which a set of identical Kuramoto oscillators (i.e. ωi = ω, ∀i) with random initial conditions evolves after a transient to the synchronized state was addressed in [55,56].6 Note that in this case full synchronization is always achieved as this state is the only attractor of the dynamics so that the coupling strength sets the time scale to attain full synchronization: the smaller σ is, the longer the time scale. The authors in [55] guessed that if high densely interconnected motifs synchronize more easily than those with sparse connections [36], then the synchronization of complex networks with community structure should behave differently at different time and spatial scales. In synthetic modular networks, starting from random initial phases, the highly connected units forming local clusters synchronize first and later on, in a sequential process, larger and larger topological structures do the same up to the point in which complete synchronization is achieved and the whole population of oscillators beat at the same pace. This process occurs at different time scales and the dynamical route towards the global attractor reveals the topological structures that represent communities, from the microscale at very early stages up to the macroscale at the end of the time evolution. The authors studied the time evolution of pairs of oscillators defining the local order parameter ρij(t) = hcos[θi(t) − θj(t)]i, (36) averaged over different initial conditions, which measures the correlation between pairs of oscillators. To identify the emergence of compact clusters reflecting communities, a binary dynamic connectivity matrix is introduced such that Dt(T )ij = 1 if ρij(t) > T 0 if ρij(t) < T , (37) for a given threshold T . Changing the threshold T at fixed times reveals the correlations between the dynamics and the underlying structure, namely, for large enough T , one is left with a set of disconnected clusters or communities that are the innermost ones, while for smaller values of T inter-community connections show up. In other words, the inner community levels are the first to become synchronized. Subsequently the second level groups, and finally the whole system shows global synchronization. Note that since the function ρij(t) is continuous and monotonic, we can define a new matrix DT (t), that takes into account the time evolution for a fixed threshold. The evolution of this matrix unravels the topological structure of the underlying network at different time scales. In the top panels of Fig. 4 we plot the number of connected components corresponding to the binary connectivity matrix with a fixed threshold as a function of time for networks with two hierarchical levels of communities. There we can notice how this procedure shows the existence of two clear time scales corresponding to the two topological scales. It is also possible to go one step further and show that the evolution of the system to the global attractor is intimately linked to the whole spectrum of the Laplacian matrix (35). The bottom panels of Fig. 4 show the ranked index of the eigenvalues of Lij versus their inverse. As can be seen, both representations (top and bottom) are qualitatively equivalent, revealing the topological structure of the networks. The only difference is that one comes from a dynamical matrix and the other from the spectrum of the Laplacian, that fully characterizes the topology. Thus, synchronization can be used to unveil topological scales when the architecture of the network is unknown. 6 It is worth stressing here that for this purpose the assumption of ωi = ω can be adopted without loss of generality as it makes the analysis easier. Synchronization of non-identical oscillators also reveals the existence of community structures. See [40]
A Arenas et aL / Physics Reports 469(2008)93-153 100 06E 069 100 100 nents(d.s.c. )as a function of time. Bottom: Rank index versus the corresponding igenvalue of the Laplacian matrix. Each column corresponds to a network with two hierarchical levels of communities. The difference lies in the relative weight of the two modular levels From [551 The relationship between the eigenvalue spectrum of Lij and the dynamical structures of Fig. 4 can be understood from the linearized dynamics of the Kuramoto model, which reads 55, 56 that is a good approximation after a fast transient starting from random initial phases in the range [0, 2]. The solution of Eq (38), in terms of the normal modes yi (t),is B()=∑的t)=∑B0e- where Bi is the normalized eigenvector matrix and hi the eigenvalues of the Laplacian matrix. Going back to the original coordinates, the phase difference between any pair of oscillators is A(-s∑-Be"wl I%K(O) 4 Assuming a global bound for the initial conditions e(o)Is 0, Vk and taking into account the normalization of the eigenvector matrix, B; s 1, we can sum over the index k to get A()-an(≤Ne∑|-B The sum starts at j= 2 because all the components of the first eigenvector(the one corresponding to the zero eigenvalue) are identical, which is the warranty of the final synchronization of the system. Here we can see the clear relation between topology (represented by the eigenvectors and eigenvalues of the Laplacian matrix)and dynamics. For long times all exponentials go to zero and the oscillators get synchronized. At short times the main contribution comes from small
106 A. Arenas et al. / Physics Reports 469 (2008) 93–153 Fig. 4. (color online) Top: Number of disconnected synchronized components (d.s.c.) as a function of time. Bottom: Rank index versus the corresponding eigenvalue of the Laplacian matrix. Each column corresponds to a network with two hierarchical levels of communities. The difference lies in the relative weight of the two modular levels. From [55]. The relationship between the eigenvalue spectrum of Lij and the dynamical structures of Fig. 4 can be understood from the linearized dynamics of the Kuramoto model, which reads [55,56] θ˙ i = −σ XN j=1 Lijθj i = 1, . . . , N, (38) that is a good approximation after a fast transient starting from random initial phases in the range [0, 2π]. The solution of Eq. (38), in terms of the normal modes ψi(t), is θi(t) = XN j=1 Bijψj(t) = XN j=1 Bijψj(0)e −σ λj t , (39) where Bij is the normalized eigenvector matrix and λi the eigenvalues of the Laplacian matrix. Going back to the original coordinates, the phase difference between any pair of oscillators is |θi(t) − θm(t)| ≤ XN j,k=1 Bij − Bmj e −σ λj t B Ď jk |ϕk(0)| . (40) Assuming a global bound for the initial conditions |θk(0)| ≤ Θ, ∀k and taking into account the normalization of the eigenvector matrix, Bij ≤ 1, we can sum over the index k to get |θi(t) − θm(t)| ≤ NΘ XN j=2 Bij − Bmj e −σ λj t . (41) The sum starts at j = 2 because all the components of the first eigenvector (the one corresponding to the zero eigenvalue) are identical, which is the warranty of the final synchronization of the system. Here we can see the clear relation between topology (represented by the eigenvectors and eigenvalues of the Laplacian matrix) and dynamics. For long times all exponentials go to zero and the oscillators get synchronized. At short times the main contribution comes from small
A. Arenas et aL Physics Reports 469(2008)93-153 eigenvalues; then those nodes with similar projections on the eigenvectors of small indices will get synchronized even at short times. In networks which are hierarchically organized this happens at all topological and dynamical scales An additional significance of the importance of this relationship between spectral and dynamical properties of identical oscillators comes from the work in (58. The authors propose a method of network reduction based on the similarity of eigenvector projections From the original network, nodes are merged according to the similarity of their components in the different eigenvectors, producing a reduced network; this merging procedure basically preserves the original eigenvalues of the laplacian matrix in the new coarse grained Laplacian matrix. the authors determine the best clustering of the nodes and show that the evolution of identical Kuramoto oscillators in the original network and according to the original Laplacian is equivalent to the evolution of the reduced network in terms of the reduced Laplacian matrix. The above results refer to situations in which networks have clearly defined community structure. The approach we have shown enables one to deal with different time and topological scales. In the current literature about community detection[ 19, 20). the main goal is to maximize the modularity, see eq (2). In this case the different algorithms try to find the best partition of a network Using a dynamical procedure, however, we are able to devise all partitions at different scales. In(59 it is found that the partition with the largest modularity turns out to be the one for which the system is more stable, if the networks are homogeneous in degree. If the networks have hubs, these more connected nodes need more time to synchronize with their neighbors and tend to form communities by themselves. This is in contradiction with the optimization of the modularity that punishes single node communities. From this result we can conclude that the modularity is a good measure for community partitioning. But when dealing with dynamical evolution in complex networks other related functions different from modularity are needed. For real networks, it has been shown that the same phenomenology applies [54]. These authors studied a system of Kuramoto oscillators, Eq(10)with o a/ ki, arranged on the nodes of two real networks with community structures, the yeast protein interaction network and the autonomous System representation of the Internet map. Both networks have a modular structure, but differ in the way communities are assembled together. In the former, the modules are connected diversely(as for the synthetic networks analyzed before ). while in the latter. different communities are interwoven mainly through a single module. the authors found that the transition to synchrony depends on the type of intermodular connections such that communities can mutually or independently synchronize. Modular networks are found in nature and they are commonly the result of a growth process. Nevertheless, these structural properties can also emerge as an adaptive mechanism generated by dynamical processes taking place in the existing network, and synchronization could be one of them. In particular, in [60 the authors studied the evolution of a network of Kuramoto oscillators. For a coupling strength below its critical value, the network is rewired by replacing links between neighbors with a large frequency difference with links between units with a small frequency difference. In this case, the network dynamically evolves to configurations that increase the order parameter. Along this evolution they noticed the appearance of synchronized groups(communities)that make the structure of the network to be more complex than the random starting on Very recently [ 61]. a slightly different model was considered, where the dynamics of each node is governed by ∑sny-82 being bi the betweenness centrality of the link, I the set of nodes that are connected to i, and aa time-dependent exponent. The authors use this dynamical evolution to identify communities. The betweenness is used as a measure of community coparticipation, since links between nodes that are in the same community have low betweenness [21]. Starting from a synchronized state, a is decreased from zero and then the corresponding interaction strength on those links is increasingly enhanced. An additional mechanism that adjusts frequencies between neighboring nodes causes the final state to show partial synchronization among nodes that are in the same community. 3.1.6. Synchronization by pacemakers It is worth mentioning the existence of other different approaches to the synchronization of populations of Kuramoto cillators. So far we have referred to populations where the oscillators are nearly identical in the sense that they can have slightly different frequencies. Whenever there is a subset of units that play a special role in the sense that they have substantially different frequencies than the rest in the population or they affect some units but are not affected by any of them, one usually refers to them as pacemakers. The effect of pacemakers has been studied in regular networks, as for instance in one-dimensional rings, two-dimensional tori and Cayley trees 62 So far, the only approach in a complex topology has been performed in [ 63]. There, the authors considered a system of identical units(same frequency) and a singular pacemaker. For an ER network they found that for a large coupling the pacemaker entrains the whole system(all units with the same effective frequency, that of the pacemaker), but the phase distribution is hierarchically organized Units at the same downward distance from the pacemaker form shells of common phases. As the coupling strength is decreased 7 Here stability(relative)of a given structure is understood to be the ratio between the final and initial times a partition remains synchronized. In terms of the number of connected components in Fig. 4 it corresponds to the length of the plateau
A. Arenas et al. / Physics Reports 469 (2008) 93–153 107 eigenvalues; then those nodes with similar projections on the eigenvectors of small indices will get synchronized even at short times. In networks which are hierarchically organized this happens at all topological and dynamical scales. An additional significance of the importance of this relationship between spectral and dynamical properties of identical oscillators comes from the work in [58]. The authors propose a method of network reduction based on the similarity of eigenvector projections. From the original network, nodes are merged according to the similarity of their components in the different eigenvectors, producing a reduced network; this merging procedure basically preserves the original eigenvalues of the Laplacian matrix in the new coarse grained Laplacian matrix. The authors determine the best clustering of the nodes and show that the evolution of identical Kuramoto oscillators in the original network and according to the original Laplacian is equivalent to the evolution of the reduced network in terms of the reduced Laplacian matrix. The above results refer to situations in which networks have clearly defined community structure. The approach we have shown enables one to deal with different time and topological scales. In the current literature about community detection [19,20], the main goal is to maximize the modularity, see Eq. (2). In this case the different algorithms try to find the best partition of a network. Using a dynamical procedure, however, we are able to devise all partitions at different scales. In [59] it is found that the partition with the largest modularity turns out to be the one for which the system is more stable, if the networks are homogeneous in degree.7 If the networks have hubs, these more connected nodes need more time to synchronize with their neighbors and tend to form communities by themselves. This is in contradiction with the optimization of the modularity that punishes single node communities. From this result we can conclude that the modularity is a good measure for community partitioning. But when dealing with dynamical evolution in complex networks other related functions different from modularity are needed. For real networks, it has been shown that the same phenomenology applies [54]. These authors studied a system of Kuramoto oscillators, Eq. (10) with σij = σ /ki , arranged on the nodes of two real networks with community structures, the yeast protein interaction network and the Autonomous System representation of the Internet map. Both networks have a modular structure, but differ in the way communities are assembled together. In the former, the modules are connected diversely (as for the synthetic networks analyzed before), while in the latter, different communities are interwoven mainly through a single module. The authors found that the transition to synchrony depends on the type of intermodular connections such that communities can mutually or independently synchronize. Modular networks are found in nature and they are commonly the result of a growth process. Nevertheless, these structural properties can also emerge as an adaptive mechanism generated by dynamical processes taking place in the existing network, and synchronization could be one of them. In particular, in [60] the authors studied the evolution of a network of Kuramoto oscillators. For a coupling strength below its critical value, the network is rewired by replacing links between neighbors with a large frequency difference with links between units with a small frequency difference. In this case, the network dynamically evolves to configurations that increase the order parameter. Along this evolution they noticed the appearance of synchronized groups (communities) that make the structure of the network to be more complex than the random starting one. Very recently [61], a slightly different model was considered, where the dynamics of each node is governed by x˙i = ωi + σ P j∈Γi b α(t) ij X j∈Γi b α(t) ij sin(xj − xi)βe β|xj−xi | being bij the betweenness centrality of the link, Γi the set of nodes that are connected to i, and α a time-dependent exponent. The authors use this dynamical evolution to identify communities. The betweenness is used as a measure of community coparticipation, since links between nodes that are in the same community have low betweenness [21]. Starting from a synchronized state, α is decreased from zero and then the corresponding interaction strength on those links is increasingly enhanced. An additional mechanism that adjusts frequencies between neighboring nodes causes the final state to show partial synchronization among nodes that are in the same community. 3.1.6. Synchronization by pacemakers It is worth mentioning the existence of other different approaches to the synchronization of populations of Kuramoto oscillators. So far we have referred to populations where the oscillators are nearly identical in the sense that they can have slightly different frequencies. Whenever there is a subset of units that play a special role, in the sense that they have substantially different frequencies than the rest in the population or they affect some units but are not affected by any of them, one usually refers to them as pacemakers. The effect of pacemakers has been studied in regular networks, as for instance in one-dimensional rings, two-dimensional tori and Cayley trees [62]. So far, the only approach in a complex topology has been performed in [63]. There, the authors considered a system of identical units (same frequency) and a singular pacemaker. For an ER network they found that for a large coupling the pacemaker entrains the whole system (all units with the same effective frequency, that of the pacemaker), but the phase distribution is hierarchically organized. Units at the same downward distance from the pacemaker form shells of common phases. As the coupling strength is decreased 7 Here stability (relative) of a given structure is understood to be the ratio between the final and initial times a partition remains synchronized. In terms of the number of connected components in Fig. 4 it corresponds to the length of the plateaus