Matryoshka and disjoint cluster synchronization of networks

Amirhossein Nazerian; Shirin Panahi; Ian Leifer; David Phillips; Hernán A. Makse; Francesco Sorrentino

doi:10.1063/5.0076412

Chaos. 2022 Apr; 32(4): 041101.

Published online 2022 Apr 4. doi: 10.1063/5.0076412

PMCID: PMC8983070

PMID: 35489844

Matryoshka and disjoint cluster synchronization of networks

Amirhossein Nazerian,¹ Shirin Panahi,¹ Ian Leifer,² David Phillips,³ Hernán A. Makse,² and Francesco Sorrentino^1,^a)

Author information Article notes Copyright and License information PMC Disclaimer

Associated Data

Supplementary Materials: The supplementary material includes further clarifications on the stability analysis of the synchronous solution for the cases of complete synchronization and cluster synchronization, an alternative formulation of the equations describing the network dynamics corresponding to the case $δ < 0$ , a discussion about the connection between the case of complete synchronization and cluster synchronization, additional information about intertwined clusters, and the canonical transformation that decouples the parallel perturbations from the transverse perturbations, an alternative formulation for the synchronizability of a network, and an analysis of the synchronizability of several real networks as a function of the parameter $δ$ .

Data Availability Statement: The data that support the findings of this study are available within the article.

Abstract

The main motivation for this paper is to characterize network synchronizability for the case of cluster synchronization (CS), in an analogous fashion to Barahona and Pecora [Phys. Rev. Lett. 89, 054101 (2002)] for the case of complete synchronization. We find this problem to be substantially more complex than the original one. We distinguish between the two cases of networks with intertwined clusters and no intertwined clusters and between the two cases that the master stability function is negative either in a bounded range or in an unbounded range of its argument. Our proposed definition of cluster synchronizability is based on the synchronizability of each individual cluster within a network. We then attempt to generalize this definition to the entire network. For CS, the synchronous solution for each cluster may be stable, independent of the stability of the other clusters, which results in possibly different ranges in which each cluster synchronizes (isolated CS). For each pair of clusters, we distinguish between three different cases: Matryoshka cluster synchronization (when the range of the stability of the synchronous solution for one cluster is included in that of the other cluster), partially disjoint cluster synchronization (when the ranges of stability of the synchronous solutions partially overlap), and complete disjoint cluster synchronization (when the ranges of stability of the synchronous solutions do not overlap).

Previous work in the area of cluster synchronization of networks has shown that it is possible for different clusters of nodes to synchronize in different ranges of the coupling strength. We define the synchronizability of each cluster as the range of the coupling strength in which the synchronous solution for that cluster is stable. We distinguish between three different types of cluster synchronization, which we call Matryoshka, partially disjoint, and complete disjoint, and discuss their role in affecting cluster synchronizability for both cases of synthetic and real-world networks.

I. INTRODUCTION

Cluster synchronization (CS) in networks of coupled oscillators has been the subject of vast research efforts (see, e.g., Refs. ⁸^,¹³^,¹⁷^,²³^,³¹^,³⁴^,³⁸^,⁴¹^,⁴⁵, and ⁴⁸). CS often occurs in networks with connectivity described by an adjacency matrix, but it can also occur in networks with connectivity described by a Laplacian matrix, with sums of the entries in all the rows equal to zero. Kaneko²² studied the emergence of CS in networks of globally coupled chaotic maps and described the emergence of multi-stability of CS patterns in such networks. Belykh et al.^4,6,7 studied CS in 1D, 2D, and 3D lattices where the network topology is described by a Laplacian matrix. These papers also showed that the synchronization manifold corresponding to a given pattern of CS can be embedded in the synchronization manifold corresponding to another pattern of CS, which is consistent with the emergence of different patterns of CS in these networks.

Recent works have discussed the role of clusters of nodes in both undirected³⁰ and directed^25,29 biological networks.¹⁸ Here, we focus on the emergence of cluster synchronization in networks of coupled dynamical systems. There is a known definition of network synchronizability,^3,19 which specifically applies to the case of complete synchronization and describes how “synchronizable” a given network is, regardless of the particular dynamics of the network nodes and the specific choice of the node-to-node interaction. The synchronizability measures the range of the coupling strength (hereafter, $σ$ ) in which the synchronous solution is stable. Despite the broad interest in CS and its relevance to biological networks, no definition of cluster synchronizability, which is related to the stability of CS, has been given in the literature. In this paper, we will provide a definition of cluster synchronizability that applies to each individual cluster within a network. We will also discuss why defining a single index of cluster synchronizability for a network is difficult.

To motivate the need for introducing a definition of cluster synchronizability, consider the following questions: (1) What is the condition for a given set of nodes to synchronize in a cluster, based on the network topology? (2) How does changing a relevant parameter affect the synchronization of clusters? In what follows, we will see that the case of CS is considerably more complex than the case of complete synchronization and a variety of alternative scenarios may occur, which we call Matryoshka synchronization, partially disjoint synchronization, and completely disjoint synchronization; yet, under appropriate assumptions, we will derive a definition of cluster synchronizability and use it to compare several networks.

In Sec. II, we briefly review the case of complete synchronization for networks described by the Laplacian matrix, and in Sec. III, we study the case of cluster synchronization for networks described by the adjacency matrix. In both cases, we focus on the stability of the synchronous solution corresponding to the network minimum balanced coloring,⁵ i.e., the solution for which the fewest sets of nodes for that network achieve synchronization. In Sec. IV, we define the synchronizability of each cluster. We pay separate attention to the cases of networks with no intertwined clusters and with intertwined clusters, and at the end of the section, we investigate the case of real network topologies.

II. THE CASE OF COMPLETE SYNCHRONIZATION

We briefly review here the definition of synchronizability for the case of complete synchronization. Consider a network of coupled dynamical systems that evolve based on the following set of equations:

{\dot{x x}}_{i} (t) = F F ({x x}_{i} (t)) + σ \sum_{j} L_{i j} H H (x x_{j} (t))

(1)

for $i = 1, \dots, N$ , where ${x x}_{i} \in R^{m}$ is the state of node $i$ , $F F : R^{m} \to R^{m}$ describes the dynamics of each individual uncoupled system, the function $H H : R^{m} \to R^{m}$ describes how two systems interact with one another and $σ > 0$ is a positive scalar parameter that measures the strength of the coupling. The symmetric Laplacian matrix $L = {L_{i j}}$ is defined as $L = A - D$ where the symmetric adjacency matrix $A = {A_{i j}}$ describes the network connectivity, i.e., $A_{i j} = A_{j i} \neq 0$ ( $A_{i j} = A_{j i} = 0$ ) if node $j$ is (not) connected to node $i$ and vice versa, and the diagonal matrix $D$ has diagonal entries that are equal to the degree of each node, $D_{i i} = \sum_{j} A_{i j}$ . The Laplacian matrix is negative semidefinite (see Sec. I in the supplementary material). Also, since $L$ has sum over its rows equaling zero, the eigenvalues of $L$ are $0 = λ_{1} \geq λ_{2} \geq \dots \geq λ_{N}$ .^11,16 The Laplacian eigenvalue $λ_{2}$ is known as the algebraic connectivity and is strictly negative for connected networks.^16,26,28

Based on the functions $F F$ and $H H$ , the network can be synchronized either in a bounded interval or in an unbounded interval of the coupling strength $σ$ (see Sec. I in the supplementary material). The network synchronizability measures the range of the coupling strength $σ$ in which the synchronous state is stable. According to whether this range is bounded or unbounded, there are two alternative definitions of network synchronizability.

Definition 1

(Network synchronizability for the case that the $σ$ -interval is bounded) —

In the case of synchronization within a bounded interval of the coupling strength $σ$ , the network synchronizability is the eigenratio,

α_{b} = \frac{λ_{2}}{λ_{N}} \leq 1.

(2)

The larger the eigenratio $α_{b}$ , the more synchronizable the network.

Based on this definition, the best possible synchronizability is obtained for $λ_{2} = λ_{3} = \dots = λ_{N}$ , i.e., all equal eigenvalues except for $λ_{1} = 0$ . We note that the original eigenratio introduced in Ref. ³ is equal to $1 / α_{b} = λ_{N} / λ_{2} \geq 1$ (the smaller this other eigenratio, the more synchronizable the network).

Definition 2

(Network synchronizability for the case that the $σ$ -interval is unbounded) —

In the case of synchronization within an unbounded interval of the coupling strength, $σ$ , the network synchronizability is defined in terms of the negative of the eigenvalue $λ_{2}$ of the network Laplacian,

α_{u} = - λ_{2} .

(3)

The larger the $α_{u}$ , the more synchronizable the network.

Based on the choice of the functions $F F$ and $H H$ , either Definition 1 or 2 applies. Both definitions are solely a function of the network topology, which in either case, enables a direct comparison between different networks in terms of their synchronizability (see, e.g., Refs. ³^,⁹^,²⁰^,³², and ⁴⁴).

III. THE CASE OF CLUSTER SYNCHRONIZATION

Consider a network with dynamical equations,

{\dot{x x}}_{i} (t) = F F ({x x}_{i} (t)) + σ \sum_{j = 1}^{N} {\tilde{A}}_{i j} H H (x x_{j} (t)),

(4)

where $i = 1, \dots, N$ . The symmetric matrix $\tilde{A} = (A - δ I_{N})$ is the shifted version of the symmetric adjacency matrix $A$ , where $I_{N}$ is the $N$ -dimensional identity matrix, and the scalar $δ \in R$ . Since the rows of the matrix $\tilde{A}$ do not typically sum to a constant, it is not possible for all the network nodes to synchronize on the same time evolution. Instead, it is possible for sets of nodes to synchronize in clusters. The matrix $\tilde{A} = {{\tilde{A}}_{i j}}$ from Eq. (4) describes the network topology. This network can also be represented as a set of nodes, $V = {v_{1}, \dots, v_{N}}$ , where the dynamical state of the node $v_{i}$ is given by $x x_{i} (t)$ in Eq. (4).

Definition 3

(Equitable clusters (balanced coloring)) —

Consider the network defined by the shifted adjacency matrix, $\tilde{A}$ . The set of the network nodes $V$ can be partitioned into subsets of nodes called equitable clusters, $C_{1}, C_{2}, \dots, C_{C}$ , $\cup_{i = 1}^{C} C_{i} = V$ , $C_{i} \cap C_{j} = \emptyset$ for $i \neq j$ , where

\sum_{h \in C_{ℓ}} {\tilde{A}}_{i h} = \sum_{h \in C_{ℓ}} {\tilde{A}}_{j h}, \begin{matrix} \forall i, j \in C_{k}, \\ \forall C_{k}, C_{ℓ} \subset V . \end{matrix}

(5)

The number of nodes in cluster $C_{k}$ is $n_{k}$ , $\sum_{k = 1}^{C} n_{k} = N .$ A partition of the set of the network nodes $V$ into equitable clusters is also called a balanced coloring.

Definition 4

(Minimum balanced coloring) —

A minimum balanced coloring is a partition of the set of the network nodes $V$ into equitable clusters $C_{1}, C_{2}, \dots, C_{K}$ with the minimum number $K$ of clusters. A fast algorithm for computing the network minimum balanced coloring from knowledge of the matrix $\tilde{A}$ was proposed in Ref. ⁵.

A trivial (non-trivial) cluster is one with only one node (more than one node) in it. We call $\tilde{K} \leq K$ the number of nontrivial clusters. Without loss of generality, we order the clusters such that the first $k = 1, \dots, \tilde{K}$ clusters are nontrivial and the remaining $k = \tilde{K} + 1, \dots, K$ clusters are trivial.

The shifting parameter $δ$ is used to aid in our analysis and has a natural interpretation. We note here that in the case of complete synchronization, Eq. (1), the Laplacian matrix has eigenvalues all with the same sign (except for the zero eigenvalue), while the adjacency matrix $A$ has typically both positive and negative eigenvalues, which provides the motivation for introducing the shift $- δ$ . The shift $- δ$ can be interpreted as a modifier of the network topology by introducing an additional autoregulation loop on each node. The presence of autoregulation loops, in the form of inhibitory interactions, has been documented in bacterial transcriptional regulatory networks, especially in the E. coli,²⁷ and has been associated with a better dynamical response of these networks.³⁷ It has been reported that these autoregulation loops are common motifs observed in biological networks^1,27,42. Regardless, it is important to emphasize that application of the shift $- δ$ is de facto needed in most cases for the emergence of stable CS and is in fact commonly assumed throughout the literature (see, e.g., Refs. ¹⁰^,³⁶^,⁴³^,⁴⁷, and ⁴⁹). Therefore, in what follows, we will proceed under the assumption that a suitable value of $δ$ is given (see our assumption A1 that follows), and study stability of CS as a function of the other parameter $σ$ . In Sec. II in the supplementary material, we will discuss the application of the theory to the case of negative $δ$ , but for now, we assume that $δ$ is positive.

The network allows a flow-invariant cluster synchronization solution ${{s s}_{1} (t), \dots, {s s}_{K} (t)}$ such that $x x_{i} (t) = s s_{k} (t)$ , $i \in C_{k}$ , $k = 1, \dots K$ .¹⁸ The set of equalities $x x_{i} (t) = x x_{j} (t)$ , $\forall i, j \in C_{k}$ defines the invariant CS manifold. By setting $x x_{i} (t) = s s_{k} (t)$ , Eq. (4) can be rewritten as

{\dot{s s}}_{k} (t) = F F ({s s}_{k} (t)) + σ \sum_{j} Q_{k j} H H (s s_{j} (t)),

(6)

$k = 1, \dots, K$ , where the $K$ -dimensional quotient matrix $Q = {Q_{k j}}$ satisfies

Q = {(Z^{T} Z)}^{- 1} Z^{T} \tilde{A} Z = Z^{†} \tilde{A} Z,

(7)

and the $N \times K$ -dimensional indicator matrix $Z = {Z_{i j}}$ is such that $Z_{i j} = 1$ if node $i$ belongs to cluster $C_{j}$ and $Z_{i j} = 0$ otherwise, $j = 1, \dots, K$ . $Z^{†}$ indicates the Moore–Penrose inverse of the matrix $Z$ .

Remark 1

There can be multiple sets of equitable clusters associated with a given adjacency matrix $A$ (see, e.g., Ref. ²¹). Multiple sets of equitable clusters (in addition to the case in which all the nodes are in only one cluster) are also possible in networks with connectivity described by a Laplacian network, with dynamics given by Eq. (1).⁴⁷ The study of the stability of the corresponding CS solutions can be performed using the approaches of Refs. ⁶^,⁴^,⁷^,⁴⁷^,⁴³^,⁴⁹, and ³⁴. For simplicity, in what follows, we focus on the stability of the one CS solution associated with the minimum balanced coloring (Definition 3), but our work is directly generalizable to any CS solution associated with an equitable cluster partition for either Eqs. (1) or (4).

In the rest of this paper, we will focus on the case that the number of clusters $1 < K < N$ , which excludes the cases $K = 1$ corresponding to complete synchronization and $K = N$ corresponding to all trivial clusters. In Sec. III in the supplementary material, we show how the general analysis presented next for the case of CS can be specialized to the case of only one cluster, i.e., complete synchronization, so that the previously introduced Definitions 1 and 2 are retrieved. Under the provision that $1 < K < N$ , there is always at least one non-trivial cluster whose stability can be studied.

We can assess CS stability³⁶ by studying small perturbations about the cluster synchronous solution $w w_{i} (t) = (x x_{i} (t) - s s_{i *}^{σ} (t))$ , where $s s_{i *}^{σ} (t)$ indicates the synchronous solution of the cluster $C_{i *}$ to which node $i$ belongs [the superscript $σ$ is used to emphasize that the cluster synchronous solution depends on $σ$ through Eq. (6)],

{\dot{w w}}_{i} (t) = D F F (s s_{i *}^{σ} (t)) {w w}_{i} (t) + σ \sum_{j} {\tilde{A}}_{i j} D H H (s s_{j *}^{σ} (t)) {w w}_{j} (t),

(8)

$i = 1, \dots, N$ .

The concept of isolated CS, originally introduced in Ref. ³⁶, indicates that the range of a given parameter that synchronizes each cluster may be different for different clusters.

Definition 5

(Isolated cluster synchronization) —

Isolated synchronization occurs when for a given coupling strength, $σ$ , nodes in one or more clusters synchronize but nodes in other clusters do not.

IV. CLUSTER SYNCHRONIZABILITY

In what follows, we categorize the networks to have either:

(a)
no intertwined clusters or
(b)
at least one intertwined cluster.

The concept of intertwined clusters was originally introduced in Ref. ³⁶. See Definition 12 in Sec. IV B for a formal definition of intertwined clusters, and Sec. IV in the supplementary material for further discussion. In this paper, we mostly focus on case (a), which we present in Sec. IV A. We briefly present case (b) in Sec. IV B.

A. Networks with no intertwined clusters

Now, we discuss the general case of cluster synchronizability in networks with no intertwined clusters. We omit the derivation and present the main result that by using a proper similarity transformation $T$ ,^33,36 the coupling matrix $\tilde{A}$ can be decomposed as follows:

T \tilde{A} T^{- 1} = \bar{Q} ⨁ R,

(9)

where the symbol $⨁$ indicates the direct sum of matrices, the “parallel” matrix $\bar{Q}$ is $K$ -dimensional, and the “transverse” matrix $R$ is $(N - K)$ -dimensional diagonal matrix. A proof of Eq. (9) can be found in Sec. V in the supplementary material. The entries on the main diagonal of $R$ are the “transverse eigenvalues” of $\tilde{A}$ . One can immediately see that the set $Λ$ of the eigenvalues of the matrix $\tilde{A}$ is partitioned into the two sets: the set $Λ_{\bar{Q}} = {λ_{1}^{\bar{Q}}, \dots, λ_{K}^{\bar{Q}}}$ of the eigenvalues of the matrix $\bar{Q}$ and the set $Λ_{R} = {λ_{1}^{R}, \dots, λ_{(N - K)}^{R}}$ of the transverse eigenvalues of the matrix $R$ , $Λ = Λ_{\bar{Q}} \cup Λ_{R}$ .

The set of transverse eigenvalues, $Λ_{R}$ , can be further partitioned into $\tilde{K}$ subsets, $Λ_{R}^{k}$ , $k = 1, \dots, \tilde{K}$ , where each subset corresponds to one non-trivial cluster^33,46 (for more details, see Sec. V in the supplementary material). The subset $Λ_{R}^{k}$ contains $(n_{k} - 1)$ eigenvalues $λ_{R, i}^{k}$ , where $n_{k}$ is the number of nodes in cluster $C_{k}$ , and $i = 1, \dots, n_{k} - 1$ . Since here we are only concerned with the transverse eigenvalues, we omit the superscript $R$ and indicate the $i$ th transverse eigenvalue for cluster $C_{k}$ with the notation $λ_{i}^{k}$ , i.e., $λ_{i}^{k} \in Λ_{R}^{k}$ , $i = 1, \dots, n_{k} - 1$ , and $k = 1, \dots, \tilde{K}$ . We also label $μ_{i}^{k} = - λ_{i}^{k} \geq 0$ . Then, $μ_{max}^{k} = max_{i} μ_{i}^{k}$ and $μ_{min}^{k} = min_{i} μ_{i}^{k}$ for each cluster $C_{k}$ , $k = 1, \dots, \tilde{K}$ . We will use this notation to define the cluster synchronizability later on.

As a result, the set of Eq. (8) can be transformed into a set of independently evolving perturbations, which can be divided into two categories, those parallel to the synchronization manifold $y y^{p} (t) \in R^{K m}$ and those transverse $y y^{t} (t)$ to the synchronization manifold. Only the transverse perturbations $y y^{t} (t) \in R^{(N - K) m}$ determine stability about the cluster synchronous solution. Following Ref. ⁴⁶, the dynamics of the transverse perturbations can be written as

{\dot{y y}}_{i}^{t} (t) = [D F F ({s s}_{i *}^{σ} (t)) - σ μ_{i}^{R} D H H (s s_{i *}^{σ} (t))] {y y}_{i}^{t} (t),

(10)

$i = 1, \dots, (N - K)$ , where in Eq. (10), we use the negative of the eigenvalues $μ_{i}^{R} = - λ_{i}^{R}$ for convenience. ${s s}_{i *}^{σ} (t)$ indicates the synchronous solution corresponding to $C_{i *}$ and $- μ_{i}^{R} \in Λ_{R}^{i *}$ . Based on our assumption A1, which we introduce below, all $λ_{i}^{R} \leq 0$ and so all $μ_{i}^{R} \geq 0$ . The discussion that follows could use either the eigenvalues $λ_{i}^{R}$ or the negative of the eigenvalues $μ_{i}^{R}$ . We opt for the $μ_{i}^{R}$ as in general we find easier to refer to positive quantities.

Definition 6

(Stability of the synchronous state of each cluster) —

The synchronous state of each non-trivial cluster $i * = 1, \dots, \tilde{K}$ is stable if the maximum Lyapunov exponent (MLE) associated with Eq. (10) is negative for all $- μ_{i}^{R} \in Λ_{R}^{i *}$ , i.e., if $M L E_{i *} (s s_{i *}^{σ}, σ μ_{i}^{R}) < 0$ , where the first argument is used to indicate the dependence on the cluster synchronous solution $s s_{i *}^{σ} (t)$ (which depends on $σ$ ) and the second argument is used to indicate the dependence on the products $μ_{i}^{R}$ times $σ$ .

Remark 2

The fact that $M L E_{i *} (s_{i *}^{σ}, σ μ_{i}^{R}) < 0$ depends on $σ$ through both its arguments is in contrast to the case of complete synchronization for which the synchronous solution does not depend on $σ$ .³⁵

Definition 7

(Cluster master stability function) —

We define the cluster master stability function (CMSF) $M_{k}^{σ} (σ ξ) = M L E_{k} (s_{k}^{σ}, σ ξ)$ , which returns the MLE associated with Eq. (10), for the cluster synchronous solution $s s_{k}^{σ} (t)$ as a function of the parameters $σ$ and $σ ξ = σ μ_{i}^{R}$ , where $σ$ and $ξ$ can vary independently of one another.

Remark 3

Note that the cluster master stability function $M_{k}^{σ} (σ ξ)$ depends on $σ$ through both the cluster synchronous solution $s s_{k}^{σ} (t)$ (superscript $σ$ ) and the argument $σ ξ$ .

Remark 4

The condition for stability of cluster k is that

M_{k}^{σ} (σ ξ) < 0, \forall ξ = - μ_{i}^{R} \in Λ_{R}^{k} .

(11)

In what follows, we proceed under the following three assumptions:

A1:
The eigenvalues of the matrix $R$ are all negative, which can be ensured by appropriately choosing $δ$ .
A2:
The CMSF is either negative in a bounded interval of its argument, i.e., $M_{k}^{σ} (σ ξ) < 0$ for $a_{1}^{k, σ} \leq ξ \leq a_{2}^{k, σ}$ , where $a_{1}^{k, σ}, a_{2}^{k, σ} > 0$ (equivalently, $b_{1}^{k, σ} \leq σ ξ \leq b_{2}^{k, σ}$ , with $b_{1}^{k, σ} = σ a_{1}^{k, σ}$ and $b_{2}^{k, σ} = σ a_{2}^{k, σ}$ ) or in an unbounded range of its argument, i.e., $M_{k}^{σ} (σ ξ) < 0$ for $a_{c}^{k, σ} \leq ξ$ , where $a_{c}^{k, σ} > 0$ (equivalently, $b_{c}^{k, σ} \leq σ ξ$ , with $b_{c}^{k, σ} = σ a_{c}^{k, σ}$ ). In what follows, we will simply refer to the former as “the bounded case” and to the latter as “the unbounded case.”
A3:
The lower and upper bounds $a_{1}^{k, σ}$ and $a_{2}^{k, σ}$ vary smoothly with $σ$ .

We can then introduce the following definitions for the synchronizability of each cluster:

Definition 8

(Synchronizability of each cluster) —

In the bounded case, the synchronizability of cluster $C_{k}$ is equal to the eigenratio $η_{b}^{k} = \frac{μ_{m i n}^{k}}{μ_{m a x}^{k}}$ , and in the unbounded case, it is equal to $η_{u}^{k} = μ_{m i n}^{k}$ .

Remark 5

The definitions of synchronizability of cluster $C_{k}$ are consistent with the observation that given $b_{1}^{k, σ}$ and $b_{2}^{k, σ}$ , increasing $η_{b}^{k}$ ( $η_{u}^{k}$ ) will necessarily increase the cluster synchronizability, i.e., the range of $σ$ over which the CS solution is stable. This is explained graphically in Fig. 1 for the bounded case.

An external file that holds a picture, illustration, etc.
Object name is CHAOEH-000032-041101_1-g001.jpg

Open in a separate window

FIG. 1.

Schematic representation of the synchronizability of cluster $C_{k}$ for the bounded case. The master stability function $M_{k}^{σ} (σ ξ) < 0$ for $b_{1}^{k, σ} \leq σ ξ \leq b_{2}^{k, σ}$ . The figure shows the lines $σ μ_{max}^{k}$ and $σ μ_{min}^{k}$ , going through the maximum and minimum eigenvalue, $ξ = μ_{max}^{k}$ and $ξ = μ_{min}^{k}$ at $σ = 1$ (there can be other eigenvalues in between). The lines intersect the curves $b_{1}^{k, σ}$ and $b_{2}^{k, σ}$ twice. However, $σ_{min}$ is determined by the intersection of $σ μ_{min}^{k}$ with $b_{1}^{k, σ}$ and $σ_{max}$ is determined by the intersection of $σ μ_{max}^{k}$ with $b_{2}^{k, σ}$ . The critical coupling strengths, $σ_{min}$ and $σ_{max}$ , determine the width of the $σ$ -interval over which the synchronous solution is stable.

Figure 1 shows how the eigenratio $μ_{min}^{k} / μ_{max}^{k}$ relates to the width of the $σ$ -interval in which cluster $C_{k}$ synchronizes. The cluster master stability function $M_{k}^{σ} (σ ξ) < 0$ for $b_{1}^{k, σ} \leq σ ξ \leq b_{2}^{k, σ}$ , where $b_{1}^{k, σ}$ and $b_{2}^{k, σ}$ are two arbitrary functions of $σ$ . The figure shows the lines $σ μ_{max}^{k}$ and $σ μ_{min}^{k}$ , intersecting the functions $b_{1}^{k, σ}$ and $b_{2}^{k, σ}$ twice. However, independent of the particular shapes of the functions $b_{1}^{k, σ}$ and $b_{2}^{k, σ}$ , $σ_{min}$ is determined by the intersection of the line $σ μ_{min}^{k}$ with $b_{1}^{k, σ}$ and $σ_{max}$ is determined by the intersection of the line $σ μ_{max}^{k}$ with $b_{2}^{k, σ}$ . The critical coupling strengths, $σ_{min}$ and $σ_{max}$ , determine the range of $σ$ over which the synchronous solution for cluster $C_{k}$ is stable. We can then write $\frac{σ_{max}}{σ_{min}} = \frac{b_{2}^{k, σ}}{b_{1}^{k, σ}} \frac{μ_{min}^{k}}{μ_{max}^{k}}$ , where the first ratio $\frac{μ_{min}^{k}}{μ_{max}^{k}}$ represents the effect of the network topology and the second ratio $\frac{b_{2}^{k, σ}}{b_{1}^{k, σ}}$ represents the effect of the dynamics, in terms of the functions $F F$ and $H H$ . As the ratio $\frac{μ_{min}^{k}}{μ_{max}^{k}}$ increases, i.e., as the eigenvalues move closer to one another, the synchronizability of cluster $C_{k}$ increases. Changing the functions $F F$ and $H H$ only moves the functions $b_{2}^{k, σ}$ and $b_{1}^{k, σ}$ (and not the lines $σ μ_{i}^{k}$ ). Changing the network topology affects the lines $σ μ_{i}^{k}$ but also, through the dynamics of the quotient network, the functions $b_{2}^{k, σ}$ and $b_{1}^{k, σ}$ . Our main result is that even if these two functions change as a result of changing the network topology, the intersections with the lines $σ μ_{i}^{k}$ always occur for $μ_{i}^{k} = μ_{min}^{k}$ and $μ_{i}^{k} = μ_{max}^{k}$ .

1. Numerical example

As a reference example, we consider the network with $N = 15$ nodes and $K = 2$ clusters in Fig. 2. This network consists of two circles, each one corresponding to a cluster: the larger cluster, $C_{1}$ , has $n_{1} = 10$ nodes, where each node is connected to its six nearest neighbors, with coupling weight $w_{1}$ . The smaller cluster, $C_{2}$ , is a fully connected circle with $n_{2} = 5$ nodes and coupling weight $w_{2}$ . Each node in one circle is coupled to all the nodes in the other circle and vice versa, with coupling weight $w_{c}$ . The shifted adjacency matrix, $\tilde{A} = A - δ I_{15}$ is

An external file that holds a picture, illustration, etc.
Object name is CHAOEH-000032-041101_1-g0d1.jpg

(12)

In order to assess the emergence of cluster synchronization, Eq. (4) is integrated for a wide range of the coupling strength $σ$ . For each value of $σ$ , the initial conditions were determined as follows. First, the dynamics of the uncoupled system $s s (t)$ is integrated for a long time so that it converges on its attractor. Then, a randomly selected point from the attractor of $s s (t)$ is picked and set as the initial condition of the quotient equation [Eq. (6)]. For a given value of $σ$ , the quotient network dynamics (6) is integrated for a long time so that it converges on its attractor. Then, a point from the synchronous state for each cluster, $s s_{k} (t)$ , $k = 1, \dots, K$ , is picked randomly, and the following steps are taken:

1.
Small perturbations are added to this point to be used as initial conditions for the network dynamics [Eq. (4)] with the selected $σ$ .
2.
This point is used as the initial condition of the quotient equation [Eq. (6)] for the next value of $σ$ .

The procedure is repeated for increasing values of $σ$ .

An external file that holds a picture, illustration, etc.
Object name is CHAOEH-000032-041101_1-g002.jpg

Open in a separate window

FIG. 2.

15-node undirected and weighted network. The adjacency matrix of this network, $\tilde{A}$ , is shown in Eq. (12). Clusters are shown in different colors: green nodes (1–10) are in the first cluster, $C_{1}$ and blue nodes (11–15) are in the second cluster, $C_{2}$ . Green, blue, red, and black edges have weights $w_{1}$ , $w_{2}$ , $w_{c}$ , and $- δ$ , respectively.

We select the individual uncoupled systems to be Rössler’s oscillators with $x x = {[x y z]}^{T} \in R^{3}$ , $F F : R^{3} \to R^{3}$ , $H H : R^{3} \to R^{3}$ ,

F F (x x) = [\begin{matrix} - y - z \\ x + a y \\ b + (x - c) z \end{matrix}], H H (x x) = [\begin{matrix} x \\ 0 \\ 0 \end{matrix}] .

(13)

We set $a = b = 0.2$ and $c = 5.7$ , which corresponds to chaotic dynamics of the Rössler oscillator. We set $\tilde{A}$ as in Eq. (12) and we set $w_{1} = 2$ , $w_{2} = 3$ , $w_{c} = 0.1$ , and $δ = 12$ . The transverse eigenvalues for the two clusters are $Λ_{R}^{1} = {- 17.24, - 17.24, - 16, - 13.24, - 13.24, - 12.76, - 12.76, - 8.76, - 8.76}$ and $Λ_{R}^{2} = {- 15, - 15, - 15, - 15}$ . Our choice of the functions $F F$ and $H H$ is such that the CMSF is bounded, according to assumption A2. We simulate Eq. (4) over a wide range of $σ$ . Then, the synchronization error for each cluster, $E_{k}$ , is calculated as

E_{k} = {⟨ \sum_{i = 1}^{n_{k}} ‖ x x_{i} (t) - {\bar{x x}}_{k} (t) ‖_{2} ⟩}_{τ}, i \in C_{k}, k = 1 and 2,

(14)

where ${\bar{x x}}_{k} (t)$ is the average time evolution of the states of the nodes in $C_{k}$ , and ${⟨ \cdot ⟩}_{τ}$ indicates an average over the time interval $τ$ . Here, we take $τ = [900, 1000]$ . Figure 3 is a plot for synchronization error $E_{k}$ computed as in Eq. (14) as a function of $σ$ . The CMSF plot (see Definition 7), corresponding to each one of the two clusters, is shown in Fig. 4. By comparing Fig. 3 and Fig. 4, one sees that the eigenratio $μ_{min}^{k} / μ_{max}^{k}$ correctly measures the width of the synchronous $σ$ -interval of the above network and dynamics. Figure 4 also shows how the synchronous $σ$ -interval of each cluster can be found from the CMSF plot. There is excellent agreement between the numerical evaluation of the synchronous $σ$ -interval from Figs. 3 and and44.

An external file that holds a picture, illustration, etc.
Object name is CHAOEH-000032-041101_1-g003.jpg

Open in a separate window

FIG. 3.

Blue and red curves represent the synchronization errors $E_{1}$ and $E_{2}$ for clusters $C_{1}$ and $C_{2}$ , respectively. The synchronous $σ$ interval for $C_{1}$ is $0.0075 < σ^{1} < 0.239$ , and for $C_{2}$ , it is $0.0052 < σ^{2} < 0.259$ .

An external file that holds a picture, illustration, etc.
Object name is CHAOEH-000032-041101_1-g004.jpg

Open in a separate window

FIG. 4.

CMSF plots for clusters $C_{1}$ (a) and $C_{2}$ (b) (see Definition 7). Following the method described in Fig. 1, the lines connecting the origin to the eigenvalues $μ_{max}^{k}$ and $μ_{min}^{k}$ are plotted in dashed white lines and the intersections are found with the $M_{k} = 0$ black contour, $b_{1}^{k, σ}$ and $b_{2}^{k, σ}$ , to find $σ_{max}^{k}$ and $σ_{min}^{k}$ . For better visualization, the bottom left corner of each plot is magnified in the insets to show $σ_{max}^{k}$ and $σ_{min}^{k}$ . The boundaries for $σ$ that are found from these CMSF plots coincide with the boundaries shown in Fig. 3.

2. Conditions for cluster synchronization

So far, we have proposed a definition of cluster synchronizability that independently applies to each cluster within a complex network. Next, we focus on conditions under which the entire network synchronizes, i.e., for nodes in different clusters to synchronize at the same time. Since nodes in one cluster may synchronize independently of nodes in another cluster, this type of analysis is considerably more complex than before and will lead to the observation of different types of cluster synchronization, namely, Matryoshka CS, partially disjoint CS, and completely disjoint CS. Under general conditions, we will not be able to derive a definition of cluster synchronizability for the entire network that only reflects the network structure. In fact, both the bounded case and the unbounded case require considerations that generally depend on both the network structure and the dynamics.

In the bounded case, for each cluster $C_{k}$ an interval of $σ$ , $[σ_{min}^{k}, σ_{max}^{k}]$ can be found such that the synchronous solution of that particular cluster is stable. The intervals for the stability of the synchronous solution of each cluster are not necessarily the same, which is associated with the phenomenon of isolated CS.³⁶

Definition 9

(Condition for cluster synchronization of the network (bounded case)) —

A network can be cluster-synchronized if there exists a value of $σ$ such that,

max_{k = 1, \dots, \tilde{K}} (σ_{min}^{k}) < σ < min_{k = 1, \dots, \tilde{K}} (σ_{max}^{k}) .

(15)

Note that Definition 9 corresponds to all nontrivial cluster synchronizing. Now, let

k_{1} = \underset{k = 1, \dots, \tilde{K}}{\arg \max} (σ_{min}^{k}), k_{2} = \underset{k = 1, \dots, \tilde{K}}{\arg \min} (σ_{max}^{k}),

(16)

where $k_{1}$ and $k_{2}$ indicate the critical clusters $C_{k_{1}}$ and $C_{k_{2}}$ that correspond to the largest lower bound and the smallest upper bound among all the clusters, respectively. Let us assume that for a given $σ$ value, nodes in all clusters are synchronized in their respective cluster synchronous solutions, $s s_{k}$ , $k = 1, \dots, K$ . In the case of bounded MSF, as we decrease (increase) this $σ$ , there will be one critical cluster $C_{k_{1}}$ ( $C_{k_{2}}$ ) whose nodes are the first to desynchronize. In general, $k_{1}$ and $k_{2}$ can either be the same ( $k_{1} = k_{2}$ ) or different ( $k_{1} \neq k_{2}$ ). In either case, we can rewrite Eq. (15) as

σ_{min}^{k_{1}} \leq σ \leq σ_{max}^{k_{2}} .

(17)

Definition 10

(The network cluster synchronizability ratio—bounded case) —

The network cluster synchronizability ratio $ρ$ is defined as the ratio between the maximum and minimum values of $σ$ for which the entire network cluster-synchronizes,

ρ := \frac{σ_{max}^{k_{2}}}{σ_{min}^{k_{1}}} .

(18)

The ratio $ρ$ can be directly measured in simulation by integrating Eq. (4) for different values of the parameter $σ$ and recording the smallest and the largest values of $σ$ for which all nontrivial clusters synchronize. Thus the cluster synchronizability ratio, $ρ$ , measures the width of the $σ$ -interval over which the network cluster-synchronizes.

We can then introduce the following definition:

Definition 11

(Cluster synchronizability set) —

The cluster synchronizability set $η_{S}$ of a network is the set of the synchronizabilities of all nontrivial clusters (see Definition 8), i.e.,

η_{S} := {η_{*}^{1}, η_{*}^{2}, \dots, η_{*}^{\tilde{K}}},

(19)

where $*$ denotes the specific case of the CMSF for each cluster $C_{k}$ , i.e., in the bounded case, $η_{*}^{k} = η_{b}^{k}$ , and in the unbounded case, $η_{*}^{k} = η_{u}^{k}$ , $k = 1, \dots, \tilde{K}$ .

The above definition reflects the fact that since nodes in each cluster may synchronize independently from nodes in other clusters, a meaningful characterization of the network cluster synchronizability requires information about the synchronizability of all its nontrivial clusters.

We emphasize here that defining a single valued measure that describes the cluster synchronizability of a network remains an open challenge. We further discuss this in Sec. VI in the supplementary material, where we present a possible definition but also highlight the shortcomings of such definition.

We note that by assuming knowledge of the type of synchronization (bounded or unbounded, see assumption A2), the synchronizability of each cluster $η_{*}^{k}$ , $k = 1, \dots, \tilde{K}$ , can be easily computed only from the network topology. This is similar to the case of complete synchronization.

In what follows, we look in more detail at the possible types of cluster-to-cluster synchronization that can be observed in a network and sub-categorize isolated synchronization in the following three types:

(a)
Matryoshka cluster synchronization, which occurs when the synchronous $σ$ -interval of cluster $C_{a}$ , is completely contained in the $σ$ -interval of cluster $C_{b}$ ,
$[σ_{min}^{a}, σ_{max}^{a}] \subseteq [σ_{min}^{b}, σ_{max}^{b}] .$
(20)
If the nodes in cluster $C_{a}$ synchronize, the nodes in cluster $C_{b}$ synchronize as well, but the reverse implication is not true.
(b)
Partially disjoint cluster synchronization, which occurs when the intersection of the synchronous $σ$ -intervals of clusters $C_{a}$ and $C_{b}$ is nonempty and it does not coincide with any of the two intervals. In this case, the lower and upper bounds of the synchronous coupling strength, $σ$ , are not from the same cluster,
$a = \underset{k = a, b}{\arg \max} (σ_{min}^{k}), b = \underset{k = a, b}{\arg \min} (σ_{max}^{k}) .$
(21)
(c)
Complete disjoint cluster synchronization, which occurs when the intersection of the synchronous $σ$ -intervals of two clusters is empty. In this case, the lower bound of $σ$ from Eq. (15) is greater than the upper bound. As a result, there is no $σ$ such that the synchronous solutions of the two clusters are stable at the same time.

These definitions can be generalized to the case of more than two clusters.

3. Numerical analysis

We take the network with adjacency matrix described in Eq. (12), and for the dynamics, we select the individual uncoupled systems to be Van der Pol oscillators with $x x = {[x_{1} x_{2}]}^{T} \in R^{2}$ , $F F : R^{2} \to R^{2}$ , and $H H : R^{2} \to R^{2}$ ,

F F (x x) = [\begin{matrix} x_{2} \\ - x_{1} + 3 (1 - x_{1}^{2}) x_{2} \end{matrix}], H H (x x) = [\begin{matrix} 0 \\ x_{2} \end{matrix}] .

(22)

In order to assess the stability of the synchronous solution $s s_{k} (t)$ , we define

Γ_{k} (σ) = max_{- μ_{i}^{R} \in Λ_{R}^{k}} M_{k}^{σ} (σ μ_{i}^{R}),

(23)

which returns the maximum of the MLEs associated with Eq. (10) over the transverse eigenvalues of the cluster $C_{k}$ as a function of $σ$ , $k = 1, \dots, \tilde{K}$ . $Γ_{k} (σ) < 0$ ( $Γ_{k} (σ) > 0$ ) indicates that the nodes in $C_{k}$ are (not) synchronized to $s s_{k} (t)$ with coupling strength $σ$ .

(a)
By setting the network parameters to $w_{1} = 2$ , $w_{2} = 3$ , $w_{c} = 0.1$ , $δ = 12$ , we obtain a case of Matryoshka synchronization. The transverse eigenvalues for the two clusters are $Λ_{R}^{1} = {- 17.24, - 17.24, - 16, - 13.24, - 13.24, - 12.76, - 12.76, - 8.76, - 8.76}$ and $Λ_{R}^{2} = {- 15, - 15, - 15, - 15}$ . The upper part of Fig. 5(a) is a plot of the synchronization error [defined in Eq. (14)] $E_{1}$ for cluster $C_{1}$ (in blue) and $E_{2}$ for cluster $C_{2}$ (in red). The lower part of the figure shows $Γ_{1}$ and $Γ_{2}$ as defined in Eq. (23). The $σ$ -interval for the network synchronization is $0.010 < σ < 0.610$ . The lower bound and the upper bound are determined by $C_{1}$ . Therefore, the synchronizability of each cluster is $η_{b}^{1} = μ_{min}^{1} / μ_{max}^{1} = 8.76 / 17.24 ≃ 0.50$ and $η_{b}^{2} = μ_{min}^{2} / μ_{max}^{2} = 15 / 15 = 1$ .
Open in a separate window
FIG. 5.
Isolated CS: Matryoshka, partially, and complete disjoint CS. The upper plot of each panel shows the CS error $E_{k}$ vs $σ$ , while the lower plot shows $Γ_{k}$ , computed as defined in Eq. (23), $k = 1, 2$ vs $σ$ . Blue and red curves represent the synchronization errors $E_{1}$ and $E_{2}$ for the clusters $C_{1}$ and $C_{2}$ , respectively. (a) shows the synchronous $σ$ interval of cluster $C_{1}$ , which is contained in the synchronous $σ$ interval of cluster $C_{2}$ , which is Matryoshka synchronization. The synchronous $σ$ interval for $C_{1}$ is $0.010 < σ < 0.610$ , and for $C_{2}$ , it is $0.005 < σ < 2.610$ . (b) shows a synchronous $σ$ interval in the case that the lower bound is from $C_{1}$ and the upper bound is from $C_{2}$ , which is partially disjoint synchronization. The synchronous $σ$ interval for $C_{1}$ is $0.022 < σ < 2.71$ , and for $C_{2}$ , it is $0.009 < σ < 1.81$ . (c) shows that there is no synchronous $σ$ that synchronizes both clusters at the same time, which is complete disjoint synchronization. The synchronous $σ$ interval for $C_{1}$ is $0.260 < σ < 3.810$ , and for $C_{2}$ , it is $0.003 < σ < 0.100$ .
(b)
Now consider the same network with parameters, $w_{1} = 1$ , $w_{2} = 3$ , $w_{c} = 0.1$ , and $δ = 12$ . Then, the transverse eigenvalues for each cluster are $Λ_{R}^{1} = {- 14.61, - 14.61, - 14, - 12.61, - 12.61, - 12.38, - 12.38, - 10.38, - 10.38}$ and $Λ_{R}^{2} = {- 15, - 15, - 15, - 15}$ . This corresponds to a case of partially disjoint synchronization [see Fig. 5(b)]. The upper part of Fig. 5(b) is a plot of the synchronization error $E_{1}$ for cluster $C_{1}$ (in blue) and $E_{2}$ for cluster $C_{2}$ (in red). The lower part of the figure shows $Γ_{1}$ and $Γ_{2}$ . The $σ$ interval for network synchronization is $0.022 < σ < 1.81$ . The lower bound and the upper bound are determined from the first and second clusters, respectively. Therefore, the synchronizabilities of each cluster are $η_{b}^{1} = μ_{min}^{1} / μ_{max}^{1} = 10.38 / 14.61 ≃ 0.71$ , and $η_{b}^{2} = μ_{min}^{2} / μ_{max}^{2} = 15 / 15 = 1$ .
(c)
Finally, we consider the network parameters $w_{1} = 0.1$ , $w_{2} = 10$ , $w_{c} = 0.1$ , and $δ = 12$ . Then, the transverse eigenvalues of each cluster are $Λ_{R}^{1} = {- 12.26, - 12.26, - 12.20, - 12.06, - 12.06, - 12.04, - 12.04, - 11.84, - 11.84}$ and $Λ_{R}^{2} = {- 22, - 22, - 22, - 22}$ . This corresponds to a case of complete disjoint synchronization, for which the network cannot be synchronized by any choice of $σ$ . The upper part of Fig. 5(c) is a plot of the synchronization errors $E_{k}$ for each cluster as a function of $σ$ . The lower part of the figure shows $Γ_{1}$ and $Γ_{2}$ .

Figure 6 shows the synchronizability $η_{b}^{1}$ (Definition 8) vs $w_{1}$ for the dynamical network described by Eqs. (4) and (22) with adjacency matrix from Eq. (12). The coupling weight of the first cluster, $w_{1}$ , is varied from 0.1 to 7, while the other network parameters $δ = 12, w_{c} = 0.1$ , and $w_{2} = 3$ are kept constant. For increasing values of $w_{1}$ from 0.1, we first see partially disjoint CS, then Matryoshka CS, then, partially disjoint CS again. The synchronizability $η_{b}^{1}$ of cluster $C_{1}$ is shown to decrease in each one of the intervals. We also plot the numerically computed synchronizability ratio $ρ$ and find very good agreement with $η_{b}^{1}$ . The synchronizability of the second cluster is a constant $η_{b}^{2} = 15 / 15 = 1$ as $w_{1}$ is varied since the transverse eigenvalues of the second cluster $Λ_{R}^{2}$ are independent from $w_{1}$ . We note that Figs. 5(a) and 5(b) correspond to choosing $w_{1} = 2$ and $w_{1} = 1$ shown in Fig. 6, respectively.

An external file that holds a picture, illustration, etc.
Object name is CHAOEH-000032-041101_1-g006.jpg

Open in a separate window

FIG. 6.

Synchronizability measures $η_{b}^{1}$ and the normalized synchronizability ratio $ρ$ vs $w_{1}$ , the coupling weight of the first cluster, while the other parameters of the network, $δ = 12, w_{c} = 0.1$ , and $w_{2} = 3$ , are kept constant. We integrate the dynamics equation (4) with functions from Eq. (22) and the network from Eq. (12). We see that as $w_{1}$ is varied, the type of synchronization changes. For $0.1 \leq w_{1} \leq 1.88$ , we see partially disjoint CS where the lower and upper bounds of $σ$ are determined by $C_{1}$ and $C_{2}$ , respectively. For $1.89 \leq w_{1} \leq 3.22$ , we see Matryoshka CS where $C_{1}$ is the critical cluster. Finally, for $3.23 \leq w_{1} \leq 7$ , we see partially disjoint CS again where the lower and upper bounds of $σ$ are now determined by $C_{2}$ and $C_{1}$ , respectively.

B. Networks with intertwined clusters

In this section, we focus on the general case of networks with intertwined clusters. A rigorous definition for intertwined clusters is provided next.

Definition 12

(Intertwined clusters) —

Suppose $B = {C_{1}, C_{2}, \dots, C_{C}}$ is a clustering of nodes so that the clusters form a balanced coloring (see Definition 3) with at least $C \geq 2$ clusters and let $C_{i}, C_{j} \in B$ be two distinct clusters. We say that $C_{i}$ and $C_{j}$ are intertwined if there are partitions $P = {P_{1}, \dots, P_{k}}$ of $C_{i}$ and $Q = {Q_{1}, \dots, Q_{ℓ}}$ of $C_{j}$ so that $k \geq 2$ , $ℓ \geq 2$ , and the following conditions are satisfied.

1.
The sets $(B - {C_{i}}) \cup P$ and $(B - {C_{j}}) \cup Q$ are not balanced colorings.
2.
The set $(B - {C_{i}, C_{j}}) \cup P \cup Q$ is a balanced coloring.

Some notes to consider about this definition are as follows:

1.
If two clusters are intertwined, this does not preclude a different partition of one (or both) that would result in a balanced coloring alone.
2.
There is a connection between intertwined clusters and algorithms that find minimal balanced coloring (see, e.g., Refs. ⁵ and ²¹).

For more discussion about intertwined clusters, see Sec. IV in the supplementary material.

We define the $N$ -dimensional diagonal indicator matrices $E_{k} = {e_{i j}}$ , $k = 1, \dots, K$ , such that $e_{i i} = 1$ if node $i$ belongs to the cluster $C_{k}$ , and $e_{i i} = 0$ otherwise.

The stability of the CS solution depends on the dynamics of small perturbations around the synchronous solution, $w w_{i} (t) = (x x_{i} (t) - s s_{i *} (t)))$ . The dynamics of the vector $w w (t) = [{w w_{1} (t)}^{T}, {{w w_{2} (t)}^{T}, \dots, {w w_{N} (t)}^{T}]}^{T}$ obeys

\dot{w w} (t) = [\sum_{k = 1}^{K} E_{k} \otimes D F F (s s_{k} (t)) + σ \sum_{k = 1}^{K} \tilde{A} E_{k} \otimes D H H (s s_{k} (t))] w w (t) .

(24)

By using a proper transformation matrix, $T$ ,^33,36,49 the shifted adjacency matrix, $\tilde{A}$ , is still decomposed into the form of Eq. (9), where the “parallel” matrix $\bar{Q}$ is $K$ -dimensional, and the “transverse” matrix $R$ is $(N - K)$ -dimensional. The matrix $T$ decouples the matrix $\tilde{A}$ into finest blocks,^33,36,49 which results in the following block-diagonal structure for the transverse matrix $R$ :

R = ⨁_{l = 1}^{L} R_{l},

(25)

where $L$ is the total number of blocks in $R$ and $1 \leq L < (N - K)$ .

We will analyze the stability of the synchronous solution in terms of the dynamics of the transverse perturbations. After applying the transformation $T$ , we can rewrite Eq. (24) as

\dot{\tilde{y y}} (t) = [\sum_{k = 1}^{K} J_{k} \otimes D F F (s s_{k} (t)) + σ \sum_{k = 1}^{K} B J_{k} \otimes D H H (s s_{k} (t))] \tilde{y y} (t),

(26)

where $B = T \tilde{A} T^{- 1} = \bar{Q} ⨁ R$ , and $J_{k} = T E_{k} T^{- 1}$ , $k = 1, \dots, K$ . The perturbations can be divided into the stack of vectors $\tilde{y y} (t) = {[{\tilde{y y}}_{\bar{Q}} {(t)}^{T}, {{\tilde{y y}}_{R} (t)}^{T}]}^{T}$ , where ${\tilde{y y}}_{R} (t) = {[{{\tilde{y y}}_{1} (t)}^{T}, {{\tilde{y y}}_{2} (t)}^{T}, \dots, {{\tilde{y y}}_{L} (t)}^{T}]}^{T}$ corresponds to the transverse perturbation equations for each block of $R$ . For each block $R_{l}$ , $l = 1, \dots, L$ , there is an interval of $σ$ in which $M L E (s s_{i *}^{σ}, σ^{l}) < 0, \forall σ^{l} \in [σ_{min}^{l}, σ_{max}^{l}]$ . As a result, the network can synchronize if

\exists σ : max_{l = 1, \dots, L} (σ_{min}^{l}) \leq σ \leq min_{l = 1, \dots, L} (σ_{max}^{l}) .

(27)

Note that this is the most general condition for synchronization presented in this paper.

In the case of intertwined clusters, the definitions of different cases of synchronization, Matryoshka, partially disjoint, and complete disjoint from Sec. IV A are still valid, but with the difference that now those definitions apply to the blocks of the matrix $R$ . For each pair of blocks, we can either have Matryoshka synchronization (if the synchronous $σ$ intervals are contained in one another), or partially disjoint synchronization (if one block determines the lower bound and the other determines the higher bound of the synchronous $σ$ interval of the pair) or completely disjoint synchronization (if there is no value of $σ$ that stabilizes the pair of blocks).

C. Real networks analysis

In this subsection, we consider several real networks from the literature. The first dataset, case16ci, is a power distribution network.^12,50 The second network, case85, is a radial power distribution network.^14,50 The third network, backward circuit, is a neural network, originally from Ref. ³⁰ and was manually repaired in Ref. ²⁴. The fourth network, macaque-rhesus-brain-2, is a human brain network.^2,39 The fifth network, rt-retweet, is a retweet network of Twitter users based on various social and political hashtags.⁴⁰ In Table I, we provide a summary of the main properties of these five networks. All these networks have intertwined clusters.

TABLE I.

Real networks. For each network, we report the number of nodes N, the number of edges S, and the minimum of the negative of the eigenvalues $μ_{min}^{R}$ (for $δ = 0$ .) All networks are undirected and unweighted.

Type	Name	N	S	$μ_{min}^{R}$	No. of non-trivial clusters
Power grid 1	case16ci	16	16	−1.93	8
Power grid 2	case85	85	84	−1.62	10
Neural network	Backward circuit	29	59	−1	7
Brain network	Macaque-rhesus-brain-2	91	582	0	13
Twitter network	rt-retweet	96	117	0	11

Open in a separate window

Each panel of Fig. 7 corresponds to one of the five real networks and shows the lower and upper bounds, $σ_{min}^{k}$ and $σ_{max}^{k}$ , vs the cluster index $k$ , after setting $δ$ such that for all these networks $μ_{min}^{R} = 0.1$ . We see that for all the networks (except for power grid 1 and power grid 2), there is at least a pair of blocks that are related by partially disjoint CS. Clusters in power grid 1 are all intertwined, and the blocks of the power grid 2 network are related by Matryoshka CS. Further analysis of the cluster synchronizability of these networks is provided in Sec. VII in the supplementary material, where the effect of varying $δ$ is investigated.

An external file that holds a picture, illustration, etc.
Object name is CHAOEH-000032-041101_1-g007.jpg

Open in a separate window

FIG. 7.

Upper and lower bounds $σ_{max}$ and $σ_{min}$ vs the cluster index for the five real networks in Table I. We set $δ$ such that $μ_{min}^{R}$ is the same and equal to $0.1$ for all the networks. Cluster indices refer to non-trivial clusters and are in the order of increasing $σ_{min}^{k}$ , $k = 1, \dots, \tilde{K}$ . Each panel shows a different network: (a) power grid 1, (b) power grid 2, (c) neural network, (d) brain network, and (e) Twitter network.

V. CONCLUSION

In this paper, we have attempted to generalize the concept of synchronizability originally introduced for complete synchronization in Ref. ³ to the case of cluster synchronization. By synchronizability, we mean the range of the coupling strength $σ$ over which each cluster synchronizes. We have found that the case of cluster synchronization is by far more complex than the case of complete synchronization. We first studied cluster synchronization in networks with no intertwined clusters and considered the following two problems: (i) introducing a definition of synchronizability for each cluster and (ii) introducing a definition of synchronizability for the entire network. For problem (i), we were able to derive a dynamics-independent metric of synchronizability in terms of the Cluster Master Stability Function (CMSF), which provides an accurate prediction for how synchronizable each cluster is. For problem (ii), we could not identify a single index of cluster synchronizability as we saw in both the bounded case and the unbounded case that this requires considerations that generally depend on both the network structure and the dynamics. The proposed definition of cluster synchronizability set (Definition 11) characterizes the synchronizability of a network in terms of $\tilde{K}$ different numbers (where $\tilde{K}$ is the number of nontrivial clusters), but we were not able to come up with a straightforward way of comparing two or more networks in terms of their respective sets. This motivated us to introduce and characterize three different types of cluster synchronization: Matryoshka CS, partially disjoint CS, and complete disjoint CS. Of these, to the best of our knowledge, only cases of Matryoshka synchronization had been previously reported (see Fig. 3 from Ref. ³⁶). However, a study of several real networks from the literature shows that partially disjoint CS is common in these networks.

Finally, we also studied the general case of networks with intertwined clusters and numerically computed the cluster synchronizability ratio for several real networks from the literature. Our work can be extended to the case of CS in multilayer networks.¹⁵

SUPPLEMENTARY MATERIAL

The supplementary material includes further clarifications on the stability analysis of the synchronous solution for the cases of complete synchronization and cluster synchronization, an alternative formulation of the equations describing the network dynamics corresponding to the case $δ < 0$ , a discussion about the connection between the case of complete synchronization and cluster synchronization, additional information about intertwined clusters, and the canonical transformation that decouples the parallel perturbations from the transverse perturbations, an alternative formulation for the synchronizability of a network, and an analysis of the synchronizability of several real networks as a function of the parameter $δ$ .

ACKNOWLEDGMENTS

This work was supported by the NIH (Grant No. 1R21EB028489-01A1) and the NIBIB and the NIMH through the NIH BRAIN Initiative Grant $#$ R01 EB028157, and NSF DMR-1945909.

AUTHOR DECLARATIONS

Conflicts of Interest

The authors have no conflicts to disclose.

DATA AVAILABILITY

The data that support the findings of this study are available within the article.

REFERENCES

1. Alon U., An Introduction to Systems Biology: Design Principles of Biological Circuits (CRC Press, 2019). [Google Scholar]

2. Amunts K., Lepage C., Borgeat L., Mohlberg H., Dickscheid T., Bazin P.-L., Lewis L. B., Oros-Peusquens A.-M., Shah N. J., Lippert T., Zilles K., and Evans A. C., “Bigbrain: An ultrahigh-resolution 3D human brain model,” Science 340, 1472–1475 (2013). 10.1126/science.1235381 [PubMed] [CrossRef] [Google Scholar]

3. Barahona M. and Pecora L. M., “Synchronization in small-world systems,” Phys. Rev. Lett. 89, 054101 (2002). 10.1103/PhysRevLett.89.054101 [PubMed] [CrossRef] [Google Scholar]

4. Belykh I., Belykh V., Nevidin K., and Hasler M., “Persistent clusters in lattices of coupled nonidentical chaotic systems,” Chaos 13, 165–178 (2003). 10.1063/1.1514202 [PubMed] [CrossRef] [Google Scholar]

5. Belykh I. and Hasler M., “Mesoscale and clusters of synchrony in networks of bursting neurons,” Chaos 21, 016106 (2011). 10.1063/1.3563581 [PubMed] [CrossRef] [Google Scholar]

6. Belykh V. N., Belykh I. V., and Hasler M., “Hierarchy and stability of partially synchronous oscillations of diffusively coupled dynamical systems,” Phys. Rev. E 62, 6332–6345 (2000). 10.1103/PhysRevE.62.6332 [PubMed] [CrossRef] [Google Scholar]

7. Belykh V. N., Belykh I. V., Hasler M., and Nevidin K. V., “Cluster synchronization in three-dimensional lattices of diffusively coupled oscillators,” Int. J. Bifurcation Chaos 13, 755–779 (2011). 10.1142/S0218127403006923 [CrossRef] [Google Scholar]

8. Belykh V. N., Osipov G. V., Petrov V. S., Suykens J. A., and Vandewalle J., “Cluster synchronization in oscillatory networks,” Chaos 18, 037106 (2008). 10.1063/1.2956986 [PubMed] [CrossRef] [Google Scholar]

9. Chavez M., Huang D., Amann A., Hentschel H., and Boccaletti S., “Synchronization is enhanced in weighted complex networks,” Phys. Rev. Lett. 94, 218701 (2005). 10.1103/PhysRevLett.94.218701 [PubMed] [CrossRef] [Google Scholar]

10. Cho Y. S., Nishikawa T., and Motter A. E., “Stable chimeras and independently synchronizable clusters,” Phys. Rev. Lett. 119, 084101 (2017). 10.1103/PhysRevLett.119.084101 [PubMed] [CrossRef] [Google Scholar]

11. Chung F. R., Spectral Graph Theory (American Mathematical Society, 1997), Vol. 92. [Google Scholar]

12. Civanlar S., Grainger J., Yin H., and Lee S., “Distribution feeder reconfiguration for loss reduction,” IEEE Trans. Power Delivery 3, 1217–1223 (1988). 10.1109/61.193906 [CrossRef] [Google Scholar]

13. Dahms T., Lehnert J., and Schöll E., “Cluster and group synchronization in delay-coupled networks,” Phys. Rev. E 86, 016202 (2012). 10.1103/PhysRevE.86.016202 [PubMed] [CrossRef] [Google Scholar]

14. Das D., Kothari D., and Kalam A., “Simple and efficient method for load flow solution of radial distribution networks,” Int. J. Electr. Power Energy Syst. 17, 335–346 (1995). 10.1016/0142-0615(95)00050-0 [CrossRef] [Google Scholar]

15. Della Rossa F., Pecora L., Blaha K., Shirin A., Klickstein I., and Sorrentino F., “Symmetries and cluster synchronization in multilayer networks,” Nat. Commun. 11, 1–17 (2020). 10.1038/s41467-019-13993-7 [PMC free article] [PubMed] [CrossRef] [Google Scholar]

16. Fiedler M., “Algebraic connectivity of graphs,” Czech. Math. J. 23, 298–305 (1973). 10.21136/CMJ.1973.101168 [CrossRef] [Google Scholar]

17. Fu C., Lin W., Huang L., and Wang X., “Synchronization transition in networked chaotic oscillators: The viewpoint from partial synchronization,” Phys. Rev. E 89, 052908 (2014). 10.1103/PhysRevE.89.052908 [PubMed] [CrossRef] [Google Scholar]

18. Golubitsky M. and Stewart I., “Nonlinear dynamics of networks: The groupoid formalism,” Bull. Am. Math. Soc. 43, 305–365 (2006). 10.1090/S0273-0979-06-01108-6 [CrossRef] [Google Scholar]

19. Huang L., Chen Q., Lai Y.-C., and Pecora L. M., “Generic behavior of master-stability functions in coupled nonlinear dynamical systems,” Phys. Rev. E 80, 036204 (2009). 10.1103/PhysRevE.80.036204 [PubMed] [CrossRef] [Google Scholar]

20. Hwang D., Chavez M., Amann A., and Boccaletti S., “Synchronization in complex networks with age ordering,” Phys. Rev. Lett. 94, 138701 (2005). 10.1103/PhysRevLett.94.138701 [PubMed] [CrossRef] [Google Scholar]

21. Kamei H. and Cock P. J., “Computation of balanced equivalence relations and their lattice for a coupled cell network,” SIAM J. Appl. Dyn. Syst. 12, 352–382 (2013). 10.1137/100819795 [CrossRef] [Google Scholar]

22. Kaneko K., “Clustering, coding, switching, hierarchical ordering, and control in a network of chaotic elements,” Physica D 41, 137–172 (1990). 10.1016/0167-2789(90)90119-A [CrossRef] [Google Scholar]

23. Kanter I., Kopelowitz E., Vardi R., Zigzag M., Kinzel W., Abeles M., and Cohen D., “Nonlocal mechanism for cluster synchronization in neural circuits,” Europhys. Lett. 93, 66001 (2011). 10.1209/0295-5075/93/66001 [CrossRef] [Google Scholar]

24. Leifer I., Phillips D., Sorrentino F., and Makse H. A., “Symmetry-driven link prediction in networks through pseudobalanced coloring optimization,” arXiv:2111.07821 (2021).

25. Leifer I., Sánchez-Pérez M., Ishida C., and Makse H. A., “Predicting synchronized gene coexpression patterns from fibration symmetries in gene regulatory networks in bacteria,” BMC Bioinf. 22, 389 (2021). 10.1186/s12859-021-04213-5 [PMC free article] [PubMed] [CrossRef] [Google Scholar]

26. Merris R., “Laplacian matrices of graphs: A survey,” Linear Algebra Appl. 197-198, 143–176 (1994). 10.1016/0024-3795(94)90486-3 [CrossRef] [Google Scholar]

27. Milo R., Shen-Orr S., Itzkovitz S., Kashtan N., Chklovskii D., and Alon U., “Network motifs: Simple building blocks of complex networks,” Science 298, 824–827 (2002). 10.1126/science.298.5594.824 [PubMed] [CrossRef] [Google Scholar]

28. Mohar B., “Laplace eigenvalues of graphs—A survey,” Discrete Math. 109, 171–183 (1992). 10.1016/0012-365X(92)90288-Q [CrossRef] [Google Scholar]

29. Morone F., Leifer I., and Makse H. A., “Fibration symmetries uncover the building blocks of biological networks,” Proc. Natl. Acad. Sci. U.S.A. 117, 8306–8314 (2020). 10.1073/pnas.1914628117 [PMC free article] [PubMed] [CrossRef] [Google Scholar]

30. Morone F. and Makse H. A., “Symmetry group factorization reveals the structure-function relation in the neural connectome of Caenorhabditis elegans,” Nat. Commun. 10, 1–13 (2019). 10.1038/s41467-019-12675-8 [PMC free article] [PubMed] [CrossRef] [Google Scholar]

31. Nicosia V., Valencia M., Chavez M., Díaz-Guilera A., and Latora V., “Remote synchronization reveals network symmetries and functional modules,” Phys. Rev. Lett. 110, 5233 (2013). 10.1103/PhysRevLett.110.174102 [PubMed] [CrossRef] [Google Scholar]

32. Nishikawa T., Motter A., Lai Y., and Hoppensteadt F., “Heterogeneity in oscillator networks: Are smaller worlds easier to synchronize?,” Phys. Rev. Lett. 91, 014101 (2003). 10.1103/PhysRevLett.91.014101 [PubMed] [CrossRef] [Google Scholar]

33. Panahi S., Klickstein I., and Sorrentino F., “Cluster synchronization of networks via a canonical transformation for simultaneous block diagonalization of matrices,” Chaos 31, 111102 (2021). 10.1063/5.0071154 [PubMed] [CrossRef] [Google Scholar]

34. Panahi S. and Sorrentino F., “Group synchrony, parameter mismatches, and intragroup connections,” Phys. Rev. E 104, 054314 (2021). 10.1103/PhysRevE.104.054314 [PubMed] [CrossRef] [Google Scholar]

35. Pecora L. and Carroll T., “Master stability functions for synchronized coupled systems,” Phys. Rev. Lett. 80, 2109–2112 (1998). 10.1103/PhysRevLett.80.2109 [CrossRef] [Google Scholar]

36. Pecora L. M., Sorrentino F., Hagerstrom A. M., Murphy T. E., and Roy R., “Cluster synchronization and isolated desynchronization in complex networks with symmetries,” Nat. Commun. 5, 1–8 (2014). 10.1038/ncomms5079 [PubMed] [CrossRef] [Google Scholar]

37. Purcell O., Savery N. J., Grierson C. S., and Di Bernardo M., “A comparative analysis of synthetic genetic oscillators,” J. R. Soc. Interface 7, 1503–1524 (2010). 10.1098/rsif.2010.0183 [PMC free article] [PubMed] [CrossRef] [Google Scholar]

38. Rosin D. P., Rontani D., Gauthier D. J., and Schöll E., “Control of synchronization patterns in neural-like Boolean networks,” Phys. Rev. Lett. 110, 104102 (2013). 10.1103/PhysRevLett.110.104102 [PubMed] [CrossRef] [Google Scholar]

39. Rossi R. A. and Ahmed N. K., “The network data repository with interactive graph analytics and visualization,” in AAAI (AAAI, 2015); available at https://networkrepository.com.

40. Rossi R. A., Gleich D. F., Gebremedhin A. H., and Patwary M. A., “What if clique were fast? Maximum cliques in information networks and strong components in temporal networks,” arXiv:1210.5802 (2012), pp. 1–11.

41. Schaub M. T., O’Clery N., Billeh Y. N., Delvenne J. -C., Lambiotte R., and Barahona M., “Graph partitions and cluster synchronization in networks of oscillators,” Chaos 26, 094821 (2016). 10.1063/1.4961065 [PMC free article] [PubMed] [CrossRef] [Google Scholar]

42. Shen-Orr S. S., Milo R., Mangan S., and Alon U., “Network motifs in the transcriptional regulation network of Escherichia coli,” Nat. Genet. 31, 64–68 (2002). 10.1038/ng881 [PubMed] [CrossRef] [Google Scholar]

43. Siddique A. B., Pecora L., Hart J. D., and Sorrentino F., “Symmetry-and input-cluster synchronization in networks,” Phys. Rev. E 97, 042217 (2018). 10.1103/PhysRevE.97.042217 [PubMed] [CrossRef] [Google Scholar]

44. Sorrentino F., Di Bernardo M., and Garofalo F., “Synchronizability and synchronization dynamics of weighed and unweighed scale free networks with degree mixing,” Int. J. Bifurcation Chaos 17, 2419–2434 (2011). 10.1142/S021812740701849X [CrossRef] [Google Scholar]

45. Sorrentino F. and Ott E., “Network synchronization of groups,” Phys. Rev. E 76, 056114 (2007). 10.1103/PhysRevE.76.056114 [PubMed] [CrossRef] [Google Scholar]

46. Sorrentino F. and Pecora L., “Approximate cluster synchronization in networks with symmetries and parameter mismatches,” Chaos 26, 094823 (2016). 10.1063/1.4961967 [PubMed] [CrossRef] [Google Scholar]

47. Sorrentino F., Pecora L. M., Hagerstrom A. M., Murphy T. E., and Roy R., “Complete characterization of stability of cluster synchronization in complex dynamical networks,” Sci. Adv. 2, 191 (2016). 10.1126/sciadv.1501737 [PMC free article] [PubMed] [CrossRef] [Google Scholar]

48. Williams C. R., Murphy T. E., Roy R., Sorrentino F., Dahms T., and Schöll E., “Experimental observations of group synchrony in a system of chaotic optoelectronic oscillators,” Phys. Rev. Lett. 110, 064104 (2013). 10.1103/PhysRevLett.110.064104 [PubMed] [CrossRef] [Google Scholar]

49. Zhang Y. and Motter A. E., “Symmetry-independent stability analysis of synchronization patterns,” SIAM Rev. 62, 817–836 (2020). 10.1137/19M127358X [CrossRef] [Google Scholar]

50. Zimmerman R. D., Murillo-Sanchez C. E., and Thomas R. J., “MATPOWER: Steady-state operations, planning, and analysis tools for power systems research and education,” IEEE Trans. Power Syst. 26, 12–19 (2011). 10.1109/TPWRS.2010.2051168 [CrossRef] [Google Scholar]

Articles from Chaos are provided here courtesy of American Institute of Physics

Matryoshka and disjoint cluster synchronization of networks

Amirhossein Nazerian

Shirin Panahi

Ian Leifer

David Phillips

Hernán A. Makse

Francesco Sorrentino

Associated Data

Abstract

I. INTRODUCTION

II. THE CASE OF COMPLETE SYNCHRONIZATION

(Network synchronizability for the case that the σ-interval is bounded) —

(Network synchronizability for the case that the σ-interval is unbounded) —

III. THE CASE OF CLUSTER SYNCHRONIZATION

(Equitable clusters (balanced coloring)) —

(Minimum balanced coloring) —

(Isolated cluster synchronization) —

IV. CLUSTER SYNCHRONIZABILITY

A. Networks with no intertwined clusters

(Stability of the synchronous state of each cluster) —

(Cluster master stability function) —

(Synchronizability of each cluster) —

1. Numerical example

2. Conditions for cluster synchronization

(Condition for cluster synchronization of the network (bounded case)) —

(The network cluster synchronizability ratio—bounded case) —

(Cluster synchronizability set) —

3. Numerical analysis

B. Networks with intertwined clusters

(Intertwined clusters) —

C. Real networks analysis

TABLE I.

V. CONCLUSION

SUPPLEMENTARY MATERIAL

ACKNOWLEDGMENTS

AUTHOR DECLARATIONS

Conflicts of Interest

DATA AVAILABILITY

REFERENCES

(Network synchronizability for the case that the $σ$ -interval is bounded) —

(Network synchronizability for the case that the $σ$ -interval is unbounded) —