Synchronization in dynamical systems coupled via multiple directed networks

There has been much research activity in studying the synchronization and consensus behavior in networks of coupled dynamical systems [1, 2, 3, 4, 5, 6, 7, 8, 9]. The coupled systems model various types of networks both man-made and naturally occurring, such as social networks, transportation networks, genetic networks and neural networks. In many cases the individual systems or agents are connected via multiple networks. For instance, automobiles are connected via a transportation network, but they can also connected via cell phones (or other vehicle-to-vehicle technologies such as DSRC [10]) in a communication network. Similarly, people can be connected via multiple social networks such as Facebook and LinkedIn. The Erdős-Bacon number is the sum of the distance in the actor and in the mathematical collaboration network.

Prior work on systems coupled via multiple networks include [11] where synchronization is studied in continuous-time dynamical systems coupled via $2$ networks with one of the networks coupling delayed state variables and conditions were provided under which the system is synchronizing. Refs. [12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23] also studied synchronization in continuous-time dynamical systems coupled via multiple networks where a local stability approach numerically computing Lyapunov exponents or a mean field approximation is used. In some of these works, networks are studied whose Laplacian matrices are simultaneously diagonalizable. This paper differs from prior work in that 1) we use the Lyapunov function approach which provides a guaranteed synchronization criteria, 2) consider simultaneously triangularizable matrices which is a superset of the simultaneously diagonalizable matrices, 3) consider directed networks 4) and consider extensions to discrete-time systems.

In this paper we study synchronization and consensus in dynamical systems coupled under multiple networks and study how these multiple networks can work together to reach synchronization even though each individual network might not be able to effect synchronization. We consider the case of continuous time systems in Section III. The case of discrete time systems will be studied in Section IV.

We define $e_{i}$ as the $i$-th unit vector and $E_{i}$ as the diagonal square matrix such that all entries are $0$ except that the $i$-th entry on the diagonal is $1$ and define $e$ as the vector of all $1$’s and $I$ as the identity matrix. For a Hermitian matrix, the eigenvalues are listed as $\lambda_{1}\leq\lambda_{2}\cdots\leq\lambda_{n}$. We use $A\succ 0$ and $A\succeq 0$ to denote that the matrix $A$ is positive definite and positive semidefinite respectively¹¹1For non-Hermitian matrices, we say $A$ is positive (semi)definite if $A+A^{H}$ is positive (semi)definite.. The following simple results generalize the results in [24] and in [25, Lemma 3.1] and prove to be useful when studying coupling via multiple networks:

Proof: The matrix $(P\otimes I)C(P^{-1}\otimes I)=\sum_{i}(J_{i}\otimes B_{i})$ is block upper triangular with diagonal blocks equal to $\sum_{i}\lambda_{ij}B_{i}$. Thus the eigenvalues are the same as the eigenvalues of $\sum_{i}\lambda_{ij}B_{i}$ for $1\leq j\leq n$.²²2Since all $G_{i}$ share the same set of unit length eigenvectors $v_{j}$, we denote $\lambda_{ij}$ as the eigenvalue of $B_{i}$ corresponding to the eigenvector $v_{j}$. This convention will used throughout. $\Box$

It is clear that if ${\cal M}$ satisfies the condition of Lemma II.1, so does ${\cal M}\cup\{\alpha I\}$ where $\alpha\in{\mathbb{C}}$.

Proof: The matrix $A$ is similar to an upper triangular matrix $J$ (e.g. the Jordan normal form). If $J$ is in upper triangular form, so is $J^{2}$ and it is clear from the spectral mapping theorem that if $J$ has eigenvalues $\lambda_{i}$, then $p(J)$ has eigenvalues $p(\lambda_{i})$. This implies that the set of matrices $\{p_{1}(A),p_{2}(A),\cdots,p_{n}(A)\}$ where $A$ is a fixed matrix and $p_{i}$ are polynomials can be transformed to an upper triangular form via the same matrix $P$ and the result follows from Lemma II.1. $\Box$

It is well known that the set of simultaneously triangularizable matrices corresponds to the set of commuting matrices [26]. Examples of commuting sets of matrices include the set of $n$ by $n$ circulant matrices. These matrices are diagonalizable with eigenvectors equal to the columns of the Discrete Fourier Transform matrix. As noted before, the identity matrix $I$ (and its scalar multiple) can always be added to such sets since the identity matrix commutes with any matrix.

In our study, $A_{i}$ will be Laplacian matrices of directed graphs³³3A Laplacian matrix of a directed graph is defined as $D-A$ where $D$ is the diagonal matrix of vertex outdegrees and $A$ is the adjacency matrix. and $A_{i}e=0$ for all $i$. This means that for all vector $v$, $e\otimes v$ is an eigenvector of $A_{i}\otimes B_{i}$ corresponding to eigenvalue $0$, i.e. the eigenvalue $0$ has multiplicity at least $m$.⁴⁴4Recall that $m$ is the order of the matrices $B_{i}$. If in addition the graph ${\mathcal{G}}_{i}$ corresponding to $A_{i}$ is connected, then $0$ is an eigenvalue of $A_{i}$ with multiplicity $1$. If $B_{i}$ is nonsingular, then $A_{i}\otimes B_{i}$ has a 0 eigenvalue of multiplicity $m$.

We ask: when does $\sum_{i}A_{i}\otimes B_{i}$ have a zero eigenvalue of multiplicity $m$? The answer to this question will be useful later on in our study of synchronization in network of systems coupled via multiple networks. The following results give some conditions under which this question can be answered.

Proof: The eigenvalues of $\sum_{i}A_{i}\otimes B$ are the eigenvalues of $\lambda_{i}B$ where $\lambda_{i}$ are the eigenvalues of $A$. $\Box$

For example, Fig. 1 shows two directed graphs with the same vertex set and edges labeled ‘A’ and ‘B’ resp. Under the canonical ordering of the nodes, the Laplacian matrices of these graphs are circulant and thus commuting. Even though each of the graph is not connected, the graph sum is a connected graph and between every pair of nodes there is a directed path between them using either ‘A’ or ‘B’ edges.

Note that the graph sum depends on the ordering of the vertices and is thus not invariant under graph isomorphism, i.e. we consider labeled graphs. If $A_{i}$ are the Laplacian matrices of graphs, then $\sum_{i}A_{i}$ is the Laplacian matrix of the graph sum of these graphs and $\sum_{i}A_{i}$ having a zero eigenvalue of multiplicity 1 is equivalent to the reversal⁵⁵5i.e. the directed graph obtained by reversing the orientation of all edges. of the graph sum containing a spanning directed tree [27]. Note that for directed graphs, the Laplacian matrix is not necessarily symmetric.

Proof: The Laplacian matrix of the graph sum is $\sum_{i}L_{i}$. By the simultaneously triangularizable property, its eigenvalues are $\sum_{i}\lambda_{ij}$ for each $j$. By [27], its Laplacian matrix has a $0$ eigenvalue of multiplicity $1$ and the conclusion follows. $\Box$

Proof: By Lemma II.1, the eigenvalues of $C$ are given by the eigenvalues $\sum_{i}\lambda_{ij}B_{i}$ for each $j$. By Lemma II.2 only for one $j$ is it true that $\lambda_{ij}=0$ for all $i$, in which case $\sum_{i}\lambda_{ij}B_{i}=0$ and we have $m$ zero eigenvalues. For all other $j$ there exists nonzero $\lambda_{ij}$’s. Since $\lambda_{ij}\geq 0$, this can be rescaled to a convex combination of $B_{i}$ which is nonsingular by hypothesis. $\Box$

Examples of nonsingular matrices $B_{i}$ for which convex combinations are nonsingular include diagonal positive definite matrices or strictly diagonally dominant matrices whose eigenvalues have positive real parts.

For the continuous-time case, consider the state equation:

where $x=(x_{1},\dots,x_{n})$ and $G_{k}(t)$ and $D_{k}(t)$ are square matrices for each $k$ and $t$. There are $n$ identical systems described by $\dot{x_{i}}=f(x_{i},t)$ and each $x_{i}$ is the $m$-dimensional state vector of the $i$-th system. The coupling matrices $G_{k}(t)$ have zero row sums and describe $r$ different coupling networks coupling these systems together, i.e. the $ij$-th entry of the matrix $G_{k}(t)$ is nonzero if there is a coupling from the $j$-th system to the $i$-th system via the $k$-th network. The matrix $D_{k}(t)$ describes the coupling between a pair of systems in the $k$-th network and is the same between any pair of systems in the $k$-th network. We are interested in the case where the $D_{k}$ are not all equal, as otherwise it reverts to the single network case with the network being the graph sum. We say the system is globally synchronizing if $\|x_{i}-x_{j}\|\rightarrow 0$ as $t\rightarrow\infty$ for all $i$,$j$ and all initial conditions. One important special case is when $D_{k}=E_{k}$, which corresponds to the case where the $k$-th network only couples the $k$-th component of the state vectors and the internetwork connections occur solely due to the dynamics of the individual systems.

The following result provides sufficient conditions under which the system in Eq. (1) is globally synchronizing. and follows directly from the synchronization theorems in [28, 29, 30].

We next look at various special cases of Theorem III.1.

Consider a network of coupled discrete-time systems with the following state equations:

Proof: First consider the case $V=I$, i.e., $f(x,p)$ is Lipschitz continuous in $x$ with Lipschitz constant $\sqrt{c}$. Let $W=I-\sum_{k}G_{k}\otimes D_{k}$. Since $G_{k}(t)$ is normal and simultaneously diagonalizable, $G_{k}(t)$ has an orthonormal set of eigenvectors $v_{i}$ with $e=v_{1}$. Denote $\cal A$ as the subspace of vectors of the form $e\otimes v$. Since $G_{k}e=0$ it follows that ${\cal A}$ is in the kernel of $G_{k}\otimes D_{k}$. Let us denote the subspace orthogonal to ${\cal A}$ by ${\cal B}$. A vector $x(p)$ is decomposed as $x(p)=y(p)+z(p)$ where $y(p)\in{\cal A}$ and $z(p)\in{\cal B}$. By hypothesis $\|F(x(p),p)-F(y(p),p)\|\leq c\|z(p)\|$. We can decompose $F(x(p),p)-F(y(p),p)$ as $a(p)+b(p)$ where $a(p)\in{\cal A}$ and $b(p)\in{\cal B}$. Note that $F(y(p),p)$ and $a(p)$ are in ${\cal A}$ and therefore $(G_{k}\otimes D_{k})F(y(p),p)=(G_{k}\otimes D_{k})a(p)=0$.

Since $a(p)\bot b(p)$, $\|b(p)\|\leq\|F(x(p),p)-F(y(p),p)\|\leq c\|z(p)\|$. Since $b(p)\in{\cal B}$, it is of the form $b(p)=\sum_{i>1,j}\alpha_{i}v_{i}\otimes f_{j}(p)$.

By hypothesis this implies that

Let $w(p)$ be the orthogonal projection of $u(p)$ onto ${\cal B}$. Since $a_{k}(p)+F_{k}(y(p),p)$ is in ${\cal A}$, $z(p+1)$ is the orthogonal projection of $Wb(p)+u(p)$ onto ${\cal B}$ and thus $\|z(p+1)\|\leq\|Wb(p)\|+\|w(p)\|$. The above shows that there exists $\beta<1$ such that $\|Wb(p)\|\leq\beta\|z(p)\|$. Thus $\|z(p+1)\|\leq\beta\|z(p)\|+\|w(p)\|$. Note that $\sum_{k}(G_{k}\otimes D_{k})u(p)\rightarrow 0$ as $p\rightarrow\infty$ and thus $w(p)\rightarrow 0$ as $p\rightarrow\infty$. This implies that $z(p)\rightarrow 0$ as $p\rightarrow\infty$ and $x(p)$ approaches the synchronization manifold ${\cal A}$.

For general $V$, let $C^{T}C$ be the decomposition of $V$. Applying the state transformation $\tilde{x}=(I\otimes C)x$, we get $\tilde{x}(p+1)=\sum_{k}(I-G_{k}\otimes CD_{k}C^{-1})\left(\begin{array}[]{c}\tilde{f}_{k}(\tilde{x}_{1}(p),p)\\ \vdots\\ \tilde{f}_{k}(\tilde{x}_{n}(p),p)\end{array}\right)+\tilde{u}(p)$ where $\tilde{f}(\tilde{x}_{i},p)=Cf(C^{-1}\tilde{x}_{i},p)$. We can then apply the result from the $V=I$ case and the conclusion follows. $\Box$

Theorem IV.1 implies that if $G_{k}=\xi L_{k}$, $L_{k}$ are commuting normal Laplacian matrices with the graph sum’s reversal containing a spanning directed tree and $\xi$ is small enough, then the discrete system synchronizes. If $V=I$ and $D_{k}(p)$ are also normal commuting matrices, then Eq. (4) can be simplified to: $\left|1-\sum_{k}\lambda_{ki}\mu_{kj}\right|\leq\frac{1}{\sqrt{c}}$ for all $\lambda_{ki}\in S_{k}$ where $\mu_{kj}$ are the eigenvalues of $D_{k}$.

We study coupled dynamical systems coupled via multiple directed networks and provide criteria under which they synchronize for both continuous-time systems and discrete-time systems. In general, under suitable conditions, two conclusions can be drawn from these synchronization criteria. First, if the coupling between individual systems (as expressed by $D_{k}$) are strong enough, then the graph sum of all the networks jointly containing a spanning directed tree is sufficient to synchronize the network, even though a single network may not be connected. This is an intuitive conclusion as it implies that there is a node that influences every other node via a set of edges where each edge in the set belongs to at least one of the networks. Secondly, even if the coupling of a single network $D_{k}$ is not sufficient to synchronize the systems, but the sum $\sum_{k}D_{k}$ does, then the synchronization can still occur with multiple networks if each of the network is well connected, for instance, if they are all strongly connected and balanced.