Rewiring hierarchical scale-free networks: Influence on synchronizability and topology

Complex systems involving large collections of dynamical elements interacting with each other on complex networks are abundant across several disciplines of sciences and engineering [1]. This has generated a consolidated effort towards unveiling structural properties of manifold real-world networked systems and uncovering fundamental principles governing their organization. A significant milestone amid such explorations was the exposition of the small-world behaviour of diverse real networks, characterized by a small average path length between nodes and a high clustering coefficient [2]. Further, the interplay between topological properties of complex networked systems and the collective dynamics exhibited by them has been simultaneously investigated, particularly with reference to the phenomenon of synchronization [1,3,4].

Synchronization is among the most relevant emergent behaviours in complex networks of dynamical systems and is often critical to their functionality [3–9]. As a result, there has been a persistent drive towards unravelling the influence of topological features of networks on their ability to synchronize, often with the objective of designing topologies for better synchronizability [10–19]. In this regard, small-world networks have been particularly known to facilitate synchronization of dynamical systems coupled on them [20–23]. Besides the small-world property, real-world networks often exhibit two other remarkable generic features, namely, scale-free behaviour [24] and hierarchical structure [25,26].

Scale-free behaviour is characterized by the probability P (k) that a randomly selected node has exactly k links decaying as a power law $(P(k) \sim k^{- \gamma})$ and appears in good approximation in diverse real networked systems such as the internet [27], the world wide web [24], networks of metabolic reactions [28], protein interaction networks [29], the web of Hollywood actors linked by movies [30], social networks such as the web of human sexual contacts [31], etc. In this context, the Barabási-Albert (BA) model [24] has been suggested for realizing random scale-free networks with growth and preferential attachment, where an incoming node is more likely to get randomly linked to an existing node with higher connectivity.

Also, manifold real-world systems such as metabolic networks in the cell [25], ecological niches in food webs [26], the scientific collaboration network [32], corporate and governmental organizations [33], etc. exhibit hierarchical organization where small groups of nodes organize in a stratified manner into larger groups, over multiple scales. This definition of hierarchical structure, also used throughout this letter, relates to that proposed by Clauset et al. [26].

Naturally, collective dynamics on scale-free [34–36] and hierarchical topologies [8,9,37–40] have been investigated intensively, but mostly separately, leaving sufficient room for further explorations concerning synchronization in networks simultaneously exhibiting the two topological properties mentioned above. Notably, the coexistence of the generic feature of scale-free topology along with a hierarchical organization in many networks in nature and society is immensely intriguing [41]. Examples in this direction constitute the internet at the domain level, the world wide web of documents, the actor network, the semantic web viewed as a network of words, biochemical networks in the cell, etc. [25,41].

Network construction

Notable instances among models simultaneously incorporating the prominent topological features of scale-free behaviour and hierarchical organization under one roof are the deterministic scale-free (DSF) [42], pseudofractal scale-free (PSF) [43], Apollonian [44] and the hierarchical network model [41]. We specifically study DSF and PSF networks in this letter, the topology of them developed over 2 generations is illustrated in fig. 1(a), (b). Evidently, these models are completely deterministic, leading to a perfectly hierarchical assembly of the associated networks. However, it is most natural to assume that real-world topologies are neither completely deterministic, nor perfectly hierarchical. Thus, a realistic model of practical networked systems should feature an aspect of randomness, besides simultaneously manifesting not far from scale-free and hierarchical design. Henceforth, as a preliminary solution to this problem, we suggest in the following perfectly hierarchical networks (generated by the deterministic rules of the aforementioned models) with randomly rewired links as better representatives of associated connected architectures in the real-world. The mechanism used throughout this letter for rewiring edges, while preserving the (scale-free) degree distribution of the otherwise perfectly hierarchical networks, is illustrated in fig. 2.

Zoom In Zoom Out Reset image size

Zoom In Zoom Out Reset image size

The desired operational state in complex networks is often associated with the synchronized motion of its dynamical components [3]. In this work, we investigate the synchronizability of the proposed network models using the master stability function (MSF) framework [45]. We recall that real-world topologies exhibiting the small-world property are known to facilitate network synchronization [46,47] as well as to be more robust to random perturbations [47]. In this regard, the classical network model of Watts and Strogatz [2] is particularly notable for capturing the small-world property. In strong analogy with the present work, the Watts-Strogatz model generates graphs by randomly rewiring completely regular architectures (ring lattices), thus interpolating between absolutely regular and random graphs with the small-world property appearing for intermediate rewiring probability. However, MSF-based [45] measurements of synchronizability of the Watts-Strogatz model [2] surprisingly do not reveal exclusive features in the small-world regime [21]. In such networks, synchronizability is only enhanced for an initial increase of the number of rewired edges, which then saturates afterwards as further links are rewired. In fact, the synchronizabilities of the rewired networks (for a given number of rewired edges) are not much different from one another. On the other hand, networks resulting from rewiring hierarchical scale-free networks considered here exhibit both significantly enhanced as well as deteriorated synchronizability (compared to that of their completely deterministic counterparts).

In a related context, Donetti et al. [12] proposed entangled networks, constructed by starting with a random network of a certain size and rewiring it using a modified simulated annealing-based approach, while keeping its average degree fixed. In contrast, we start with the deterministic networks of DSF and PSF and rewire them using a different mechanism (fig. 2), where we instead maintain a fixed degree distribution. Further, the scheme of constructing entangled networks is aimed at achieving optimal synchronizability. However, we focus on exploring the synchronizability of an ensemble of rewired networks and, in turn, obtaining the "optimal" synchronizability of the representative network among the different members of this ensemble. Further, Donetti et al. found that the topological features of the average distance between nodes and betweenness centrality exhibit negative correlations with the synchronizability of entangled networks. Similarly, Dwivedi et al. [48] investigated the optimization of synchronizability in multiplex networks and demonstrated that a stronger interlayer connectivity as compared to the connections within each layer leads to better synchronizability. Moreover, they obtained results similar to those of Donetti et al. [12] where the latter have shown that entangled networks with more homogeneous degree distributions, distances between nodes and betweenness centrality distributions exhibit better synchronizability.

In the following, we briefly review the framework of MSF [45] and the traditional quantifier of synchronizability of a network, prior to its application to the aforementioned network models.

Consider a network of N identical oscillators where the isolated dynamics of the i-th oscillator is described by

$$\begin{equation} \dot{\mathbf{x}}^{i} = \mathbf{F} \left( \mathbf{x}^{i} \right);\quad \mathbf{x}^{i} \in \mathbb{R}^{d},\quad i = 1,\, 2,\, \ldots,\, N, \end{equation} \tag{ 1 }$$

and coupling is established via an output function ${\mathbf{H}:}\,\mathbb{R}^{d} \rightarrow\mathbb{R}^{d}$ (identical for all i). The topology of interactions is captured by the adjacency matrix A, where $A_{ij} = 1$ if nodes i and $j ( \neq i)$ are connected while $A_{ij} = 0$ otherwise. The dynamical equations of the networked system read

$$\begin{eqnarray} \dot{\mathbf{x}}^{i} & = \mathbf{F} \left( \mathbf{x}^{i} \right) + \epsilon \sum\limits_{j = 1}^{N} A_{ij} \left[ \mathbf{H} \left( \mathbf{x}^{j} \right) - \mathbf{H} \left( \mathbf{x}^{i} \right) \right]\nonumber\\ & = \mathbf{F} \left( \mathbf{x}^{i} \right) - \epsilon \sum\limits_{j = 1}^{N} L_{ij} \mathbf{H} \left( \mathbf{x}^{j} \right), \end{eqnarray} \tag{ 2 }$$

where represents the overall coupling strength and L is the graph Laplacian such that $L_{ij} = - A_{ij}$ if $i \neq j$ and $L_{ii} = \sum\nolimits_{j = 1}^{N} A_{ij} = k_{i}$ is the degree of node i. Since the Laplacian matrix L is symmetric, its eigenvalue spectrum $(\lambda_{1},\, \lambda_{2},\, \ldots,\, \lambda_{N})$ is real and ordered as $0 = \lambda_{1} < \lambda_{2} \le \ldots \le \lambda_{N}$, assuming the network is connected. Further, L has zero row sum by definition, guaranteeing the existence of a completely synchronized state, $\mathbf{x}^{1} (t) = \mathbf{x}^{2} (t) = \ldots = \mathbf{x}^{N} (t) = \mathbf{s} (t)$ as a solution of eq. (2). Starting from heterogeneous initial conditions, the oscillators (asymptotically) approach (and thus evolve on) the synchronization manifold $\mathbf{s} (t)$ corresponding to the solution of the uncoupled dynamics of the individual oscillators in eq. (1) $(\dot{\mathbf{s}} = \mathbf{F} (\mathbf{s}))$.

The local stability of the completely synchronized state determined by the framework of MSF [45] relates the synchronizability of a network to the eigenratio ${R \equiv \frac{\lambda_{N}}{\lambda_{2}}}$. Irrespective of F and H (eq. (2)), this condition has been extensively used to characterize the synchronizability of a network such that the lower the value of R, the more synchronizable the network and vice versa [4,10–19,23,44,46,49–51]. Note that the above condition applies to situations involving bounded MSFs, i.e., where the MSF exhibits negative values within a range of the normalized coupling parameter [4]. Also, finite $\lambda_{N}$ is related to the maximum degree of the network, while $\lambda_{2}$ relates to the connectivity [4]. Given that the degree distribution is preserved when rewiring the networks considered in this letter, one does not expect significant variations in $\lambda_{N}$.

We utilize the above framework in exploring the synchronizability of the aforementioned network models (fig. 1) after stochastically rewiring their edges. Further, we investigate the influence of rewiring on the topological properties of the resulting networks and, in turn, their relation to the synchronizability of the associated topologies. For that purpose, we refer the reader to the Supplementary Information Supplementarymaterial.pdf (SM) for a discussion of the topological properties of average path length $(\mathcal{L})$, maximum betweenness centrality (bc_max), average local clustering coefficient $(\mathcal{C}^{L})$, global clustering coefficient (transitivity, $\mathcal{C}^{G}$) and assortativity (r) of a network, to be studied in this letter.

We consider two paradigmatic network topologies simultaneously exhibiting scale-free degree distributions and hierarchical organization. On the one hand, we study a DSF network developed over 3 generations comprising $N = 81$ nodes and $E = 130$ edges. On the other hand, we investigate a 3-generation PSF network with $N = 123$ nodes and $E = 243$ edges. In both cases, we generate an ensemble of 10⁴ networks by rewiring e (equivalently, a fraction $f = \frac{e}{E}$) pairs of edges of the completely deterministic networks, using the mechanism described in fig. 2. Further, for a particular value of f, we compute the values of $\mathcal{L}$, bc_max, $\mathcal{C}^{L}$, $\mathcal{C}^{G}$, r and R of each network with e randomly rewired links of the ensemble and then estimate the expectation values $\langle \mathcal{L} \rangle$, $\langle bc_{max} \rangle$, $\langle \mathcal{C}^{L} \rangle$, $\langle \mathcal{C}^{G} \rangle$, $\langle r \rangle$ and $\langle R \rangle$ as the corresponding ensemble means.

We present the variation in the expected synchronizability $\langle R \rangle$ (solid line) with the fraction f of rewired edges of the DSF network in fig. 3(a). We clearly observe that rewired versions of the otherwise completely DSF network exhibit significantly enhanced as well as deteriorated values of synchronizability (fig. 3(a)). The dashed line represents the minimum R value over the ensemble of rewired networks for a given value of f. The corresponding topologies thus represent approximately "optimally" synchronizable networks for the respective value of f. The fluctuations in the minimum R values may be attributed to the relatively small considered ensemble sizes (10⁴), as compared with the much greater variety of possible rewired networks for a given value of f. Also, in the inset of fig. 3(a), we observe a minimal value of $\langle R \rangle$ (highest average synchronizability) for f equal to $f^{*} = 0.046$ (6 rewired edges) of the 81-node network. As f is further increased beyond $f^{*}$, the value of $\langle R \rangle$ increases again, finally saturating at $\langle R \rangle \sim 185$ for $f \gtrsim 0.6$.

Zoom In Zoom Out Reset image size

Figure 3(b) demonstrates that a similar (and even more pronounced) behaviour of average synchronizability is found in the PSF networks, for which we observe a minimal value of $\langle R \rangle$ for $f^{*} = 0.16$ (39 rewired edges). Moreover, we find similar results (see SM) with regard to synchronizability of 4-generation DSF and PSF networks as well.

Next, we investigate the relationships between f and the topological properties $\langle \mathcal{L} \rangle$, $\langle bc_{max} \rangle$, $\langle \mathcal{C}^{L} \rangle$ and $\langle \mathcal{C}^{G} \rangle$ of the associated ensemble of stochastically rewired DSF networks in fig. 4. For $f < f^{*}$, the decrease in $\langle \mathcal{L} \rangle$ and the increase in $\langle bc_{max} \rangle$ conform to the decreasing trend of $\langle R \rangle$ (cf. the discussion in the SM on network properties and their expected relationship with synchronizability). The value of $\langle \mathcal{C}^{L} \rangle$ (as well as $\langle \mathcal{C}^{G} \rangle$) starts from zero and increases as more edges are rewired. This implies the formation of triangles in the network, which promotes communication between the oscillators, thereby enhancing synchronizability. However, for $f > f^{*}$, further decrease in $\langle \mathcal{L} \rangle$ and increase in $\langle bc_{max} \rangle$ should still improve the average synchronizability, which, however, only declines from thereon.

Zoom In Zoom Out Reset image size

Thus, rewiring a few edges $(f < f^{*})$ alters the topological features of the ensemble of networks for better synchronizability. However, when more edges $(f > f^{*})$ are further rewired, it no longer affects on average the topological properties relevant for improving synchronizability, in fact, only undermines it. Hong et al. [52] have previously proposed maximum betweenness centrality as a suitable indicator for predicting synchronizability of networks. They have shown that among various topological factors, such as short characteristic path length or large heterogeneity of the degree distribution, it is a small value of the maximum betweenness centrality of a network that promotes synchronization [52]. However, this is not corroborated by our results in fig. 4 where we do not observe a strong linear relationship between $\langle R \rangle$ and $\langle bc_{max} \rangle$, as also indicated by a correlation coefficient of 0.776. Similarly, a correlation coefficient of −0.681 rules out a systematic linear dependence between $\langle R \rangle$ and $\langle \mathcal{L} \rangle$. However, a correlation coefficient of 0.847 (0.889) between $\langle R \rangle$ and $\langle \mathcal{C}^{L} \rangle\ (\langle \mathcal{C}^{G} \rangle)$ indicates an appreciable underlying linear relationship. Further, for $f > f^{*}$, the correlation coefficient of 0.939 (0.970) between $\langle R \rangle$ and $\langle \mathcal{C}^{L} \rangle\ (\langle \mathcal{C}^{G} \rangle)$ underlines the above observation.

Analogously to fig. 4, fig. 5 again shows the relationships between f and the topological properties $\langle \mathcal{L} \rangle$, $\langle bc_{max} \rangle$, $\langle \mathcal{C}^{L} \rangle$ and $\langle \mathcal{C}^{G} \rangle$ of the associated ensemble of rewired PSF networks. In this case, we observe a clear relationship between $\langle R \rangle$ and $\langle \mathcal{L} \rangle$, further corroborated by a correlation coefficient of 0.987. On the other hand, a possible linear relationship between $\langle R \rangle$ and $\langle bc_{max} \rangle$, $\langle \mathcal{C}^{L} \rangle$ and $\langle \mathcal{C}^{G} \rangle$ is ruled out by correlation coefficients of −0.25, −0.175 and −0.373, respectively.

Zoom In Zoom Out Reset image size

Taken together, we notice that the topological features of the ensembles of rewired DSF (fig. 4) and PSF (fig. 5) networks exhibit certain contrasting variations, as f is tuned from 0 to 1. Prior to saturation, the bc_max of the rewired DSF networks (fig. 4(b)) initially increases with f, as opposed to a corresponding decrease in bc_max observed for the rewired PSF networks (fig. 5(b)). On the contrary, both clustering coefficients $\langle \mathcal{C}^{L} \rangle$ and $\langle \mathcal{C}^{G} \rangle$ increase with f until saturation for rewired DSF networks (fig. 4(c), (d)), which, however, display a decreasing trend in the case of rewired PSF networks (fig. 5(c), (d)).

Jalan et al. [53] have recently studied the role of degree-degree correlations (assortativity) in the cluster synchronizability of networks during the evolution of coupled chaotic dynamics on them. They have shown that an increased disassortativity relates to an increase or decrease in the cluster synchronizability of networks depending on their degree distribution and average connectivity, such that networks with heterogeneous degree distributions exhibit significant changes in cluster synchronizability in comparison to those with homogeneous degree distributions. For gathering similar insights, we now investigate the relationships between the assortativity $(\langle r \rangle)$ and the synchronizability of the rewired DSF and PSF networks considered here (fig. 6). Note that the degree distribution of the deterministic DSF and PSF networks is preserved during the process of rewiring, as also mentioned earlier. Clearly, the decrease in the degree of disassortativity of the rewired DSF as well as PSF networks is accompanied by an improvement (decline) in their synchronizability for $f < f^{*}\ (f > f^{*})$. However, we again do not observe any strict correlations between $\langle r \rangle$ and $\langle R \rangle$.

Zoom In Zoom Out Reset image size

We finally compare the synchronizability of rewired DSF and PSF networks with that of random scale-free networks generated using the classical BA model of growth and preferential attachment [24]. In this regard, we consider an ensemble of 100 such random scale-free networks of 81 nodes (123 nodes) each for comparison with rewired DSF (PSF) networks, respectively. While generating the BA networks, we incorporate the growing character of the network by starting with a small number of vertices and at every time step introducing a new vertex and linking it to 2 vertices already present in the system, until the network comprises 81 (123) nodes. Preferential attachment is incorporated by assuming that the probability $\Pi_{i}$ that a new node will be connected to node i depends on the degree k_i of node i, such that $\Pi_{i} = \frac{k_{i}}{\sum\limits_{j} k_{j}}$. The 81-node (123-node) BA networks have a total of 158 (242) edges in each realization. The $\langle R \rangle$ values of the considered ensemble of 81-node (123-node) BA networks turn out to be 36.74 (49.75), which is much smaller than the minimum R values among the ensembles of rewired DSF (PSF) networks for different f, presented in fig. 3. Thus, random scale-free networks generated using the classical BA model appear to promote synchronizability better than randomly rewired DSF as well as PSF networks. We outline further investigations to unveil the reasons for this behaviour as a subject of future research.

In a similar spirit, we also investigate the synchronizability of an ensemble of 100 networks of 81 (123) nodes generated using the random configuration model [1]. We find that their $\langle R \rangle$ values of 175.71 (112.54) are larger than those of the rewired DSF (PSF) networks of 141.24 (70.71), even when their respective $f^{*}$ fractions of edges are rewired. Also, the networks with the minimum R values within this ensemble of 81- (123-) node networks generated using the random configuration model are 81.57 (65.93), which are again larger than the minimum values of 70.47 (48.41) among the R values of the entire ensemble of rewired DSF (PSF) networks, for all values of f. Thus, we conclude that the rewired versions of DSF and PSF networks generally exhibit better synchronizability than networks generated using the random configuration model.

Many real-world complex networks simultaneously exhibit the generic feature of scale-free topology along with hierarchical organization. In this regard, two notable models which simultaneously capture the two different topological properties are the deterministic and pseudofractal scale-free networks. These models comprise completely deterministic processes underlying the formation of the respective networks. However, real-world networks are presumably neither completely deterministic nor perfectly hierarchical. Thus, a practical model of such networks should feature an aspect of randomness, while exhibiting scale-free and hierarchical design. For this purpose, we suggested preserving the scale-free degree distribution of the deterministic networks we start with, while tweaking the hierarchical structure by rewiring them. Specifically, we hypothesized that perfectly hierarchical scale-free networks (generated by the deterministic rules of the aforementioned models) with randomly rewired links may provide more realistic representatives of associated real-world topologies than perfectly hierarchical ones.

The desired operational state in many complex systems often concurs with the synchronized motion of dynamical units coupled on a networked architecture. Consequently, we utilized the analytical framework of master stability function (MSF) in investigating the synchronizability of dynamical systems coupled on the proposed network structures. Interestingly, this revealed that the process of rewiring is capable of significantly enhancing as well as deteriorating the synchronizability of the resulting networks. Importantly, when a certain critical fraction of edges of the otherwise completely deterministic networks was rewired, it optimized the average synchronizability of the resulting topologies. This observation is, however, different from Braess's paradox where the addition of edges undermines synchrony in complex oscillator networks [54]. We also investigated the influence of rewiring links on some key topological properties (average path length, maximum betweenness centrality, average local clustering coefficient and global clustering coefficient) of the resulting networks and, in turn, their relation to the synchronizability of the associated topologies demonstrating distinct behaviours in these different models of hierarchical scale-free networks. We speculate that an interplay between the various topological properties of the networks, in particular their average path lengths and clustering coefficients in a trade-off leads to an "optimal" value of synchronizability when rewiring the respective networks.

In a related context, we recall that networks exhibiting the small-world property have been considered conducive for synchronization [46,47]. However, MSF-based measurements of the synchronizability of Watts-Strogatz networks did not reveal exclusive features in the small-world regime [21]. Importantly, the critical fraction of rewired edges (for maximal synchronizability) in the hierarchical scale-free networks considered here, roughly corresponds to a similar value for typical Watt-Strogatz networks to exhibit small-world behaviour. Specifically, we also found that rewiring a few edges of the deterministic scale-free as well as pseudofractal scale-free networks generated a topology with significantly enhanced or "optimal" synchronizability, which did not exhibit major improvements thereafter, as the fraction of rewired edges was further increased.

The aforementioned results may have potential implications in the design of complex networks (simultaneously exhibiting hierarchical structure and scale-free behaviour) for better synchronizability. A more challenging problem is that of comparing real-world topologies with rewired versions of deterministic scale-free hierarchical networks explored here, in ascertaining a possible deterministic backbone of certain practical networks and the proportion of randomness in the same. Any efforts in this direction could certainly provide deeper insights into the developmental processes and synchronizability of many practical networked dynamical systems simultaneously displaying hierarchical structure and scale-free behaviour.

CM and RVD have been supported by the German Federal Ministry of Education and Research (BMBF) via the Young Investigators Group CoSy-CC² (grant No. 01LN1306A). JK and RVD acknowledge support from the IRTG 1740/TRP 2011/50151-0, funded by the DFG/FAPESP. The authors gratefully acknowledge the European Regional Development Fund (ERDF), the German Federal Ministry of Education and Research (BMBF) and the Land Brandenburg for supporting this project by providing resources on the high-performance computer system at the Potsdam Institute for Climate Impact Research.