Synchronization in complex networks of phase oscillators: A survey <s> Towards an Exact Synchronization Condition <s> 1. Introduction to algebraic graph theory Part I. Linear Algebra in Graphic Thoery: 2. The spectrum of a graph 3. Regular graphs and line graphs 4. Cycles and cuts 5. Spanning trees and associated structures 6. The tree-number 7. Determinant expansions 8. Vertex-partitions and the spectrum Part II. Colouring Problems: 9. The chromatic polynomial 10. Subgraph expansions 11. The multiplicative expansion 12. The induced subgraph expansion 13. The Tutte polynomial 14. Chromatic polynomials and spanning trees Part III. Symmetry and Regularity: 15. Automorphisms of graphs 16. Vertex-transitive graphs 17. Symmetric graphs 18. Symmetric graphs of degree three 19. The covering graph construction 20. Distance-transitive graphs 21. Feasibility of intersection arrays 22. Imprimitivity 23. Minimal regular graphs with given girth References Index. <s> BIB001 </s> Synchronization in complex networks of phase oscillators: A survey <s> Towards an Exact Synchronization Condition <s> This paper encompasses a motley collection of ideas from several ::: areas of mathematics, including, in no particular order, random walks, the Picard ::: group, exchange rate networks, chip-firing games, cohomology, and the conductance ::: of an electrical network. The linking threads are the discrete Laplacian on a graph and the solution of the associated Dirichlet problem . Thirty years ago, this subject was dismissed by many as a trivial specialisation of cohomology theory, but ::: it has now been shown to have hidden depths. Plumbing these depths leads to new theoretical ::: advances, many of which throw light on the diverse applications of the ::: theory. <s> BIB002 </s> Synchronization in complex networks of phase oscillators: A survey <s> Towards an Exact Synchronization Condition <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> BIB003 </s> Synchronization in complex networks of phase oscillators: A survey <s> Towards an Exact Synchronization Condition <s> A central question in the analysis and operation of power networks is feasibility of the power flow equations subject to security constraints. For large-scale networks the solution of the nonlinear AC power flow equations can be constructed only numerically or approximated through the linear DC power flow. The latter serves as well-used approximation to obtain the phase angle differences near an acceptable operating point, but the accuracy of the DC approximation drops in a stressed grid. Here, we propose a modified DC approximation that applies to lossless networks with parametric uncertainties and with voltage magnitudes bounded within security constraints. We show that the phase angle differences can be well approximated by the solution to a set of linear and interval-valued equations reminiscent of the DC power flow equations. Our proposed approximation improves upon the standard DC approximation, is computationally attractive and provably exact for a broad range of network topologies and parameters. We validate the accuracy of our approximation through standard power network test cases with randomized power demand at the loads. <s> BIB004
An analysis of the fixed-point equations (51) using 2-norm bounding of L(θ) † ω E,2 results in the condition ω E,2 /λ 2 (L) < 1 in Theorem 7.2. As discussed above, an ∞-norm analysis of equations (51) and the term L(θ) † ω E,∞ should yield a less conservative condition, possibly of the form L † ω E,∞ < 1. Indeed, this condition can be derived for particular networks. By formally replacing each term sin(θ i − θ j ) in the fixed-point equations (50) by an auxiliary scalar variable ψ ij we arrive at where ψ ∈ R |E| is a vector with elements ψ ij . We refer to equations (53) as the auxiliary-fixed point equation. It can be easily verified that every solution of the auxiliary fixed-point equations (53) is of the form where the homogeneous solution ψ hom ∈ R |E| satisfies Aψ hom ∈ Ker (B). Note that the orthogonal vector spaces Ker (B) and Ker (B) ⊥ = Im (B T ) are spanned by vectors associated to cycles and cutsets in the graph, see BIB001 BIB002 . For x, y ∈ R n , we say x = y mod 2π if, for each i ∈ {1, . . . , n}, there exists an integer k i such that x i = y i + 2πk i . We now arrive at the following characterization of the fixed points , Theorem 1). If the equivalent statements (i) and (ii) are true, then we have is a locally exponentially stable synchronization manifold. By Lemma 7.3, the cycle space Ker (B) of the graph serves as a degree of freedom to find a minimum ∞-norm solution ψ * ∈ R |E| to equations (53), which yields an optimal necessary synchronization condition. Corollary 7.4 (Optimal necessary synchronization condition) Consider the coupled oscillator model (1) with a connected graph G(V, E, A) and ω ∈ 1 ⊥ n . Compute ψ * ∈ R |E| as solution to the optimization problem Let γ ∈ [0, π/2[. There exists a locally exponentially sta- If the graph is acyclic, then there are no cycle constraints, and the norm constraint in Lemma 7.3 reduces to sin(γ) ≥ ψ ∞ = L † ω E,∞ . We arrive at the following corollary , Theorem 2). Corollary 7.5 (Practical phase synchronization in acyclic graphs) Consider the coupled oscillator model (1) with a connected and acyclic graph G(V, E, A) and ω ∈ 1 ⊥ n . There exists a locally exponentially stable equilibrium manifold Condition (57) is equivalent to the cutset condition  , Lemma 1). BIB003 also proved that condition (57) is sufficient and tight for various extremal graph topologies and parameters such as complete and uniformly weighted graphs (in this case (57) is equivalent to (46)), small cycles of length strictly less than five, cutset-inducing natural frequencies ω = Lω bip , in the limit L † ω E,∞ 0, and 1-connected combinations of these graphs. Moreover, by means of a statistical analysis, it can be shown that condition (57) is extremely accurate for a broad set of random network topologies and weights as well as for standard power network test cases BIB004 . However, the authors also identified possibly thin sets of topologies and parameters for which condition (57) is not sufficiently tight. We conclude this section with a comparison of the synchronization conditions (27), (28), (49), (52), and (57). Let V ∈ R n×n be the matrix of orthonormal eigenvectors of L and let 0 = λ 1 < λ 2 ≤ · · · ≤ λ n be the corresponding eigenvalues. Then condition (57) reads as V diag 0, 1/λ 2 , . . . , 1/λ n · V T ω E,∞ < 1 . A sufficient condition for inequality (58) is λ 2 > ω E,∞ , which strictly improves upon the algebraic connectivity conditions (49) and (52). Likewise, a necessary condition for (58) is 2 · max i∈V deg i ≥ λ n ≥ ω E,∞ , resembling the degree-dependent conditions (27) and (28). When compared to (58), this sufficient condition and this necessary condition feature only one of n − 1 nonzero Laplacian eigenvalues and are overly conservative. We conclude that condition (57) strongly improves upon the conditions (27), (28), (49), and (52), but a complete analytic characterization of its applicability is still open.