Driving Interconnected Networks to Supercriticality

Networks in the real world do not exist as isolated entities, but they are often part of more complicated structures composed of many interconnected network layers. Recent studies have shown that such mutual dependence makes real networked systems potentially exposed to atypical structural and dynamical behaviors, and thus there is an urgent necessity to better understand the mechanisms at the basis of these anomalies. Previous research has mainly focused on the emergence of atypical properties in relation to the moments of the intra- and interlayer degree distributions. In this paper, we show that an additional ingredient plays a fundamental role for the possible scenario that an interconnected network can face: the correlation between intra- and interlayer degrees. For sufficiently high amounts of correlation, an interconnected network can be tuned, by varying the moments of the intra- and interlayer degree distributions, in distinct topological and dynamical regimes. When instead the correlation between intra- and interlayer degrees is lower than a critical value, the system enters in a supercritical regime where dynamical and topological phases are no longer distinguishable.

Popular Summary

In the age of Facebook, Twitter, and email, the phenomena of a story, an idea, or a certain behavior going “viral” are commonplace. But, viewed scientifically, such phenomena are far from being trivial. First of all, the underlying mechanisms have certain degrees of unpredictability, or randomness. Moreover, the structure of human connectivity that enables such viral spreading (or “diffusion”) is actually composed of many layers of networks arbitrarily interconnected. Very little is known about the basic scientific properties of viral spreading processes taking place in interconnected multilayer networks. In this paper, we provide the first full characterization of diffusion processes on this new type of network topology.

We find that features of diffusion processes in interconnected networks strongly depend on the relation of proportionality between the numbers of connections that nodes have in different layers. If the network is such that the number of neighbors that a node has within a network layer—called “intralayer degree”—is similar to the number of neighbors it has in another (e.g., many/few friends on Facebook corresponds to many/few followers on Twitter), then information can spread either in the same network layer or among layers. If, instead, the numbers of neighbors in different layers are inversely proportional (e.g., many/few friends on Facebook corresponds to few/many followers on Twitter), then diffusion takes place simultaneously both within and among layers, and information spreads at fast rates.

Our findings have direct applicability in the design and control of real interconnected systems. If the goal is to enhance the rate of diffusion, as in the case of information-spreading phenomena in social networks or efficient navigability protocols in transportation networks, then the best strategy to follow is to design the system to have different nodes to serve as intralayer and interlayer hubs. If, instead, the goal is to contain diffusion, such as in epidemic-spreading phenomena, then the optimal structure requires a strong proportionality between intralayer and interlayer degrees.

Figure 1

Abrupt transition in interconnected networks. Spectral analysis of the normalized Laplacian $\mathcal{L}$ of an interconnected network composed of two network layers of size $N=1024$. The degree sequence is composed of integers extracted from a power-law probability distribution with exponent $\gamma =2.5$ defined on the support $[32,N]$. Intra- and interlayer degree sequences are perfectly aligned so that the correlation term reads $\xi =\sum _{k^{\text{in}},k^{\text{out}}}{k}^{\text{in}}{k}^{\text{out}}P(k^{\text{in}},k^{\text{out}})=⟨k^2⟩$. As the weight of the intralayer connections $p$ varies, the system explores different regimes that are clearly visible from the spectrum of $\mathcal{L}$. (a) For $p=0.3$, only the largest eigenvalue ${\nu }_{2N}$ is well separated from the rest of the spectrum. The system is said to be in the “bipartite” regime ($\mathcal{B}$ phase). (b) For $p=0.5$, there are no detached eigenvalues. The system is in the “indistinguishable” regime ($\mathcal{I}$ phase). (c) For $p=0.7$, the second-smallest eigenvalue ${\nu }_2$ is well separated for the rest of the spectrum. The system is in the “decoupled” regime ($\mathcal{D}$ phase). (d) In the $\mathcal{B}$ phase, the components of the largest eigenvector ${\mathbf{w}}_{2N}$ corresponding to a single network layer (blue squares) are linearly correlated with the square root of the respective node degrees $\sqrt{k}$, while those of the second-smallest eigenvector ${\mathbf{w}}_2$ (red circles) are not. (e) In the $\mathcal{I}$ phase, there is no correlation between the components of ${\mathbf{w}}_{2N}$ (${\mathbf{w}}_2$) and $\sqrt{k}$. (f) In the $\mathcal{D}$ phase, the components of the second-smallest eigenvector ${\mathbf{w}}_2$ are linearly correlated with $\sqrt{k}$, while the components of ${\mathbf{w}}_{2N}$ are not. (g) The transition points $p_c^{-}\simeq 0.42$ and $p_c^{+}\simeq 0.58$ (delimiting the vertical gray band) between the different regimes correspond to the points in which our prediction [Eq. (5), dashed black line] enters the continuous band of the spectrum [Eq. (4), horizontal gray band]. Red circles refer to ${\nu }_2$, while blue squares refer to ${\nu }_{2N}$. (h) The sums of the components of ${\mathbf{w}}_2$ (red circles) and ${\mathbf{w}}_{2N}$ (blue squares) corresponding to nodes of a single network layer can be used as an order parameter to monitor the transition between the different regimes. ($\mathbf{u}$ is the vector whose components are all equal to 1.) (i) As noted above, in the $\mathcal{D}$ phase ($\mathcal{B}$ phase), the components of ${\mathbf{w}}_2$ (${\mathbf{w}}_{2N}$) are perfectly correlated with the square root of the node degrees.

Figure 2

Phase diagram. We consider interconnected networks composed of two layers of size $N=8192$ with intra- and interlayer degrees obeying a Poisson distribution with average $⟨k⟩=32$. (a) Second-smallest eigenvalue ${\nu }_2$ as a function of the weight of the intralayer connections $p$. For values of the correlation term $\xi$ in the range $[⟨k{⟩}^2,⟨k^2⟩]$, the results of numerical computations (symbols) are in very good agreement with our analytic predictions (dashed lines). The critical point $p_c^{+}$ is determined as the point for which the dashed lines enter the spectral band (gray area). For $\xi ={\xi }_{\min }$, our predictions fail to correctly describe how ${\nu }_2$ changes as a function of $p$. (b) As in Fig. 1, we monitor the transition between the $\mathcal{D}$ and the $\mathcal{I}$ phases, by looking at the order parameter ${\mathbf{u}}^T{\mathbf{w}}_2/\sqrt{N/2}$. As $\xi$ decreases, the change of the order parameter becomes smoother, and the value of the critical point gets closer to $p=0.5$. For $\xi \in [⟨k{⟩}^2,⟨k^2⟩]$, the order parameter goes to 0 if $p<p_c^{+}$. For $\xi ={\xi }_{\min }$, instead, the order parameter is even larger than 0 for $p=0.5$. (c) The same behavior described for the order parameter is visible if we monitor the transition through the linear correlation coefficient between the eigenvector components and the right-hand side of Eq. (6). (d) Phase diagram representing the expected behavior of the system in the thermodynamic limit. The red line stands for the critical value $p_c^{+}$, while the blue line represents $p_c^{-}$ [Eq. (9)]. These critical values are plotted as functions of the quantity $⟨k^2⟩-\xi$, ranging between 0 and $⟨k^2⟩-{\xi }_{\min }$. As a reference, the dashed line represents the point at which $\xi =⟨k^2⟩$. Although the curves corresponding to $p_c^{+}$ and $p_c^{-}$ do not intersect, for values of the correlation term $\xi$ that are sufficiently low, their analytic continuations suggest the disappearance of the $\mathcal{I}$ phase and the appearance of a supercritical regime where both the bipartite and the decoupled phases are present (i.e., the $\mathcal{BD}$ phase).

Figure 3

Supercritical regime. Spectral analysis of the normalized Laplacian $\mathcal{L}$ for an interconnected network with a degree sequence identical to the one analyzed in Fig. 1. In this case, however, intra- and interlayer degree sequences are aligned in such a way that the correlation term is $\xi \simeq 1/2(⟨k^2⟩+⟨k{⟩}^2)$. (a) For $p=0.5$, the system is in the $\mathcal{BD}$ phase, where both the eigenvalues ${\nu }_2$ and ${\nu }_{2N}$ are well separated from the other eigenvalues of $\mathcal{L}$. (b) The components of both eigenvectors ${\mathbf{w}}_2$ and ${\mathbf{w}}_{2N}$ are correlated with the right-hand side of Eq. (6). (c) The eigenvalues ${\nu }_2$ (red circles) and ${\nu }_{2N}$ (blue squares) touch the continuous band tangentially. (d) The order parameter clearly shows the presence of the supercritical regime, where both the $\mathcal{B}$ and $\mathcal{D}$ phases are simultaneously present, for a wide range of values of $p$. Only for very low (large) values of $p$, the system is in the pure $\mathcal{B}$ phase ($\mathcal{D}$ phase).

Figure 4

Random-walk dynamics. We consider two interconnected networks composed of $N=8192$ nodes. Degrees are extracted from a power-law distribution with exponent $\gamma =2.5$ defined on the support $[32,N]$. We monitor the trajectory of a random walker moving on these systems for different values of the correlation term $\xi$ and different values of the weight of the intralayer connections $p$. (a) Autocorrelation function $R(\tau )=⟨x(t)x(t+\tau )⟩$ as a function of the time delay $\tau$. In the definition of $R(\tau )$, $x(t)=+1$ if the random walker does not change network layer at time $t$, and $x(t)=-1$ otherwise. (b) Spectral density $S(\omega )$ of the autocorrelation functions of (a). Intralayer movements are characterized by the presence of a peak of $S(\omega )$ at $\omega =0$, while interlayer jumps are emphasized by the presence of peaks at $\omega =\pm 1$.