Synchronization in complex networks of phase oscillators: A survey <s> B <s> Abstract We study phase-locking in a network of coupled nonlinear oscillators with local interactions and random intrinsic frequencies. The oscillators are located at the vertices of a graph and interact along the edges. They are coupled by sinusoidal functions of the phase differences across the edges, and their intrinsic frequencies are independent and identically distributed with finite mean and variance. We derive an exact expression for the probability of phase-locking in a linear chain of such oscillators and prove that this probability tends to zero as the number of oscillators grows without bound. However, if the coupling strength increases as the square root of the number of oscillators, the probability of phase-locking tends to a limiting distribution, the Kolmogorov-Smirnov distribution. This latter result is obtained by showing that the phase-locking problem is equivalent to a discretization of pinned Brownian motion. The results on chains of oscillators are extended to more general graphs. In particular, for a hypercubic lattice of any dimension, the probability of phase-locking tends to zero exponentially fast as the number of oscillators grows without bound. We also consider a less stringent type of synchronization, characterized by large clusters of oscillators mutually entrained at the same average frequency. It is shown that if such clusters exist, they necessarily have a sponge-like geometry. <s> BIB001 </s> Synchronization in complex networks of phase oscillators: A survey <s> B <s> The Kuramoto model describes a large population of coupled limit-cycle oscillators whose natural frequencies are drawn from some prescribed distribution. If the coupling strength exceeds a certain threshold, the system exhibits a phase transition: some of the oscillators spontaneously synchronize, while others remain incoherent. The mathematical analysis of this bifurcation has proved both problematic and fascinating. We review 25 years of research on the Kuramoto model, highlighting the false turns as well as the successes, but mainly following the trail leading from Kuramoto’s work to Crawford’s recent contributions. It is a lovely winding road, with excursions through mathematical biology, statistical physics, kinetic theory, bifurcation theory, and plasma physics. © 2000 Elsevier Science B.V. All rights reserved. <s> BIB002 </s> Synchronization in complex networks of phase oscillators: A survey <s> B <s> The study of networks pervades all of science, from neurobiology to statistical physics. The most basic issues are structural: how does one characterize the wiring diagram of a food web or the Internet or the metabolic network of the bacterium Escherichia coli? Are there any unifying principles underlying their topology? From the perspective of nonlinear dynamics, we would also like to understand how an enormous network of interacting dynamical systems — be they neurons, power stations or lasers — will behave collectively, given their individual dynamics and coupling architecture. Researchers are only now beginning to unravel the structure and dynamics of complex networks. <s> BIB003 </s> Synchronization in complex networks of phase oscillators: A survey <s> B <s> We consider a ring of identical or near-identical coupled periodic oscillators in which the connections have randomly heterogeneous strength. We use the master stability function method to determine the possible patterns at the desynchronization transition that occurs as the coupling strengths are increased. We demonstrate Anderson localization of the modes of instability and show that such localized instability generates waves of desynchronization that spread to the whole array. Similar results should apply to other networks with regular topology and heterogeneous connection strengths. <s> BIB004 </s> Synchronization in complex networks of phase oscillators: A survey <s> B <s> We provide an analysis of the classic Kuramoto model of coupled nonlinear oscillators that goes beyond the existing results for all-to-all networks of identical oscillators. Our work is applicable to oscillator networks of arbitrary interconnection topology with uncertain natural frequencies. Using tools from spectral graph theory and control theory, we prove that for couplings above a critical value, the synchronized state is locally asymptotically stable, resulting in convergence of all phase differences to a constant value, both in the case of identical natural frequencies as well as uncertain ones. We further explain the behavior of the system as the number of oscillators grows to infinity. <s> BIB005 </s> Synchronization in complex networks of phase oscillators: A survey <s> B <s> We study the transition from incoherence to coherence in large networks of coupled phase oscillators. We present various approximations that describe the behavior of an appropriately defined order parameter past the transition and generalize recent results for the critical coupling strength. We find that, under appropriate conditions, the coupling strength at which the transition occurs is determined by the largest eigenvalue of the adjacency matrix. We show how, with an additional assumption, a mean-field approximation recently proposed is recovered from our results. We test our theory with numerical simulations and find that it describes the transition when our assumptions are satisfied. We find that our theory describes the transition well in situations in which the mean-field approximation fails. We study the finite-size effects caused by nodes with small degree and find that they cause the critical coupling strength to increase. <s> BIB006 </s> Synchronization in complex networks of phase oscillators: A survey <s> B <s> Coupled biological and chemical systems, neural networks, social interacting species, the Internet and the World Wide Web, are only a few examples of systems composed by a large number of highly interconnected dynamical units. The first approach to capture the global properties of such systems is to model them as graphs whose nodes represent the dynamical units, and whose links stand for the interactions between them. On the one hand, scientists have to cope with structural issues, such as characterizing the topology of a complex wiring architecture, revealing the unifying principles that are at the basis of real networks, and developing models to mimic the growth of a network and reproduce its structural properties. On the other hand, many relevant questions arise when studying complex networks’ dynamics, such as learning how a large ensemble of dynamical systems that interact through a complex wiring topology can behave collectively. We review the major concepts and results recently achieved in the study of the structure and dynamics of complex networks, and summarize the relevant applications of these ideas in many different disciplines, ranging from nonlinear science to biology, from statistical mechanics to medicine and engineering. © 2005 Elsevier B.V. All rights reserved. <s> BIB007 </s> Synchronization in complex networks of phase oscillators: A survey <s> B <s> In this paper, we introduce a programmable particle swarm evolving on a sphere called swarm on sphere system. This model is a polynomial dynamical system obtained from a consensus algorithm that exhibits a rich set of synchronous behaviors with close connections to the Kuramoto model of coupled oscillators, coalition formation in social networks, small-words, integer programming problems such as max-cut, and networks of self-synchronous oscillators with applications to synthetic biology. We prove the generalized Kuramoto model can be obtained as a special case of this model in dimension two. Moreover, we provide formal stability analysis of aligned, bipolar, and dispersed synchronous modes of the system. As a byproduct of this stability analysis, we obtain simple algorithms for programming the weights of the swarm enabling it to exhibit various desired patterns of synchrony. Simulation results are provided that demonstrate 3-D in-phase synchrony, coalition formation for interacting agents with mixed-sign couplings, and dispersal behavior with spatial order. <s> BIB008 </s> Synchronization in complex networks of phase oscillators: A survey <s> B <s> The understanding of emergent collective phenomena in natural and social systems has driven the interest of scientists from different disciplines during decades. Among these phenomena, the synchronization of a set of interacting individuals or units has been intensively studied because of its ubiquity in the natural world. In this Letter, we show how for fixed coupling strengths local patterns of synchronization emerge differently in homogeneous and heterogeneous complex networks, driving the process towards a certain global synchronization degree following different paths. The dependence of the dynamics on the coupling strength and on the topology is unveiled. This study provides a new perspective and tools to understand this emerging phenomena. <s> BIB009 </s> Synchronization in complex networks of phase oscillators: A survey <s> B <s> The combination of the compactness of networks, featuring small diameters, and their complex architectures results in a variety of critical effects dramatically different from those in cooperative systems on lattices. In the last few years, researchers have made important steps toward understanding the qualitatively new critical phenomena in complex networks. We review the results, concepts, and methods of this rapidly developing field. Here we mostly consider two closely related classes of these critical phenomena, namely structural phase transitions in the network architectures and transitions in cooperative models on networks as substrates. We also discuss systems where a network and interacting agents on it influence each other. We overview a wide range of critical phenomena in equilibrium and growing networks including the birth of the giant connected component, percolation, k-core percolation, phenomena near epidemic thresholds, condensation transitions, critical phenomena in spin models placed on networks, synchronization, and self-organized criticality effects in interacting systems on networks. We also discuss strong finite size effects in these systems and highlight open problems and perspectives. <s> BIB010 </s> Synchronization in complex networks of phase oscillators: A survey <s> B <s> Synchronization in complex networks Alex Arenas, 1, 2, 3 Albert D´ iaz-Guilera, 4, 2 Jurgen Kurths, 5 Yamir Moreno, 2, 6 and Changsong Zhou 7 Departament d’Enginyeria Inform` tica i Matem` tiques, Universitat Rovira i Virgili, 43007 Tarragona, Spain a a Institute for Biocomputation and Physics of Complex Systems (BIFI), University of Zaragoza, Zaragoza 50009, Spain Lawrence Berkeley National Laboratory, Berkeley, CA 94720 Departament de F´ isica Fonamental, Universitat de Barcelona, 08028 Barcelona, Spain Institute of Physics, University of Potsdam PF 601553, 14415 Potsdam, Germany Department of Theoretical Physics, University of Zaragoza, Zaragoza 50009, Spain Department of Physics, Hong Kong Baptist University, Kowloon Tong, Hong Kong (Dated: February 6, 2008) Synchronization processes in populations of locally interacting elements are in the focus of intense research in physical, biological, chemical, technological and social systems. The many eﬀorts de- voted to understand synchronization phenomena in natural systems take now advantage of the recent theory of complex networks. In this review, we report the advances in the comprehension of synchronization phenomena when oscillating elements are constrained to interact in a complex network topology. We also overview the new emergent features coming out from the interplay between the structure and the function of the underlying pattern of connections. Extensive nu- merical work as well as analytical approaches to the problem are presented. Finally, we review several applications of synchronization in complex networks to diﬀerent disciplines: biological systems and neuroscience, engineering and computer science, and economy and social sciences. PACS numbers: 05.45.Xt,89.75.Fb,89.75.Hc Contents I. Introduction II. Complex networks in a nutshell III. Coupled phase oscillator models on complex networks A. Phase oscillators 1. The Kuramoto model 2. Kuramoto model on complex networks 3. Onset of synchronization in complex networks 4. Path towards synchronization in complex networks 5. Kuramoto model on structured or modular networks 6. Synchronization by pacemakers B. Pulse-coupled models C. Coupled maps IV. Stability of the synchronized state in complex networks A. Master Stability Function formalism 1. Linear Stability and Master Stability Function 2. Measures of synchronizability 3. Synchronizability of typical network models 4. Synchronizability and structural characteristics of networks 5. Graph theoretical bounds to synchronizability 6. Synchronizability of weighted networks 7. Universal parameters controlling the synchronizability B. Design of synchronizable networks 1. Weighted couplings for enhancing synchronizability 2. Topological modiﬁcation for enhancing synchronizability 3. Optimization of synchronizability C. Beyond the Master Stability Function formalism V. Applications A. Biological systems and neuroscience 1. Genetic networks 2. Circadian rhythms 3. Ecology 4. Neuronal networks 5. Cortical networks B. Computer science and engineering 1. Parallel/Distributed computation 2. Data mining 3. Consensus problems 4. Communication networks 5. Material and traﬃc ﬂow 6. Power-grids C. Social sciences and economy 1. Opinion formation 2. Finance 3. World Trade Web D. Perspectives VI. Conclusions Acknowledgments References I. INTRODUCTION Synchronization, as an emerging phenomenon of a pop- ulation of dynamically interacting units, has fascinated humans from ancestral times. No matter whether the phenomenon is spontaneous or induced, synchronization captivates our minds and becomes one of the most in- teresting scientiﬁc problems. Synchronization processes are ubiquitous in nature and play a very important role in many diﬀerent contexts as biology, ecology, climatol- ogy, sociology, technology, or even in arts ((Osipov et al., 2007; Pikovsky et al., 2001). It is known that synchrony <s> BIB011 </s> Synchronization in complex networks of phase oscillators: A survey <s> B <s> We derive a master stability function (MSF) for synchronization in networks of coupled dynamical systems with small but arbitrary parametric variations. Analogous to the MSF for identical systems, our generalized MSF simultaneously solves the linear-stability problem for near-synchronous states (NSS) for all possible connectivity structures. We also derive a general sufficient condition for stable near-synchronization and show that the synchronization error scales linearly with the magnitude of parameter variations. Our analysis underlines the significant role played by the Laplacian eigenvectors in the study of network synchronization of near-identical systems. <s> BIB012 </s> Synchronization in complex networks of phase oscillators: A survey <s> B <s> In this brief, the contraction theory is applied to the synchronization of a network. The association between the contraction principle, the Lyapunov exponents of a system, and the master stability function of the network is pointed out. Novel sufficient criteria for the fulfillment of a synchronous state are derived. <s> BIB013 </s> Synchronization in complex networks of phase oscillators: A survey <s> B <s> We analyze populations of Kuramoto oscillators with a particular distribution of natural frequencies. Inspired by networks where there are two groups of nodes with opposite behaviors, as for instance in power-grids where energy is either generated or consumed at different locations, we assume that the frequencies can take only two different values. Correlations between the value of the frequency of a given node and its topological localization are considered in both regular and random topologies. Synchronization is enhanced when nodes are surrounded by nodes of the opposite frequency. We find analytical estimations for the minimum value of the coupling strength between oscillators that guarantees the achievement of a globally synchronized state, getting a very good agreement with the numerical simulations. <s> BIB014 </s> Synchronization in complex networks of phase oscillators: A survey <s> B <s> We study the synchronization properties of the Kuramoto model of coupled phase oscillators on a general network. Here we distinguish the ability of such a system to self-synchronize from the stability of this behavior. While self-synchronization is a consequence of genuine nonperturbative dynamics, the stability in dynamical systems is usually accessible by fluctuations about a fixed point, here taken to be the phase synchronized solution. We examine this problem in terms of modes of the graph Laplacian, by which the absolute Lyapunov stability of the phase synchronized fixed point is readily demonstrated. Departures from stability are seen to arise at the next order in fluctuations where, depending on a truncation in the number of time-dependent Laplacian modes, the dynamical equations can be reduced to forms resembling those for species population models, the logistic and the Lotka-Volterra equations. Methods from these systems are exploited to analytically derive new critical couplings signaling deviation from classical stability. We thereby analytically explain the existence of an intermediate regime of behavior between incoherence and synchronization, where system wide periodic behaviors are exhibited and stable, unstable, and hyperbolic fixed points can be identified. We discuss these results in light of numerical solutions of the equations of motion for various networks. <s> BIB015 </s> Synchronization in complex networks of phase oscillators: A survey <s> B <s> Motivated by recent interest for multi-agent systems and smart power grid architectures, we discuss the synchronization problem for the network-reduced model of a power system with non-trivial transfer conductances. Our key insight is to exploit the relationship between the power network model and a first-order model of coupled oscillators. Assuming overdamped generators (possibly due to local excitation controllers), a singular perturbation analysis shows the equivalence between the classic swing equations and a non-uniform Kuramoto model. Here, non-uniform Kuramoto oscillators are characterized by multiple time constants, non-homogeneous coupling, and non-uniform phase shifts. Extending methods from transient stability, synchronization theory, and consensus protocols, we establish sufficient conditions for synchronization of non-uniform Kuramoto oscillators. These conditions reduce to and improve upon previously-available tests for the standard Kuramoto model. Combining our singular perturbation and Kuramoto analyses, we derive concise and purely algebraic conditions that relate synchronization and transient stability of a power network to the underlying system parameters and initial conditions. <s> BIB016 </s> Synchronization in complex networks of phase oscillators: A survey <s> B <s> In this letter, we perform a sensitivity analysis on the master stability function approach for the synchronization of networks of coupled dynamical systems. More specifically, we analyze the linear stability of a nearly synchronized solution for a network of coupled dynamical systems, for which the individual dynamics and output functions of each unit are approximately identical and the sums of the entries in the rows of the coupling matrix slightly deviate from zero. The motivation for this parametric study comes from experimental instances of synchronization in human-made or natural settings, where ideal conditions are difficult to observe. <s> BIB017 </s> Synchronization in complex networks of phase oscillators: A survey <s> B <s> We introduce a model to study the effect of degree-frequency correlations on synchronization in networks of coupled oscillators. Analyzing this model, we find several remarkable characteristics. We find a stationary synchronized state that is i) universal, i.e., the degree of synchrony, as measured by a global order parameter, is independent of network topology, and ii) fully phase-locked, i.e., all oscillators become simultaneously phase-locked despite having different natural frequencies. This state separates qualitatively different behaviors for two other classes of correlations where, respectively, slow and fast oscillators can remain unsynchronized. We close by presenting an analysis of the dynamics under arbitrary degree-frequency correlations. <s> BIB018 </s> Synchronization in complex networks of phase oscillators: A survey <s> B <s> The emergence of synchronization in a network of coupled oscillators is a fascinating topic in various scientific disciplines. A widely adopted model of a coupled oscillator network is characterized by a population of heterogeneous phase oscillators, a graph describing the interaction among them, and diffusive and sinusoidal coupling. It is known that a strongly coupled and sufficiently homogeneous network synchronizes, but the exact threshold from incoherence to synchrony is unknown. Here, we present a unique, concise, and closed-form condition for synchronization of the fully nonlinear, nonequilibrium, and dynamic network. Our synchronization condition can be stated elegantly in terms of the network topology and parameters or equivalently in terms of an intuitive, linear, and static auxiliary system. Our results significantly improve upon the existing conditions advocated thus far, they are provably exact for various interesting network topologies and parameters; they are statistically correct for almost all networks; and they can be applied equally to synchronization phenomena arising in physics and biology as well as in engineered oscillator networks, such as electrical power networks. We illustrate the validity, the accuracy, and the practical applicability of our results in complex network scenarios and in smart grid applications. <s> BIB019 </s> Synchronization in complex networks of phase oscillators: A survey <s> B <s> We develop analytical and numerical conditions to determine whether limit cycle oscillations synchronize in diffusively coupled systems. We examine two classes of systems: reaction-diffusion PDEs with Neumann boundary conditions, and compartmental ODEs, where compartments are interconnected through diffusion terms with adjacent compartments. In both cases the uncoupled dynamics are governed by a nonlinear system that admits an asymptotically stable limit cycle. We provide two-time scale averaging methods for certifying stability of spatially homogeneous time-periodic trajectories in the presence of sufficiently small or large diffusion and develop methods using the structured singular value for the case of intermediate diffusion. We highlight cases where diffusion stabilizes or destabilizes such trajectories. <s> BIB020
T ω p , for p ∈ N. Here, we specifically consider the three incremental norms: , where the subscript cplt stands for the complete graph. With slight abuse of notation, we also adopt these incremental norms for angular distances. For example, for γ ∈ [0, π[, the incremental ∞-norm ball {θ ∈ T n | θ E∞ ≤ γ} is identical to the phase cohesive set ∆ G (γ). As every review article on synchronization BIB002 BIB003  BIB007 BIB011 BIB010 BIB019 , let us state here that the problem of finding sharp and provably correct synchronization conditions is not yet completely solved. Some of the proposed synchronization conditions for complex phase oscillator networks can be evaluated only numerically since they are state-dependent Kumagai, 1980, 1982) or arise from a non-trivial linearization process of full state space oscillator models. The latter procedure is adopted in the widely-studied Master Stability Function formalism, see  BIB007 BIB011 for the original reference and relevant surveys, see BIB004 BIB012 BIB017 for its extension to quasi-identical oscillators, and see BIB020 BIB013 ) for related linearizationbased approaches from the control community. In general, concise and accurate results are known only for specific topologies such as complete graphs (as discussed in the previous section), linear chains BIB001 , highly symmetric ring graphs BIB014 , acyclic graphs  , and complete bipartite graphs  ) with uniform weights. For arbitrary coupling topologies, the literature contains only sufficient conditions Kumagai, 1980, 1982; BIB005 BIB016 as well as numerical and statistical investigations for large random net-11 More precisely, the incremental norms B T ω p are seminorms in R n and proper norms in the quotient space 1 ⊥ n . works indicating certain (e.g., degree-dependent) scaling laws BIB008 BIB006 BIB009  BIB015 BIB018 . Numerical studies indicate that all known and provablycorrect synchronization conditions are conservative estimates on the threshold from incoherence to synchrony. Our recently-proposed condition is provably correct for various extremal network topologies and weights, and is numerically accurate for a broad range of random networks; a complete analytic treatment is missing at this time. In the following, we review a set of known and provably correct synchronization conditions and analysis concepts.