Synchronization in networks of coupled systems

In this section we study synchronization in a network of coupled systems. A simple generalization of Theorem 3 in the previous section is the following:

Corollary 1

Consider n coupled dynamical systems coupled in the form:

dx₁/dt = f(x₁,x₁,x₂,...,x_n)

dx₂/dt = f(x₂,x₁,x₂,...,x_n)

.

.

.

dx_n/dt = f(x_n,x₁,x₂,...,x_n)

This network of systems synchronizes if dz/dt = f(z,σ₁,σ₂,...,σ_n) is uniform asymptotically stable and i-uniformly with respect to σ_i(t).

However, Corollary 1 does not take into account the way the n systems are connected to each other. Next we study the influence of the topology of the network that is represented mathematically as a graph or hypergraph. In particular, we will show that algebraic properties of the graph provide information on the propensity of the network to synchronize. In the sequel we assume that G(t) (and G) is a zero row sums matrix for all t.

Theorem 6 [Wu and Chua 1995, Wu 2003]

Consider n coupled dynamical systems coupled in the form:

Let P(t) be a time-varying matrix and V be a symmetric positive definite matrix such that (y-z)^TV(f(y,t)+P(t)y-f(z,t)-P(t)z) ≤- α||y-z||² for some α > 0. This condition, introduced in [Wu and Chua 1995] to derive synchronization conditions for networks of coupled systems, has since been referred to as the QUAD condition. If there exists an irreducible symmetric zero row sums matrix with nonpositive off-diagonal elements U such that

for all t then the network synchronizes.

Let us concentrate on the equation

Assume that P(t) =C(t) and VC(t) is negative semidefinite. This equation is then reduced to ensuring that U(G(t)-I) is positive semidefinite. The matrix U in this discussion is always assumed to be irreducible symmetric, has zero sums and nonpositive off-diagonal elements. Let us study the conditions for G(t) and U such that U(G(t)-I) is positive semidefinite. We have the following result:

Theorem 7 [Wu 2006a]

Let U = L_k be the Laplacian matrix of the complete graph, i.e. L_k(i,i) = n-1 and L_k(i,j) = -1 for i≠j. If min_{x≠0,∑xi = 0,} x^TGx/x^Tx ≥ 1, then U(G-I) is positive semidefinite.

A consequence of Theorem 7 is the following synchronization result which relates the ability to synchronize to an algebraic quantity derived from the topology of the network.

Theorem 8 [Wu 2005a]

Consider n coupled dynamical systems coupled in the form:

Let C(t) be a time-varying matrix and V be a symmetric positive definite matrix such that (y-z)^TV(f(y,t)+C(t)y-f(z,t)-C(t)z) ≤- α||y-z||² for some α > 0. The network of coupled dynamical systems synchronizes if VC(t) is symmetric negative semidefinite and min_{x≠0,∑xi = 0,} x^TG(t)x/x^Tx ≥ 1 for all t.

Definition 6 [Fiedler 1973]

For a Laplacian matrix L of an undirected graph, the algebraic connectivity is defined as the second smallest eigenvalue of L (not counting multiplicity).

By an extension of the Rayleigh-Ritz theorem [Horn and Johnson 1985] and the fact that the vector of all 1's is in the kernel of L, the algebraic connectivity is equal to min_{x≠0,∑xi=0} x^TLx/x^Tx. Thus in the case that the matrix G is a Laplacian matrix of a undirected graph, the quantity in Theorem 7 is the algebraic connectivity of the underlying graph. This motivates the following extension of algebraic connectivity to directed graphs:

Definition 7 [Wu 2005a]

If G is the Laplacian matrix a directed graph, then the algebraic connectivity of the graph is defined as min_{x≠0,∑xi=0} x^TGx/x^Tx.

When G(t) is constant, i.e. does not depend on t, then Theorem 8 can be strengthened as follows:

Theorem 9 [Wu 2005b]

Consider n coupled dynamical systems coupled in the form:

Let C(t) be a time-varying matrix and V be a symmetric positive definite matrix such that (y-z)^TV(f(y,t)+C(t)y-f(z,t)-C(t)z) ≤- α||y-z||² for some α > 0. Let w be the left eigenvector corresponding to the zero eigenvalue of G and W be the diagonal matrix with the entries of w on the diagonal. The network of coupled dynamical systems synchronizes if VC(t) is symmetric negative semidefinite and min_{x≠0,∑xi = 0,} x^TWGx/x^Tx ≥ 1 for all t.

Thus Theorems 8 and 9 show that the quantities min_{x≠0,∑xi = 0,} x^TG(t)x/x^Tx and min_{x≠0,∑xi = 0,} x^TWGx/x^Tx are important in determining synchronization properties of the network. The following quantity is also important in determining synchronization:

Definition 8 [Wu 2006a]

μ(G) is defined as the supremum of the set of real numbers μ such that U(G-μI) is positive semidefinite for some matrix U that is symmetric, irreducible, have zero row sums and nonpositive offdiagonal elements.

Lemma 1 [Wu 2005b]

If G is the Laplacian matrix of a strongly connected digraph, then 0 < min_{x≠0,∑xi = 0,} x^TWGx/x^Tx ≤ min_{x≠0,∑xi = 0,} x^TWGx/x^T(W-ww^T/∑w_i)x ≤ μ(G).

Theorem 10 [Wu 2006a]

Consider n coupled dynamical systems coupled in the form:

Let VC(t) be symmetric negative semidefinite for all t and V be a symmetric positive definite matrix such that (y-z)^TV(f(y,t)+μ(G)C(t)y-f(z,t)-μ(G)C(t)z) ≤- α||y-z||² for some α > 0. Then the network of coupled dynamical systems synchronizes.

One way to paraphrase Theorem 8 is that the higher the algebraic connectivity of the underlying network is, the easier it is to synchronize the network. This makes intuitive sense since the algebraic connectivity is a measure of the connectedness of the network, and a more connected graph should be more amenable to synchronization since there is more influence among nodes. The following result shows that the existence of a spanning directed tree in the reversal of the underlying network is sufficient to synchronize the network when the coupling is strong enough.

Theorem 11 [Wu 2005c]

Consider n coupled dynamical systems coupled of the form:

Let VC(t) be symmetric negative semidefinite for all t and V be a symmetric positive definite matrix such that (y-z)^TV(f(y,t)+C(t)y-f(z,t)-C(t)z) ≤- α||y-z||² for some α > 0. Then the network of coupled dynamical systems synchronizes for a larger enough κ > 0 if G is the Laplacian matrix of a weighted directed graph whose reversal contains a spanning directed tree.

When the coupling topology is a directed graph that is connected but not strongly connected, synchronization can be analyzed in stages in the following way [Wu and Chua 1995]:

First decompose the directed graph into maximal strongly connected components. The components can be considered as vertices of an acyclic directed graph called condensation directed graph (CDG) [Brualdi and Ryser, 1991]. We look at the strongly connected components corresponding to vertices of indegree 0 in the CDG and call them leading strong connected components (LSCC). If there are more than one such LSCC, then it will not be possible to synchronize the entire network, especially if the individual systems are chaotic. Otherwise we restrict ourselves to the systems in the LSCC and see if the systems synchronize. If they do, we collapse the LSCC into a single system and continue analyzing the reduced network, each time collapsing the synchronized subset of systems into a single system.

We see that the algebraic connectivity and the Laplacian matrix of a graph can provide much information on the synchronization properties of a network of coupled systems. Some properties of the algebraic connectivity and the Laplacian matrix of directed graphs and their relationship to graph theoretical properties are enumerated in the next section: properties of Laplacian matrix and algebraic connectivity of directed graphs.

References

[Brualdi and Ryser, 1991] R. Brualdi and H. Ryser, Combinatorial Matrix Theory, Cambridge University Press, 1991.

[Fiedler 1973] M. Fiedler. Algebraic connectivity of Graphs, Czechoslovak Mathematical Journal. 23(2):298-305, 1973.

[Horn and Johnson 1985] R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, 1985.

[Wu and Chua 1995] C. W. Wu and L. O. Chua. Synchronization in an array of linearly coupled dynamical systems. IEEE Transactions on Circuits and Systems, Part I, 42(8):430-447, 1995.

[Wu 2003] C. W. Wu. Perturbation of coupling matrices and its effect on the synchronizability in arrays of coupled chaotic systems. Physics Letters A, 319(5-6):495-503, 2003.

[Wu 2005a] C. W. Wu. Algebraic connectivity of directed graphs. Linear and Multilinear Algebra. 53(3):203-223, 2005.

[Wu 2005b] C. W. Wu. On Rayleigh–Ritz ratios of a generalized Laplacian matrix of directed graphs. Linear Algebra and Its Applications. 402:207-227, 2005.

[Wu 2005c] C. W. Wu. Synchronization in networks of nonlinear dynamical systems coupled via a directed graph. Nonlinearity. 18:1057-1064, 2005.

[Wu 2006a] C. W. Wu. On a matrix inequality and its application to the synchronization in coupled chaotic systems. Complex Computing-Networks: Brain-like and Wave-oriented Electrodynamic Algorithms, Springer Proceedings in Physics. 104:279-288, 2006.

[Wu 2006b] C. W. Wu. Identical synchronization in networks of coupled nonlinear circuits and systems, IBM Research Report RC23848, 2006.

Copyright 2006-2009 by Chai Wah Wu.