Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> The flow function of a power system is the vector of node powers expressed in terms of the node angles. The Jacobian is the matrix of partial derivatives of the flow vector with respect to the angle vector. The ratio of the determinant of the Jacobian to the value which it has when the node angles are set to zero is a dimensionless stability margin which lies between one and zero (steady-state in- stability) and is easily computed from a load flow. The margin of torque is the least change in power flows that will cause instability. Maximizing the torque margin or maximizing the stability margin with a load constraint yields the optimum dispatching change to maximize security. <s> BIB001 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> Practical experience with load-flow solutions has indicated that stable solutions are probably unique, given sufficient data about a network to determine a solution from the standpoint of dimensionality, i.e., having as many equations as variables for the remaining unknowns. A counterexample is given here for which two stable solutions exist, and an approach towards the analysis of uniqueness is presented that adds some insight into the nature of load-flow solutions in general. <s> BIB002 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> A new model for the study of power system stability via Lyapunov functions is proposed. The key feature of the model is an assumption of frequency-dependent load power, rather than the usual impedance loads which are subsequently absorbed into a reduced network. The original network topology is explicitly represented. This approach has the important advantage of rigorously accounting for real power loads in the Lyapunov functions. This compares favorably with existing methods involving approximations to allow for the significant transfer conductances in reduced network models. The preservation of network topology can be exploited in stability analysis, with the concepts of critical and vulnerable cutsets playing central roles in dynamic and transient stability evaluation respectively. Of fundamental importance is the feature that the Lyapunov functions give a true representation of the spatial distribution of stored energy in the system <s> BIB003 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> Abstract The qualitative properties of the power-flow equation for a transmission network are studied in terms of global and local aspects, as well as stability. Global aspects include estimates of the number of solutions and topological properties of the stable region. Local aspects are examined through bifurcations of the flow equation. Examples are given to counter some intuitive conjectures, and other conjectures are made. <s> BIB004 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> Electric utility analysts today face an increasingly difficult task of formulating both long and short term operating plans which will provide at the same time efficient and economical operation while delivering reliable and uninterrupted service to electricity users. One of the key ingredients in this planning is a set of large scale simulations of the steady-state network performance under various anticipated operating conditions. Central to these analyses are the classical "load flow" equations which are the equilibrium equations for the "swing equations" which are a physically based model of the dynamic operation of an n -node power system. Despite the long standing and widespread use of these equations, there remain a number of very basic open questions: What are the number and nature of the equilibria of the swing equations? How many stable equilibrium operating points are there in an n -node electric power grid? In this paper some powerful analytical tools from topology and geometry are used to answer certain of these questions. It is well documented that the load flow equations comprise a formidable large scale system but what is interesting, and perhaps surprising, is that even for a small number of buses, these equations possess a rather rich and intricate qualitative behavior which has heretofor been only partially understood. Indeed, until now there was no complete statement in the literature concerning the number of load flows in a general three-bus network. In Theorem 2.7, we state that for the "generic" three-bus network there are, for sufficiently small power injections, either four or six real load flows and that, in either case, exactly one of those load flows is stable. This is a special case of the results we derive for a general n -bus powergrid. Our method consists in first transforming the load flow equations for a lossless electric power network by trigonometric substitutions into algebraic equations. This makes it possible to apply some deep and powerful results from algebraic geometry and intersection theory to study these equations. An obvious tool for determining the number of solutions is provided by the classical theorem of Bezout, but it is shown that for systems describing an n -machine network with n \geq 4 , this result cannot be directly applied because the solutions contain solution components of positive dimension "at infinity." A major result in this paper is a modified Bezout technique which allows us to compute the number of complex (and a fortiori an upper bound on the number of real) solutions to the load flow equations. Combining this with the classical Morse inequalities, we obtain very explicit results regarding the number of stable load flows for a given network topology and set of power injections. The cases of three and four machine networks are considered in detail. <s> BIB005 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> A simple model for synchronous firing of biological oscillators based on Peskin's model of the cardiac pacemaker (Mathematical aspects of heart physiology, Courant Institute of Mathematical Sciences, New York University, New York, 1975, pp. 268-278) is studied. The model consists of a population of identical integrate-and-fire oscillators. The coupling between oscillators is pulsatile: when a given oscillator fires, it pulls the others up by a fixed amount, or brings them to the firing threshold, whichever is less. The main result is that for almost all initial conditions, the population evolves to a state in which all the oscillators are firing synchronously. The relationship between the model and real communities of biological oscillators is discussed; examples include populations of synchronously flashing fireflies, crickets that chirp in unison, electrically synchronous pacemaker cells, and groups of women whose menstrual cycles become mutually synchronized. <s> BIB006 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> Abstract A phase model is proposed and studied for a population of integrate-and-fire-type oscillators and excitable units with pulsatile coupling. The units are subject to external noise, and their mutual connection is all-to-all. An evolution equation is derived for the phase distribution in a closed form. Its steady-state analysis in the limit of weak noise shows the possibility of collective bistability. The evolution equation is simplified drastically when the coupling as well as noise is sufficiently weak. This reduction of equation enables analytical calculation of various quantities. Among others, the stability of the steady distribution is analyzed explicity, and the onset of collective oscillations is described in terms of the Hopf bifurcation. It is also shown that the present model is improved in some respects by introducing absolute refractoriness. <s> BIB007 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> We describe a new model for synchronization of neuronal oscillators that is based on the observation that certain species of fireflies are able to alter their free-running period. We show that by adding adaptation to standard oscillator models it is possible to observe the frequency alteration. One consequence of this is the perfect synchrony between coupled oscillators. Stability and some analytic results are included along with numerical simulations. <s> BIB008 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> Publisher Summary ::: Chaotic systems would seem to be dynamical systems that defy synchronization. Two identical autonomous chaotic systems started at nearly the same initial points in phase space have trajectories which quickly become uncorrelated, even though each maps out the same attractor in phase space. It is thus a practical impossibility to construct identical, chaotic, synchronized systems in the laboratory. This chapter describes the linking of two chaotic systems with a common signal or signals. It highlights that when the signs of the Lyapunov exponents for the subsystems are all negative the systems are synchronized. By synchronize it means that the trajectories of one of the systems converge to the same values as the other and they remain in step with each other. The synchronization appears to be structurally stable. <s> BIB009 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> Research was supported in part by the ONR under Contract No. N00014-J- 1257, NATO Collaborative Research Grant No. CRG- 950282, NSF Grants Nos. DMS-9057433 and DMS- 9500948, and DGICYT ~Spain! Grant No. PB94-1167. <s> BIB010 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <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> BIB011 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> 1. Introduction. 2. Electromagnetic Transients. 3. Synchronous Machine Modeling. 4. Synchronous Machine Control Models. 5. Single-Machine Dynamic Models. 6. Multimachine Dynamic Models. 7. Multimachine Simulation. 8. Small-Signal Stability. 9. Energy Function Methods. Appendix A: Integral Manifolds for Model. Bibliography. Index. <s> BIB012 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> We investigate here possible neurocomputational features of networks of laser oscillators. Our approach is similar to classical optical neurocomputing where artificial neurons are lasers and connection matrices are holographic media. However, we consider oscillatory neurons communicating via phases rather than amplitudes. Memorized patterns correspond to synchronized states where the neurons oscillate with equal frequencies and with prescribed phase relations. The mechanism of recognition is related to phase locking. <s> BIB013 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> Synchronization is a common phenomenon in physical and biological systems. We examine the synchronization of two (and more) metronomes placed on a freely moving base. The small motion of the base couples the pendulums causing synchronization. The synchronization is generally in-phase, with antiphase synchronization occurring only under special conditions. The metronome system provides a mechanical realization of the popular Kuramoto model for synchronization of biological oscillators, and is excellent for classroom demonstrations and an undergraduate physics lab. <s> BIB014 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> Coupled oscillator models use a single phase variable to approximate the voltage oscillation of each neuron during repetitivefiring where the behavior of the model depends on the connectivityand the interaction function chosen to describe the coupling. Weintroduce a network model consisting of a continuum of theseoscillators that includes the effects of spatially decaying coupling and axonal delay. We derive equations for determining the stability of solutions and analyze the network behavior for two different interaction functions. The first is a sine function, and the second is derived from a compartmental model of a pyramidal cell.In both cases, the system of coupled neural oscillators can undergo a bifurcation from synchronous oscillations to waves.The change in qualitative behavior is due to the axonal delay,which causes distant connections to encourage a phase shift between cells. We suggest that this mechanism could contribute to the behavior observed in several neurobiological systems. <s> BIB015 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> A complex high-dimensional chaotic behavior, phase chaos, is found in the finite-dimensional Kuramoto model of coupled phase oscillators. This type of chaos is characterized by half of the spectrum of Lyapunov exponents being positive and the Lyapunov dimension equaling almost the total system dimension. Intriguingly, the strongest phase chaos occurs for intermediate-size ensembles. Phase chaos is a common property of networks of oscillators of very different natures, such as phase oscillators, limit-cycle oscillators, and chaotic oscillators, e.g., Rössler systems. <s> BIB016 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> Footbridges start to sway when packed with pedestrians falling into step with their vibrations. <s> BIB017 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <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> BIB018 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> A survey of the use of graph theoretical techniques in Biology is presented. In particular, recent work on identifying and modelling the structure of bio-molecular networks is discussed, as well as the application of centrality measures to interaction networks and research on the hierarchical structure of such networks and network motifs. Work on the link between structural network properties and dynamics is also described, with emphasis on synchronisation and disease propagation. <s> BIB019 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> We study the emergence of collective synchronization in large directed networks of heterogeneous oscillators by generalizing the classical Kuramoto model of globally coupled phase oscillators to more realistic networks. We extend recent theoretical approximations describing the transition to synchronization in large undirected networks of coupled phase oscillators to the case of directed networks. We also consider the case of networks with mixed positive-negative coupling strengths. We compare our theory with numerical simulations and find good agreement. <s> BIB020 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> This book explains the relationship of electrophysiology, nonlinear dynamics, and the computational properties of neurons, with each concept presented in terms of both neuroscience and mathematics and illustrated using geometrical intuition. In order to model neuronal behavior or to interpret the results of modeling studies, neuroscientists must call upon methods of nonlinear dynamics. This book offers an introduction to nonlinear dynamical systems theory for researchers and graduate students in neuroscience. It also provides an overview of neuroscience for mathematicians who want to learn the basic facts of electrophysiology. "Dynamical Systems in Neuroscience" presents a systematic study of the relationship of electrophysiology, nonlinear dynamics, and computational properties of neurons. It emphasizes that information processing in the brain depends not only on the electrophysiological properties of neurons but also on their dynamical properties. The book introduces dynamical systems starting with one- and two-dimensional Hodgkin-Huxley-type models and continuing to a description of bursting systems. Each chapter proceeds from the simple to the complex, and provides sample problems at the end. The book explains all necessary mathematical concepts using geometrical intuition; it includes many figures and few equations, making it especially suitable for non-mathematicians. Each concept is presented in terms of both neuroscience and mathematics, providing a link between the two disciplines. Nonlinear dynamical systems theory is at the core of computational neuroscience research, but it is not a standard part of the graduate neuroscience curriculum - or taught by math or physics department in a way that is suitable for students of biology. This book offers neuroscience students and researchers a comprehensive account of concepts and methods increasingly used in computational neuroscience. <s> BIB021 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> We suggest a new line of research that we hope will appeal to the nonlinear dynamics community, especially the readers of this Focus Issue. Consider a network of identical oscillators. Suppose the synchronous state is locally stable but not globally stable; it competes with other attractors for the available phase space. How likely is the system to synchronize, starting from a random initial condition? And how does the probability of synchronization depend on the way the network is connected? On the one hand, such questions are inherently difficult because they require calculation of a global geometric quantity, the size of the "sync basin" (or, more formally, the measure of the basin of attraction for the synchronous state). On the other hand, these questions are wide open, important in many real-world settings, and approachable by numerical experiments on various combinations of dynamical systems and network topologies. To give a case study in this direction, we report results on the sync basin for a ring of n >> 1 identical phase oscillators with sinusoidal coupling. Each oscillator interacts equally with its k nearest neighbors on either side. For k/n greater than a critical value (approximately 0.34, obtained analytically), we show that the sync basin is the whole phase space, except for a set of measure zero. As k/n passes below this critical value, coexisting attractors are born in a well-defined sequence. These take the form of uniformly twisted waves, each characterized by an integer winding number q, the number of complete phase twists in one circuit around the ring. The maximum stable twist is proportional to n/k; the constant of proportionality is also obtained analytically. For large values of n/k, corresponding to large rings or short-range coupling, many different twisted states compete for their share of phase space. Our simulations reveal that their basin sizes obey a tantalizingly simple statistical law: the probability that the final state has q twists follows a Gaussian distribution with respect to q. Furthermore, as n/k increases, the standard deviation of this distribution grows linearly with square root of n/k. We have been unable to explain either of these last two results by anything beyond a hand-waving argument. <s> BIB022 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> We present a system of coupled nonlinear oscillators to be used as programmable central pattern generators, and apply it to control the locomotion of a humanoid robot. Central pattern generators are biological neural networks that can produce coordinated multidimensional rhythmic signals, under the control of simple input signals. They are found both in vertebrate and invertebrate animals for the control of locomotion. In this article, we present a novel system composed of coupled adaptive nonlinear oscillators that can learn arbitrary rhythmic signals in a supervised learning framework. Using adaptive rules implemented as differential equations, parameters such as intrinsic frequencies, amplitudes, and coupling weights are automatically adjusted to replicate a teaching signal. Once the teaching signal is removed, the trajectories remain embedded as the limit cycle of the dynamical system. An interesting aspect of this approach is that the learning is completely embedded into the dynamical system, and does not require external optimization algorithms. We use our system to encapsulate rhythmic trajectories for biped locomotion with a simulated humanoid robot, and demonstrate how it can be used to do online trajectory generation. The system can modulate the speed of locomotion, and even allow the reversal of direction (i.e. walking backwards). The integration of sensory feedback allows the online modulation of trajectories such as to increase the basin of stability of the gaits, and therefore the range of speeds that can be produced <s> BIB023 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <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> BIB024 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <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> BIB025 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <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> BIB026 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> We consider the Kuramoto model of globally coupled phase oscillators subject to Ornstein-Uhlenbeck and non-Gaussian colored noise and investigate the influence of noise on the order parameter of the synchronization process. We use numerical methods to study the dependence of the threshold as well as the maximum degree of synchronization on the correlation time and the strength of the noise, and find that the threshold of synchronization strongly depends on the nature of the noise. It is found to be lower for both the Ornstein-Uhlenbeck and non-Gaussian processes compared to the case of white noise. A finite correlation time also favors the achievement of the full synchronization of the system, in contract to the white noise process, which does not allow that. Finally, we discuss possible applications of the stochastic Kuramoto model to oscillations taking place in biochemical systems. <s> BIB027 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> Abstract Although modifications of the Kuramoto model have been the subject of extensive research, the model itself is not yet fully understood. We offer several results and observations, some analytic, others through simulations. We derive a sufficient condition for the existence of a solution exhibiting partial entrainment with respect to a given subset of oscillators; the result also implies persistence of the entrainment behavior under perturbations. The critical values of the coupling strength, defining the transitions between different forms of partial entrainment, are predicted by an analytical approximation, based on the fact that oscillators with large differences in their natural frequencies have little influence on each other’s entrainment behavior; the predictions agree with the actual values, obtained by simulations. We indicate (by simulations) that entrainment can disappear with increasing coupling strength, and that, in arrays of Josephson junctions, a similar phenomenon can be observed, where it is also possible that a junction leaving one entrained subset joins another entrained subset. <s> BIB028 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> We pursue a group coordination problem where the objective is to steer the differences between output variables of the group members to a prescribed compact set. To stabilize this set we study a class of feedback rules that are implementable with local information available to each member. When the information flow between neighboring members is bidirectional, we show that the closed-loop system exhibits a special interconnection structure which inherits the passivity properties of its components. By exploiting this structure we develop a passivity-based design framework, which results in a broad class of feedback rules that encompass as special cases some of the existing formation stabilization and group agreement designs in the literature. The passivity approach offers additional design flexibility compared to these special cases, and systematically constructs a Lurie-type Lyapunov function for the closed-loop system. We further study the robustness of these feedback laws in the presence of a time-varying communication topology, and present a persistency of excitation condition which allows the interconnection graph to lose connectivity pointwise in time as long as it is established in an integral sense. <s> BIB029 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> This article has explored history, recent advances, and challenges in distributed synchronization for distributed wireless systems. It is focused on synchronization schemes based on exchange of signals at the physical layer and corresponding baseband processing, wherein analysis and design can be performed using known tools from signal processing. Emphasis has also been given on the synergy between distributed synchronization and distributed estimation/detection problems. Finally, we have touched upon synchronization of nonperiodic (chaotic) signals. Overall, we hope to have conveyed the relevance of the subject and to have provided insight on the open issues and available analytical tools that could inspire further research within the signal processing community. <s> BIB030 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <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> BIB031 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <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> BIB032 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <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> BIB033 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <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> BIB034 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> We present a planar agent-based flocking model with a distance-dependent communication weight. We derive a sufficient condition for the asymptotic flocking in terms of the initial spatial and heading-angle diameters and a communication weight. For this, we employ differential inequalities for the spatial and phase diameters together with the Lyapunov functional approach. When the diameter of the agent's initial heading-angles is sufficiently small, we show that the diameter of the heading-angles converges to the average value of the initial heading-angles exponentially fast. As an application of flocking estimates, we also show that the Kuramoto model with a connected communication topology on the regular lattice for identical oscillators exhibits a complete-phase-frequency synchronization, when coupled oscillators are initially distributed on the half circle. <s> BIB035 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> The Kuramoto model captures various synchronization phenomena in biological and man-made systems of coupled oscillators. It is well-known that there exists a critical coupling strength among the oscillators at which a phase transition from incoherency to synchronization occurs. This paper features four contributions. First, we characterize and distinguish the different notions of synchronization used throughout the literature and formally introduce the concept of phase cohesiveness as an analysis tool and performance index for synchronization. Second, we review the vast literature providing necessary, sufficient, implicit, and explicit estimates of the critical coupling strength for finite and infinite-dimensional, and for first and second-order Kuramoto models. Third, we present the first explicit necessary and sufficient condition on the critical coupling to achieve synchronization in the finite-dimensional Kuramoto model for an arbitrary distribution of the natural frequencies. The multiplicative gap in the synchronization condition yields a practical stability result determining the admissible initial and the guaranteed ultimate phase cohesiveness as well as the guaranteed asymptotic magnitude of the order parameter. Fourth and finally, we extend our analysis to multi-rate Kuramoto models consisting of second-order Kuramoto oscillators with inertia and viscous damping together with first-order Kuramoto oscillators with multiple time constants. We prove that the multi-rate Kuramoto model is locally topologically conjugate to a first-order Kuramoto model with scaled natural frequencies, and we present necessary and sufficient conditions for almost global phase synchronization and local frequency synchronization. Interestingly, these conditions do not depend on the inertiae which contradicts prior observations on the role of inertiae in synchronization of second-order Kuramoto models. <s> BIB036 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> We study the stationary points of what is known as the lattice Landau gauge fixing functional in one-dimensional compact U(1) lattice gauge theory, or as the Hamiltonian of the one-dimensional random phase XY model in statistical physics. An analytic solution of all stationary points is derived for lattices with an odd number of lattice sites and periodic boundary conditions. In the context of lattice gauge theory, these stationary points and their indices are used to compute the gauge fixing partition function, making reference in particular to the Neuberger problem. Interpreted as stationary points of the one-dimensional XY Hamiltonian, the solutions and their Hessian determinants allow us to evaluate a criterion which makes predictions on the existence of phase transitions and the corresponding critical energies in the thermodynamic limit. <s> BIB037 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> We consider a generalization of the Kuramoto model in which the oscillators are coupled to the mean field with random signs. Oscillators with positive coupling are ``conformists''; they are attracted to the mean field and tend to synchronize with it. Oscillators with negative coupling are ``contrarians''; they are repelled by the mean field and prefer a phase diametrically opposed to it. The model is simple and exactly solvable, yet some of its behavior is surprising. Along with the stationary states one might have expected (a desynchronized state, and a partially-synchronized state, with conformists and contrarians locked in antiphase), it also displays a traveling wave, in which the mean field oscillates at a frequency different from the population's mean natural frequency. <s> BIB038 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> Synchronization on the nanoscale has a wide range of applications ranging from timing, navigation, signal processing, microwave communication and novel computing and memory concepts. Existing coupled micromechanical oscillators suffer from limited range, neighborhood restriction and non-configurable coupling which limit the control, physical size and possible topologies of complex oscillator networks [1]. Here, we demonstrate the synchronization of two micromechanical oscillators, which are actuated and coupled by optical radiation field. We show that the coupling between the two oscillators can be tuned continuously from uncoupled to maximally coupled. These results pave a path towards massive and long-range synchronized oscillator networks. <s> BIB039 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> Abstract We present an approach based on Gronwall’s inequalities for the asymptotic complete phase–frequency synchronization of Kuramoto oscillators with finite inertia. For given finite inertia and coupling strength, we present admissible classes of initial configurations and natural frequency distributions, which lead to the complete phase–frequency synchronization asymptotically. For this, we explicitly identify invariant regions for the Kuramoto flow, and derive second-order Gronwall’s inequalities for the evolution of phase and frequency diameters. Our detailed time-decay estimates for phase and frequency diameters are independent of the number of oscillators. We also compare our analytical results with numerical simulations. <s> BIB040 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> We present the long-time dynamics of unidirectionally coupled identical Kuramoto oscillators in a ring, when each oscillator is influenced sinusoidally by a single preassigned oscillator. In this situation, for a large system with $N \geq 5$, it is well known that the synchronized states and the splay-state are the only stable equilibria by Gershgorin's theorem and linear stability analysis, whereas for low-dimensional systems with $N=2,3$ the synchronized state is the unique stable equilibrium. We present nontrivial proper subsets of synchronized and splay-state basins with positive Lebesgue measure in $N$-phase space. For the threshold case $N=4$, we show that the splay-state is nonlinearly unstable by explicit construction of perturbations converging toward the synchronized state asymptotically. <s> BIB041 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> We consider Kuramoto-Sakaguchi type model of globally coupled phase oscillators with positive and negative coupling parameters. Such type of model with natural motivation was proposed for consideration by H. Hong and S.H. Strogatz where they obtained interesting and unexpected results. Our aim is to do bifurcation analysis for the finite-dimensional case of identical oscillators when phase shift is involved. We describe invariant manifolds and find complicated heteroclinic constructions, chaos and multistability in the system. <s> BIB042 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> Abstract In this report we recall the famous Huygens’ experiment which gave the first evidence of the synchronization phenomenon. We consider the synchronization of two clocks which are accurate (show the same time) but have pendula with different masses. It has been shown that such clocks hanging on the same beam can show the almost complete (in-phase) and almost antiphase synchronizations. By almost complete and almost antiphase synchronization we defined the periodic motion of the pendula in which the phase shift between the displacements of the pendula is respectively close (but not equal) to 0 or π . We give evidence that almost antiphase synchronization was the phenomenon observed by Huygens in XVII century. We support our numerical studies by considering the energy balance in the system and showing how the energy is transferred between the pendula via oscillating beam allowing the pendula’s synchronization. Additionally we discuss the synchronization of a number of different pendulum clocks hanging from a horizontal beam which can roll on the parallel surface. It has been shown that after a transient, different types of synchronization between pendula can be observed; (i) the complete synchronization in which all pendula behave identically, (ii) pendula create three or five clusters of synchronized pendula. We derive the equations for the estimation of the phase differences between phase synchronized clusters. The evidence, why other configurations with a different number of clusters are not observed, is given. <s> BIB043 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <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> BIB044 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> We consider Kuramoto model of phase oscillators with attractive-repulsive interconnections, that is, part of interconnection gains can be negative. We generalize results on existence of phase locked solutions of input-output weighted sign-symmetric interconnections and present corresponding necessary and sufficient conditions for phase locking. We give an expression for synchronization frequency, which appears to be independent of signs appearing in the interconnection matrix. Local asymptotic stability of phase locked solutions is analysed and finally our results are illustrated through a demonstrative example. <s> BIB045 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> The synchronization of coupled oscillators is a fascinating manifestation of self-organization that nature employs to orchestrate essential processes of life, such as the beating of the heart. Although it was long thought that synchrony or disorder were mutually exclusive steady states for a network of identical oscillators, numerous theoretical studies in recent years have revealed the intriguing possibility of `chimera states', in which the symmetry of the oscillator population is broken into a synchronous and an asynchronous part. However, a striking lack of empirical evidence raises the question of whether chimeras are indeed characteristic to natural systems. This calls for a palpable realization of chimera states without any fine-tuning, from which physical mechanisms underlying their emergence can be uncovered. Here, we devise a simple experiment with mechanical oscillators coupled in a hierarchical network to show that chimeras emerge naturally from a competition between two antagonistic synchronization patterns. We identify a wide spectrum of complex states, encompassing and extending the set of previously described chimeras. Our mathematical model shows that the self-organization observed in our experiments is controlled by elementary dynamical equations from mechanics that are ubiquitous in many natural and technological systems. The symmetry breaking mechanism revealed by our experiments may thus be prevalent in systems exhibiting collective behaviour, such as power grids, opto-mechanical crystals or cells communicating via quorum sensing in microbial populations. <s> BIB046 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> This paper studies cluster synchronization in dynamical networks. A class of cooperative dynamical networks that exhibit clustering in their asymptotic behavior is analyzed. The network nodes are equipped with heterogeneous dynamics and interact with a nonlinear and saturated interaction rule. It is proven that cluster synchronization appears asymptotically independent of the initial conditions. The clustering behavior of the dynamic network is shown to correspond to the solution of a static saddle-point problem, enabling a precise characterization of the clustering structure. We show how the clustering structure depends on the relation between the underlying graph, the node dynamics, and the saturation level of the interactions. This interpretation leads to deeper combinatorial insights related to clustering, including a generalization of classical network partitioning problems such as the inhibiting bisection problem, the min s-t-cut problem, and hierarchical clustering analysis. The theoretical results are applied for the analysis of a test-case network, inspired by the IEEE 30-bus system. <s> BIB047 </s> Synchronization in complex networks of phase oscillators: A survey <s> Conclusions and Open Research Directions <s> An imperative condition for the functioning of a power-grid network is that its power generators remain synchronized. Disturbances can prompt desynchronization, which is a process that has been involved in large power outages. Here we derive a condition under which the desired synchronous state of a power grid is stable, and use this condition to identify tunable parameters of the generators that are determinants of spontaneous synchronization. Our analysis gives rise to an approach to specify parameter assignments that can enhance synchronization of any given network, which we demonstrate for a selection of both test systems and real power grids. Because our results concern spontaneous synchronization, they are relevant both for reducing dependence on conventional control devices, thus offering an additional layer of protection given that most power outages involve equipment or operational errors, and for contributing to the development of "smart grids" that can recover from failures in real time. <s> BIB048
In this paper we introduced the reader to the coupled oscillator model (1), we reviewed several applications, we discussed different synchronization notions, and we presented different analysis approaches and results for phase synchronization, phase balancing, pattern formation, frequency synchronization, and partial synchronization. We covered complete and sparse network topologies, homogeneous and heterogeneous natural frequencies, and finite and infinite oscillator populations. Despite the vast literature, the countless applications, and the numerous theoretical results on the synchronization properties of model (1), many interesting and important problems are still open. In the following, we summarize limitations of the existing analysis approaches and present a few worthwhile directions for future research. Generalized interactions: Most of the results presented in this paper can be extended to more general anti-symmetric and 2π-periodic coupling functions as long as the coupling is diffusive and bidirectional. In some applications, the coupling topology is inherently directed, such as transcriptional, metabolic, or neuronal networks BIB019 . In this case, there are only a few theoretical investigations including analyses for ring graphs BIB041 and acyclic graphs  , results on the synchronization frequency (El Ati and Panteley, 2013a; BIB034 , and statistical analysis of large graphs BIB020 . Also, in many applications the diffusive coupling includes a phase shift BIB021 . For instance, mutual excitatory or inhibitory synaptic organizations in neuroscience BIB015 , time delays in sensor networks BIB030 , or transfer conductances in power networks  lead to a shifted coupling of the form sin(θ i − θ j − ϕ ij ) with ϕ ij ∈ [−π/2, π/2]. In these cases and also for other "skewed" or "symmetry-breaking" interactions among the oscillators, many of the presented analysis schemes either fail or lead to overly conservative results. Additionally, the inclusion of odd coupling functions possibly with higher-order harmonics can lead to qualitatively different behavior and scaling laws as discussed by   BIB011 . Finally, a topic of recent interest is mixed attractive and repulsive coupling BIB038 BIB045 BIB042 . Pulse coupling: Another interesting class of oscillator networks are systems of pulse-coupled oscillators which were introduced by Peskin (1975) and popularized in the seminal work by BIB006 . Pulsecoupled oscillators feature hybrid dynamics: impulsive coupling at discrete time instants and uncoupled continuous dynamics otherwise. This class of oscillator networks displays a very interesting phenomenology which is qualitatively different from diffusive and continuous coupling, see . For instance, the behavior of identical oscillators coupled in a complete graph strongly depends on the curvature of the uncoupled dynamics. As discussed in Subsection 2.4, weakly pulse-coupled oscillator models can be reduced to the canonical model (14) through a phase reduction and averaging analysis. For certain weakly pulse-coupled oscillators the coupling functions h ij (·) turn out to be monotone and discontinuous, and they result in finite-time convergent dynamics BIB007 . Most of the results and analysis methods known for continuously-coupled oscillators still need to be extended to pulse-coupled oscillators, especially in the case of dissimilar natural frequencies. Transient dynamics: For dissimilar oscillators, most results presented in this paper pertain to existence and local stability of synchronous solutions, with the exception of Theorems 6.6 and 7.1. Even for the Kuramoto model (3), many problems pertaining to the transient dynamics still need to be fully resolved. For instance, most known estimates on the region of attraction of a synchronized solution are conservative, such as the semicircle estimates given in Theorems 5.2 and 6.6. We refer to  BIB022 for a set of interesting results and conjectures on the region of attraction. Of further interest is whether almost global frequency synchronization can be achieved for heterogeneous oscillator networks coupled in, e.g., acyclic graphs. As shown in Theorem 6.6, for complete graphs, the region of attraction of a synchronous solution always includes ∆ G (π/2) for any K > K critical . It is unclear if an analogous result holds for sparse graphs or if the region of attraction severely depends on the topology. When the Kuramoto dynamics (3) are subject to additive noise, they can be analyzed through Fokker-Planck equations similar to the continuum-limit model (18)-(19) or in the limit of small stochastic perturbations, see BIB027  . In this case, there are various interesting transitions between wells of the potential landscape and only few analytic investigations. Also the sub-synchronous regime for K < K critical is vastly unexplored, and partial synchronization or clustering (similar to the infinite-dimensional model) BIB028 , chimera states  BIB046 , or chaotic motion  BIB016 BIB032 can occur. Finally, the incremental stability results referenced in Subsection 4.1 appear to be a promising direction that still needs to be fully explored. Higher-order phase oscillator networks: For the mechanical analog in Fig. 1 and the previously listed applications BIB003 BIB008  BIB012 BIB010 BIB013  BIB014 BIB017 BIB023  BIB035 BIB043 BIB039 the coupled oscillator dynamics are not exactly given by the first-order phase model (1). In many cases, the dynamics are of second order as in (9). The analysis of second-order oscillator networks has also received a lot of attention, see  BIB036 BIB040 ) for a literature overview. Among others, the contraction Lyapunov function (32) can be extended to second-order oscillators BIB040 , the continuum-limit analysis can be extended  , and the local stability properties are preserved when going from first to second order BIB036 . Of course, the transient dynamics of second-order oscillator networks have their own characteristics, especially for large inertia and small damping  . Thus, many of the presented results still need to be extended to secondorder oscillator networks. State space and aperiodic oscillator networks: In other instances of oscillator networks, there is no readilyavailable phase variable to describe the periodic limitcycle dynamics of the coupled system, and the phase oscillator model is valid only after a phase reduction and averaging analysis. Since features of the original model may be poorly preserved in the phase model (4), a direct analysis of the state space model is preferred. In the case of linear or passive systems, state or output synchronization are well understood, see for example, BIB029  BIB047  . The analysis of synchronization problems in general periodic and heterogeneous state space oscillator networks remains a challenging and important problem. Additionally, synchronization phenomena can also occur among chaotic and aperiodic oscillators BIB009 , whose analysis is thus far mainly restricted to numerical linearization via the Master Stability Function approach  BIB024 BIB031 BIB048 . It is yet unclear which analysis methods carry over from phase oscillator networks to state space or chaotic oscillator networks. Sparse and heterogeneous networks: Despite the vast scientific interest the quest for sharp, concise, and closed-form synchronization conditions for arbitrary connected graphs has been so far in vain. As suggested by our discussion in Section 7, the proper metric for the analysis of synchronization problem appears to be the incremental ∞-norm. In the authors' opinion, an analysis with the incremental ∞-norm will most likely deliver the sharpest possible conditions. We believe that the norm and cycle constraints developed in are a fruitful approach towards a more complete understanding of sparse topologies. Likewise, for the transient analysis, the ∞ -type contraction Lyapunov function (32) is a powerful analysis concepts for complete graphs and still needs to be extended to arbitrary connected graphs. Regarding the potential and equilibrium landscape, a few interesting and still unresolved conjectures can be found in BIB001 ; BIB004 ; BIB005 ; BIB037 BIB002 and pertain to the number of (stable) equilibria and topological properties of the equilibrium set. Finally, the complex networks, nonlinear dynamics, and statistical physics communities found various interesting scaling laws in their statistical and numerical analyses of random graph models, such as conditions depending on the spectral ratio λ 2 /λ n of the Laplacian eigenvalues, interesting results for correlations between the degree deg i and the natural frequency ω i , and degree-dependent synchronization conditions BIB025  BIB018 BIB024 BIB026 BIB031 BIB033 BIB044 . It is unclear which of these results and findings are amenable to an analytic and quantitative investigation. We sincerely hope that this survey article stimulates further exciting research on synchronization in coupled oscillators, both on the theoretical side as well as in the countless applications.