Diffusion dynamics and synchronizability of hierarchical products of networks

The hierarchical product of networks represents a natural tool for building large networks out of two smaller subnetworks: a primary subnetwork and a secondary subnetwork. Here we study the dynamics of diffusion and synchronization processes on hierarchical products. We apply techniques previously used for approximating the eigenvalues of the adjacency matrix to the Laplacian matrix, allowing us to quantify the effects that the primary and secondary subnetworks have on diffusion and synchronization in terms of a coupling parameter that weighs the secondary subnetwork relative to the primary subnetwork. Diffusion processes are separated into two regimes: for small coupling the diffusion rate is determined by the structure of the secondary network, scaling with the coupling parameter, while for large coupling it is determined by the primary network and saturates. Synchronization, on the other hand, is separated into three regimes, for both small and large coupling hierarchical products have poor synchronization properties, but is optimized at an intermediate value. Moreover, the critical coupling value that optimizes synchronization is shaped by the relative connectivities of the primary and secondary subnetworks, compensating for significant differences between the two subnetworks.

Figure 1

Hierarchical product. Illustration of the hierarchical product $G_1\left(\{1,4\}\right)\sqcap G_2$ of two subgraphs $G_1$ and $G_2$.

Figure 2

Laplacian eigenvalues. The full spectrum of nontrivial eigenvalues for the Laplacian matrix $L_{\alpha }$ as a function of the coupling parameter $\alpha$ for the hierarchical product illustrated in Fig. 1.

Figure 3

Laplacian eigenvalues. Approximate (dashed blue and dot-dashed red) and actual (solid black) eigenvalues for the Laplacian matrix $L_{\alpha }$ for the hierarchical product illustrated in Fig. 1 for (a) small and (b) large $\alpha$.

Figure 4

Diffusion dynamics. The diffusion rate computed directly from simulations (blue circles) and our approximations for ${\lambda }_2$ (dashed black) as a function of $\alpha$ for the hierarchical product illustrated in Fig. 1. Inset: diffusion time scale.

Figure 5

Large coupling: diffusion rate and root set fraction I. For ER networks of size $N_1=100$ with link probability $p=0.1$, the quantities ${\nu }_2$ (blue circles) and ${\nu }_1^0$ (red triangles) as a function of the root set fraction $n/N_1$. Results represent an average with standard deviation indicated by dashed curves. The transition from ${\lambda }_2={\nu }_1^0$ to ${\lambda }_2={\nu }_2$ occurs at $n/N_1\approx 0.3487$.

Figure 6

Large coupling: diffusion rate and root set fraction II. For BA networks of size $N_1=100$ with minimum degree $k_0=3$, the quantities ${\nu }_2$ (blue circles) and ${\nu }_1^0$ (red triangles) as a function of the root set fraction $n/N_1$ for root sets chosen (a) with the highest degree nodes (b) randomly and (c) with the lowest degree nodes. Results represent an average with standard deviation indicated by dashed curves. For the three cases the transition from ${\lambda }_2={\nu }_1^0$ to ${\lambda }_2={\nu }_2$ occurs at $n/N_1\approx 0.1630$, 0.3375, and 0.3843, respectively.

Figure 7

Synchronizability. (a) Actual (solid black) and approximate (dashed blue and dot-dashed red, respectively) eigenvalues ${\lambda }_N$ and ${\lambda }_2$ as a function of coupling $\alpha$ for the hierarchical product illustrated in Fig. 1. (b) Actual (solid black) and approximate (dashed blue) synchronizability ratio $R={\lambda }_N/{\lambda }_2$ as a function of coupling $\alpha$.

Figure 8

Optimal synchronizability. The actual (blue circles) and approximated (red triangles) optimal synchronizability ratio $R_{\text{min}}$ achievable as a function of the root set fraction $n/N_1$. Results represent an average over 1000 hierarchical products constructed using ER networks of sizes $N_1=100$ and $N_2=20$ with link probabilities $p=0.1$ and 0.5.

Figure 9

Critical coupling. The actual (blue circles) and approximated (red triangles) critical coupling parameter ${\alpha }_c$ that optimized synchronizability ratio, $R=R_{\text{min}}$, as a function of the connectivity ratio ${\langle k\rangle }_1/{\langle k\rangle }_2$. 100 networks were constructed using $N_1=N_2=50$ with mean degrees determined randomly such that they fall between 5 and 45. Results fall roughly around the power-law relationship ${\alpha }_c\propto {\left({\langle k\rangle }_1/{\langle k\rangle }_2\right)}^{\beta }$ (dashed black) for $\beta \approx 1.18$.