Learn more: PMC Disclaimer | PMC Copyright Notice
Matryoshka and disjoint cluster synchronization of networks
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. 8, 13, 17, 23, 31, 34, 38, 41, 45, and 48). 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. Kaneko22 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 undirected30 and directed25,29 biological networks.18 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,5 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:
for , where is the state of node , describes the dynamics of each individual uncoupled system, the function describes how two systems interact with one another and is a positive scalar parameter that measures the strength of the coupling. The symmetric Laplacian matrix is defined as where the symmetric adjacency matrix describes the network connectivity, i.e., ( ) if node is (not) connected to node and vice versa, and the diagonal matrix has diagonal entries that are equal to the degree of each node, . The Laplacian matrix is negative semidefinite (see Sec. I in the supplementary material). Also, since has sum over its rows equaling zero, the eigenvalues of are .11,16 The Laplacian eigenvalue is known as the algebraic connectivity and is strictly negative for connected networks.16,26,28
Based on the functions and , 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.
(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,
The larger the eigenratio , the more synchronizable the network.
Based on this definition, the best possible synchronizability is obtained for , i.e., all equal eigenvalues except for . We note that the original eigenratio introduced in Ref. 3 is equal to (the smaller this other eigenratio, the more synchronizable the network).
(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 of the network Laplacian,
The larger the , the more synchronizable the network.
Based on the choice of the functions and , 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. 3, 9, 20, 32, and 44).
III. THE CASE OF CLUSTER SYNCHRONIZATION
Consider a network with dynamical equations,
where . The symmetric matrix is the shifted version of the symmetric adjacency matrix , where is the -dimensional identity matrix, and the scalar . Since the rows of the matrix 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 from Eq. (4) describes the network topology. This network can also be represented as a set of nodes, , where the dynamical state of the node is given by in Eq. (4).
(Equitable clusters (balanced coloring)) —
Consider the network defined by the shifted adjacency matrix, . The set of the network nodes can be partitioned into subsets of nodes called equitable clusters, , , for , where
The number of nodes in cluster is , A partition of the set of the network nodes into equitable clusters is also called a balanced coloring.
(Minimum balanced coloring) —
A minimum balanced coloring is a partition of the set of the network nodes into equitable clusters with the minimum number of clusters. A fast algorithm for computing the network minimum balanced coloring from knowledge of the matrix was proposed in Ref. 5.
A trivial (non-trivial) cluster is one with only one node (more than one node) in it. We call the number of nontrivial clusters. Without loss of generality, we order the clusters such that the first clusters are nontrivial and the remaining 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 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,27 and has been associated with a better dynamical response of these networks.37 It has been reported that these autoregulation loops are common motifs observed in biological networks1,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. 10, 36, 43, 47, and 49). 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 such that , , .18 The set of equalities , defines the invariant CS manifold. By setting , Eq. (4) can be rewritten as
, where the -dimensional quotient matrix satisfies
and the -dimensional indicator matrix is such that if node belongs to cluster and otherwise, . indicates the Moore–Penrose inverse of the matrix .
There can be multiple sets of equitable clusters associated with a given adjacency matrix (see, e.g., Ref. 21). 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).47 The study of the stability of the corresponding CS solutions can be performed using the approaches of Refs. 6, 4, 7, 47, 43, 49, and 34. 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 , which excludes the cases corresponding to complete synchronization and 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 , there is always at least one non-trivial cluster whose stability can be studied.
We can assess CS stability36 by studying small perturbations about the cluster synchronous solution , where indicates the synchronous solution of the cluster to which node belongs [the superscript is used to emphasize that the cluster synchronous solution depends on through Eq. (6)],
.
The concept of isolated CS, originally introduced in Ref. 36, indicates that the range of a given parameter that synchronizes each cluster may be different for different clusters.
(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. 36. 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 ,33,36 the coupling matrix can be decomposed as follows:
where the symbol indicates the direct sum of matrices, the “parallel” matrix is -dimensional, and the “transverse” matrix is -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 are the “transverse eigenvalues” of . One can immediately see that the set of the eigenvalues of the matrix is partitioned into the two sets: the set of the eigenvalues of the matrix and the set of the transverse eigenvalues of the matrix , .
The set of transverse eigenvalues, , can be further partitioned into subsets, , , where each subset corresponds to one non-trivial cluster33,46 (for more details, see Sec. V in the supplementary material). The subset contains eigenvalues , where is the number of nodes in cluster , and . Since here we are only concerned with the transverse eigenvalues, we omit the superscript and indicate the th transverse eigenvalue for cluster with the notation , i.e., , , and . We also label . Then, and for each cluster , . 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 and those transverse to the synchronization manifold. Only the transverse perturbations determine stability about the cluster synchronous solution. Following Ref. 46, the dynamics of the transverse perturbations can be written as
, where in Eq. (10), we use the negative of the eigenvalues for convenience. indicates the synchronous solution corresponding to and . Based on our assumption A1, which we introduce below, all and so all . The discussion that follows could use either the eigenvalues or the negative of the eigenvalues . We opt for the as in general we find easier to refer to positive quantities.
(Stability of the synchronous state of each cluster) —
The synchronous state of each non-trivial cluster is stable if the maximum Lyapunov exponent (MLE) associated with Eq. (10) is negative for all , i.e., if , where the first argument is used to indicate the dependence on the cluster synchronous solution (which depends on ) and the second argument is used to indicate the dependence on the products times .
The fact that depends on through both its arguments is in contrast to the case of complete synchronization for which the synchronous solution does not depend on .35
(Cluster master stability function) —
We define the cluster master stability function (CMSF) , which returns the MLE associated with Eq. (10), for the cluster synchronous solution as a function of the parameters and , where and can vary independently of one another.
Note that the cluster master stability function depends on through both the cluster synchronous solution (superscript ) and the argument .
The condition for stability of cluster k is that
In what follows, we proceed under the following three assumptions:
- A1:The eigenvalues of the matrix 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., for , where (equivalently, , with and ) or in an unbounded range of its argument, i.e., for , where (equivalently, , with ). 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 and vary smoothly with .
We can then introduce the following definitions for the synchronizability of each cluster:
(Synchronizability of each cluster) —
In the bounded case, the synchronizability of cluster is equal to the eigenratio , and in the unbounded case, it is equal to .
The definitions of synchronizability of cluster are consistent with the observation that given and , increasing ( ) 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.
Schematic representation of the synchronizability of cluster for the bounded case. The master stability function for . The figure shows the lines and , going through the maximum and minimum eigenvalue, and at (there can be other eigenvalues in between). The lines intersect the curves and twice. However, is determined by the intersection of with and is determined by the intersection of with . The critical coupling strengths, and , determine the width of the -interval over which the synchronous solution is stable.
Figure 1 shows how the eigenratio relates to the width of the -interval in which cluster synchronizes. The cluster master stability function for , where and are two arbitrary functions of . The figure shows the lines and , intersecting the functions and twice. However, independent of the particular shapes of the functions and , is determined by the intersection of the line with and is determined by the intersection of the line with . The critical coupling strengths, and , determine the range of over which the synchronous solution for cluster is stable. We can then write , where the first ratio represents the effect of the network topology and the second ratio represents the effect of the dynamics, in terms of the functions and . As the ratio increases, i.e., as the eigenvalues move closer to one another, the synchronizability of cluster increases. Changing the functions and only moves the functions and (and not the lines ). Changing the network topology affects the lines but also, through the dynamics of the quotient network, the functions and . Our main result is that even if these two functions change as a result of changing the network topology, the intersections with the lines always occur for and .
1. Numerical example
As a reference example, we consider the network with nodes and clusters in Fig. 2. This network consists of two circles, each one corresponding to a cluster: the larger cluster, , has nodes, where each node is connected to its six nearest neighbors, with coupling weight . The smaller cluster, , is a fully connected circle with nodes and coupling weight . Each node in one circle is coupled to all the nodes in the other circle and vice versa, with coupling weight . The shifted adjacency matrix, is
![An external file that holds a picture, illustration, etc.
Object name is CHAOEH-000032-041101_1-g0d1.jpg](https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8983070/bin/CHAOEH-000032-041101_1-g0d1.jpg)
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 is integrated for a long time so that it converges on its attractor. Then, a randomly selected point from the attractor of 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, , , 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 .
15-node undirected and weighted network. The adjacency matrix of this network, , is shown in Eq. (12). Clusters are shown in different colors: green nodes (1–10) are in the first cluster, and blue nodes (11–15) are in the second cluster, . Green, blue, red, and black edges have weights , , , and , respectively.
We select the individual uncoupled systems to be Rössler’s oscillators with , , ,
We set and , which corresponds to chaotic dynamics of the Rössler oscillator. We set as in Eq. (12) and we set , , , and . The transverse eigenvalues for the two clusters are and . Our choice of the functions and 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, , is calculated as
where is the average time evolution of the states of the nodes in , and indicates an average over the time interval . Here, we take . Figure 3 is a plot for synchronization error 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 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.
Blue and red curves represent the synchronization errors and for clusters and , respectively. The synchronous interval for is , and for , it is .
CMSF plots for clusters (a) and (b) (see Definition 7). Following the method described in Fig. 1, the lines connecting the origin to the eigenvalues and are plotted in dashed white lines and the intersections are found with the black contour, and , to find and . For better visualization, the bottom left corner of each plot is magnified in the insets to show and . 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 an interval of , 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.36
(Condition for cluster synchronization of the network (bounded case)) —
A network can be cluster-synchronized if there exists a value of such that,
Note that Definition 9 corresponds to all nontrivial cluster synchronizing. Now, let
where and indicate the critical clusters and 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, , . In the case of bounded MSF, as we decrease (increase) this , there will be one critical cluster ( ) whose nodes are the first to desynchronize. In general, and can either be the same ( ) or different ( ). In either case, we can rewrite Eq. (15) as
(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,
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:
(Cluster synchronizability set) —
The cluster synchronizability set of a network is the set of the synchronizabilities of all nontrivial clusters (see Definition 8), i.e.,
where denotes the specific case of the CMSF for each cluster , i.e., in the bounded case, , and in the unbounded case, , .
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 , , 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 , is completely contained in the -interval of cluster ,If the nodes in cluster synchronize, the nodes in cluster synchronize as well, but the reverse implication is not true.(20)
- (b)Partially disjoint cluster synchronization, which occurs when the intersection of the synchronous -intervals of clusters and 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,(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 , , and ,
In order to assess the stability of the synchronous solution , we define
which returns the maximum of the MLEs associated with Eq. (10) over the transverse eigenvalues of the cluster as a function of , . ( ) indicates that the nodes in are (not) synchronized to with coupling strength .
- (a)By setting the network parameters to , , , , we obtain a case of Matryoshka synchronization. The transverse eigenvalues for the two clusters are and . The upper part of Fig. 5(a) is a plot of the synchronization error [defined in Eq. (14)] for cluster (in blue) and for cluster (in red). The lower part of the figure shows and as defined in Eq. (23). The -interval for the network synchronization is . The lower bound and the upper bound are determined by . Therefore, the synchronizability of each cluster is and .
Isolated CS: Matryoshka, partially, and complete disjoint CS. The upper plot of each panel shows the CS error vs , while the lower plot shows , computed as defined in Eq. (23), vs . Blue and red curves represent the synchronization errors and for the clusters and , respectively. (a) shows the synchronous interval of cluster , which is contained in the synchronous interval of cluster , which is Matryoshka synchronization. The synchronous interval for is , and for , it is . (b) shows a synchronous interval in the case that the lower bound is from and the upper bound is from , which is partially disjoint synchronization. The synchronous interval for is , and for , it is . (c) shows that there is no synchronous that synchronizes both clusters at the same time, which is complete disjoint synchronization. The synchronous interval for is , and for , it is .
- (b)Now consider the same network with parameters, , , , and . Then, the transverse eigenvalues for each cluster are and . 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 for cluster (in blue) and for cluster (in red). The lower part of the figure shows and . The interval for network synchronization is . The lower bound and the upper bound are determined from the first and second clusters, respectively. Therefore, the synchronizabilities of each cluster are , and .
- (c)Finally, we consider the network parameters , , , and . Then, the transverse eigenvalues of each cluster are and . 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 for each cluster as a function of . The lower part of the figure shows and .
Figure 6 shows the synchronizability (Definition 8) vs for the dynamical network described by Eqs. (4) and (22) with adjacency matrix from Eq. (12). The coupling weight of the first cluster, , is varied from 0.1 to 7, while the other network parameters , and are kept constant. For increasing values of from 0.1, we first see partially disjoint CS, then Matryoshka CS, then, partially disjoint CS again. The synchronizability of cluster is shown to decrease in each one of the intervals. We also plot the numerically computed synchronizability ratio and find very good agreement with . The synchronizability of the second cluster is a constant as is varied since the transverse eigenvalues of the second cluster are independent from . We note that Figs. 5(a) and 5(b) correspond to choosing and shown in Fig. 6, respectively.
Synchronizability measures and the normalized synchronizability ratio vs , the coupling weight of the first cluster, while the other parameters of the network, , and , are kept constant. We integrate the dynamics equation (4) with functions from Eq. (22) and the network from Eq. (12). We see that as is varied, the type of synchronization changes. For , we see partially disjoint CS where the lower and upper bounds of are determined by and , respectively. For , we see Matryoshka CS where is the critical cluster. Finally, for , we see partially disjoint CS again where the lower and upper bounds of are now determined by and , 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.
(Intertwined clusters) —
Suppose is a clustering of nodes so that the clusters form a balanced coloring (see Definition 3) with at least clusters and let be two distinct clusters. We say that and are intertwined if there are partitions of and of so that , , and the following conditions are satisfied.
- 1.The sets and are not balanced colorings.
- 2.The set 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.
For more discussion about intertwined clusters, see Sec. IV in the supplementary material.
We define the -dimensional diagonal indicator matrices , , such that if node belongs to the cluster , and otherwise.
The stability of the CS solution depends on the dynamics of small perturbations around the synchronous solution, . The dynamics of the vector obeys
By using a proper transformation matrix, ,33,36,49 the shifted adjacency matrix, , is still decomposed into the form of Eq. (9), where the “parallel” matrix is -dimensional, and the “transverse” matrix is -dimensional. The matrix decouples the matrix into finest blocks,33,36,49 which results in the following block-diagonal structure for the transverse matrix :
where is the total number of blocks in and .
We will analyze the stability of the synchronous solution in terms of the dynamics of the transverse perturbations. After applying the transformation , we can rewrite Eq. (24) as
where , and , . The perturbations can be divided into the stack of vectors , where corresponds to the transverse perturbation equations for each block of . For each block , , there is an interval of in which . As a result, the network can synchronize if
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 . 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. 30 and was manually repaired in Ref. 24. 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.40 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 (for .) All networks are undirected and unweighted.
Type | Name | N | S | 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 |
Each panel of Fig. 7 corresponds to one of the five real networks and shows the lower and upper bounds, and , vs the cluster index , after setting such that for all these networks . 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.
Upper and lower bounds and vs the cluster index for the five real networks in Table I. We set such that is the same and equal to for all the networks. Cluster indices refer to non-trivial clusters and are in the order of increasing , . 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. 3 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 different numbers (where 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. 36). 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.15
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 , 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.