Synchronization in complex networks of phase oscillators: A survey <s> Preliminaries and Notation: <s> This paper provides a theoretical framework for analysis of consensus algorithms for multi-agent networked systems with an emphasis on the role of directed information flow, robustness to changes in network topology due to link/node failures, time-delays, and performance guarantees. An overview of basic concepts of information consensus in networks and methods of convergence and performance analysis for the algorithms are provided. Our analysis frame- work is based on tools from matrix theory, algebraic graph theory, and control theory. We discuss the connections between consensus problems in networked dynamic systems and diverse applications including synchronization of coupled oscillators, flocking, formation control, fast consensus in small- world networks, Markov processes and gossip-based algo- rithms, load balancing in networks, rendezvous in space, distributed sensor fusion in sensor networks, and belief propagation. We establish direct connections between spectral and structural properties of complex networks and the speed of information diffusion of consensus algorithms. A brief introduction is provided on networked systems with nonlocal information flow that are considerably faster than distributed systems with lattice-type nearest neighbor interactions. Simu- lation results are presented that demonstrate the role of small- world effects on the speed of consensus algorithms and cooperative control of multivehicle formations. <s> BIB001 </s> Synchronization in complex networks of phase oscillators: A survey <s> Preliminaries and Notation: <s> Consider a weighted and undirected graph, possibly with self-loops, and its corresponding Laplacian matrix, possibly augmented with additional diagonal elements corresponding to the self-loops. The Kron reduction of this graph is again a graph whose Laplacian matrix is obtained by the Schur complement of the original Laplacian matrix with respect to a subset of nodes. The Kron reduction process is ubiquitous in classic circuit theory and in related disciplines such as electrical impedance tomography, smart grid monitoring, transient stability assessment in power networks, or analysis and simulation of induction motors and power electronics. More general applications of Kron reduction occur in sparse matrix algorithms, multi-grid solvers, finite--element analysis, and Markov chains. The Schur complement of a Laplacian matrix and related concepts have also been studied under different names and as purely theoretic problems in the literature on linear algebra. In this paper we propose a general graph-theoretic framework for Kron reduction that leads to novel and deep insights both on the mathematical and the physical side. We show the applicability of our framework to various practical problem setups arising in engineering applications and computation. Furthermore, we provide a comprehensive and detailed graph-theoretic analysis of the Kron reduction process encompassing topological, algebraic, spectral, resistive, and sensitivity analyses. Throughout our theoretic elaborations we especially emphasize the practical applicability of our results. <s> BIB002
The remainder of this section recalls some standard notation and preliminaries from algebraic graph theory. Vectors and functions: Let 1 n and 0 n be the ndimensional vectors of unit and zero entries, and let 1 ⊥ n be the orthogonal complement of 1 n in R n , that is, 1 ⊥ n {x ∈ R n | x ⊥ 1 n }. Accordingly, let 1 n×n denote the (n × n)-dimensional matrix with unit entries. Given an n-tuple (x 1 , . . . , x n ), let x ∈ R n be the associated vector with maximum and minimum elements x max and x min . Given an ordered index set I of cardinality |I| and a one-dimensional array {x i } i∈I , let diag({x i } i∈I ) ∈ R |I|×|I| be the associated diagonal matrix. For x ∈ R n define sin(x) = (sin(x 1 ), . . . , sin(x n )) and for x ∈ [−1, 1] n define arcsin(x) = (arcsin(x 1 ), . . . , arcsin(x n )). Finally, define the continuous function sinc : R → R by sinc(x) = sin(x)/x, where sinc(0) = 1. Geometry on the n-torus: The set S 1 denotes the unit circle, an angle is a point θ ∈ S 1 , and an arc is a connected subset of S 1 . The n-torus is the Cartesian product The geodesic distance between two angles θ 1 , θ 2 is the minimum of the counter-clockwise and the clockwise arc lengths connecting θ 1 and θ 2 . With slight abuse of notation, let |θ 1 − θ 2 | denote the geodesic distance between the two angles θ 1 , θ 2 ∈ S 1 . Algebraic graph theory: Let G(V, E, A) be an undirected, connected, and weighted graph without selfloops. Let A ∈ R n×n be its symmetric nonnegative adjacency matrix with zero diagonal elements a ii = 0. For each node i ∈ {1, . . . , n}, define the node degree If a unique number ∈ {1, . . . , |E|} and an arbitrary direction are assigned to each edge {i, j} ∈ E, the (oriented) incidence matrix B ∈ R n×|E| is defined component-wise by B k = 1 if node k is the sink node of edge and by B k = −1 if node k is the source node of edge ; all other elements are zero. For x ∈ R n , the vector B T x ∈ R |E| has entries of the form x i − x j corresponding to the oriented edge from j to i, that is, B T maps node variables x i , x j to incremental edge variables T . If the graph is connected, then Ker (B T ) = Ker (L) = span(1 n ), all n − 1 non-zero eigenvalues of L are strictly positive, and the second-smallest eigenvalue λ 2 (L) is called the algebraic connectivity and is a spectral connectivity measure. Since the Laplacian L is singular, we will use its MoorePenrose pseudo inverse L † . If V ∈ R n×n is an orthonormal matrix of eigenvectors of L, the singular value decomposition of L is L = V diag(0, {λ i } i∈{2,...,n} )V T , and We also define the effective resistance between any two nodes i and j by We refer to BIB002 for further information and identities on Laplacian inverses and on the resistance distance. Laplacian flow: A well-studied cost function associated with a graph is the Laplacian potential 1/2·x The associated gradient flowẋ = −Lx is known as the Laplacian flow or consensus protocol, and it reads in components aṡ The consensus protocol is well-studied in the control literature BIB001     , and it can be regarded as linear counterpart to the coupled oscillator model (1) with dynamics evolving on the Euclidean state space R n and without drift terms. Some of the analysis tools and insights developed for the consensus protocol extend to the coupled oscillator model (1).