$k$-core structure of real multiplex networks

Multiplex networks are convenient mathematical representations for many real-world—biological, social, and technological—systems of interacting elements, where pairwise interactions among elements have different flavors. Previous studies pointed out that real-world multiplex networks display significant interlayer correlations—degree-degree correlation, edge overlap, node similarities—able to make them robust against random and targeted failures of their individual components. Here, we show that interlayer correlations are important also in the characterization of their $\mathbf{k}$-core structure, namely, the organization in shells of nodes with an increasingly high degree. Understanding of $k$-core structures is important in the study of spreading processes taking place on networks, as for example in the identification of influential spreaders and the emergence of localization phenomena. We find that, if the degree distribution of the network is heterogeneous, then a strong $\mathbf{k}$-core structure is well predicted by significantly positive degree-degree correlations. However, if the network degree distribution is homogeneous, then strong $\mathbf{k}$-core structure is due to positive correlations at the level of node similarities. We reach our conclusions by analyzing different real-world multiplex networks, introducing novel techniques for controlling interlayer correlations of networks without changing their structure, and taking advantage of synthetic network models with tunable levels of interlayer correlations.

Figure 1

$k$-core structure of real-world networks. We analyze single-layer networks. The top row refers to results valid for the IPv6 Internet; the bottom row refers to results valid for the arXiv coauthorship network. [(a) and (e)] Scatter plot of node degrees vs coreness. The size of the symbols is proportional to the number of nodes having each specific degree and $k$-shell index values. [(b) and (f)] Relative size $S\left(k\right)$ of the $k$-core (see Appendix pp1-s1) in the real networks (labeled as “org”) and their randomized counterparts (labeled as “rnd”). Randomized networks are obtained by shuffling random pairs of edges while controlling for the average value of the clustering coefficient $\overline{c}$ (Appendix pp1-s2). $\overline{c}\approx 0$ is obtained after 10,000 and 2000 link rewirings in the Internet and arXiv, respectively. [(c) and (g)] $k$-shell index of nodes before and after network randomization (obtained for $\overline{c}\approx 0$). The size of the symbols is proportional to the percentage of nodes whose coreness changed from $k_s$ in the original network to $k_s^{\prime }$ in the reshuffled network. [(d) and (h)] Angular coherence ${\xi }_k$ of the nodes belonging to each $k$-core.

Figure 2

$k$-core structure of single-layer networks. (a) Hyperbolic embedding of the arXiv network. The position of the nodes in the disk is determined by their hyperbolic coordinates; different colors serve to differentiate nodes depending on their $k$-shell index value. (b) Same as in (a) but for an instance of the ${\mathbb{S}}^1$ model built using similar characteristics as in the arXiv network (i.e., same network size $N$, and same values of the degree exponent $\gamma$, average degree $\overline{k}$, and average clustering coefficient $\overline{c}$). (c) Relative size $S\left(k\right)$ of the $k$-core as a function of the threshold value $k$ for the arXiv network and the ${\mathbb{S}}^1$ model. The results for the modeled network are average values over 1000 network instances. The shaded area identifies the region corresponding to one standard deviation away from the average. The average value is computed only over non-null $k$-cores, and the bars in the background of the figure display the fraction of instances where such nonempty cores were indeed present. (d) We consider the same data as in (c) but monitor the angular coherence ${\xi }_k$ as a function of $k$. (e) $S\left(k\right)$ vs $k$ for the ${\mathbb{S}}^1$. We set here the size of the network $N=10000$, degree exponent $\gamma =2.2$, and average degree $\overline{k}=6$. We consider three different values of the temperature parameter $T$. This serves to tune the average value of the clustering coefficient $\overline{c}$ of the model, as $T$ is inversely proportional to $\overline{c}$. Results are averaged over 200 instances of the model. Shaded areas stand for one standard deviation away from the average. (f) Same as in (e) but for $\gamma =2.6$. (g) Same as in (e) but for $\gamma =3.5$. (h) We consider the same networks as in (e) but we monitor angular coherence ${\xi }_k$ vs $k$. (i) Same as in (h) but for $\gamma =2.6$. (j) Same as in (h) but for $\gamma =3.5$.

Figure 3

$\mathbf{k}$-core of real-world multiplex networks. [(a) and (b)] Hyperbolic embedding of the arXiv multiplex network. (a) refers to the layer arXiv1, while (b) to the layer arXiv2. The position of the nodes in the disk is determined by their hyperbolic coordinates, and only nodes that exist in both layers are shown (911 nodes); different colors serve to differentiate nodes depending on their $k$-shell index value. (c) Correspondence among nodes belonging to the $(k,k)$-shells (see Appendix pp1-s1) of the arXiv multiplex network. (d) Same as in (c) but for $k\ge 7$. (e) Same as in (c) but for the randomized version of the multiplex where the node labels of one of the two layers are randomly reshuffled. (f) Relative size $S(k_1,k_2)$ of the $(k_1,k_2)$-core for the arXiv multiplex network. (g) Same as in (f) but for the randomized version of the multiplex network. (h) Relative size $S(k,k)$ of the $(k,k)$-core for the arXiv multiplex network, and its randomized version. These curves are compared with those of the relative size $S\left(k\right)$ of the $k$-core of the individual layers. (i) Same as in (h) but for the metrics of angular coherence ${\xi }_{k,k}$ and ${\xi }_k$.

Figure 4

Interlayer correlations and the $\mathbf{k}$-core structure of the arXiv multiplex network. We analyze the arXiv multiplex network. (a) Different metrics of interlayer similarity as a function of the group size $n$ used to randomize node labels, thus breaking interlayer degree correlations. For $n=1$, node labels of the network are not randomized; full shuffle of node labels is obtained for large $n$ values. We focus here on the case where interlayer degree correlation is broken but we preserve interlayer correlation among node angular coordinates (see main text for details). Metrics of similarities considered here are the Pearson correlation coefficient $r_{k,k^{\prime }}$ among the degrees of nodes in the two layers; normalized mutual information $NM{I}_{\theta ,{\theta }^{\prime }}$ of the angular coordinates of the nodes in the two layers; and edge overlap $\mathcal{O}$ among the two layers (Appendix pp1-s6). (b) Relative size $S(k,k)$ of the $(k,k)$-core. The results of the original multiplex network ($n=1$) are compared with those valid for $n=4$. At this level of randomization, we find that $r_{k,k^{\prime }}=0.36$ and $NM{I}_{\theta ,{\theta }^{\prime }}=0.41$. These numbers should be compared respectively with $r_{k,k^{\prime }}=0.82$ and $NM{I}_{\theta ,{\theta }^{\prime }}=0.46$ of the original network. The results for $n=4$ are average values obtained on 100 independent randomizations. Shaded areas identify the region corresponding to one standard deviation away from the average. (c) Same as in (b) but for the angular coherence ${\xi }_{k,k}$. (d) Scatter plot of the $(k,k)$-shell index of nodes in the original vs the randomized multiplex network. The size of the symbols is proportional to the percentage of points in the scatter plot. [(e)–(h)] Same as in (a)–(d), respectively. We consider here the case where interlayer correlation among nodes' angular coordinates is destroyed but interlayer correlation among node degrees is preserved (see main text for details). The results of the original network are compared with those obtained for $n=16$, when $r_{k,k^{\prime }}=0.78$ and $NM{I}_{\theta ,{\theta }^{\prime }}=0.01$.

Figure 5

Interlayer correlations and the $\mathbf{k}$-core structure of the Internet multiplex network. Same analysis as in Fig. 4 but for the IPv4/IPv6 Internet multiplex network. Correlations of the original network are such that $r_{k,k^{\prime }}=0.82$ and $NM{I}_{\theta ,{\theta }^{\prime }}=0.32$. Results of the real-world system are compared with those obtained after destroying interlayer degree correlations such that $r_{k,k^{\prime }}=0.12$ and $NM{I}_{\theta ,{\theta }^{\prime }}=0.28$ in the top-row panels, and after destroying angular correlations such that $r_{k,k^{\prime }}=0.76$ and $NM{I}_{\theta ,{\theta }^{\prime }}=0.03$ in the bottom-row panels.

Figure 6

Quantifying the effect of interlayer degree and similarity correlations in the $\mathbf{k}$-core structure of real-world multiplex networks. Relative difference $D_S=[{\sum }_{k}S{(k,k)}^{o}rg-{\sum }_{k}S{(k,k)}^{r}nd]/{\sum }_{k}S{(k,k)}^{o}rg$ between the relative $(k,k)$-core sizes $S{(k,k)}^{o}rg$ and $S{(k,k)}^{r}nd$ of real-world multiplex networks and their randomized counterparts. In the randomized counterparts, we either destroy interlayer degree correlation or correlation among the nodes' angular coordinates. Each point in the figure corresponds to one of the real-world multiplex networks considered in this study. The points from left to right correspond to the following multiplex networks: IPv4/IPv6 Internet, arXiv1-arXiv4, arXiv2-arXiv4, arXiv1-arXiv2, Drosophila1-Drososphila2, Air-Train, C.Elegans2-C.Elegans3, and arXiv1-arXiv5 (Ref. [39], Sec. I). The $x$ axis shows the average degree exponent $\gamma$ across the two layers of each multiplex. Results in each case are obtained by taking the average value of $D_S$ over 100 randomized counterparts. Error bars correspond to one standard deviation away from the average. The Pearson correlation coefficient between $D_S$ and $\gamma$ is $r_{D_S,\gamma }=-0.87$ when degree correlation is broken and $r_{D_S,\gamma }=0.48$ when similarity correlation is broken. The dashed lines represent least squares regression lines.

Figure 7

$\mathbf{k}$-core structure of synthetic multiplex networks. We study here the effect of degree and angular correlations on the size of the $(k,k)$-core $S(k,k)$ and its coherence ${\xi }_{k,k}$, in two-layer synthetic multiplex networks constructed according to the geometric multiplex model (Appendix pp1-s7). Interlayer degree correlation can be tuned using the parameter $\nu \in [0,1]$, with $\nu =0$ corresponding to the uncorrelated case, and $\nu =1$ to the case where degrees are maximally correlated. Interlayer correlation among angular coordinates of nodes is tuned using the model parameter $g\in [0,1]$. When generating network instances according to the GMM, we imposed that each layer of the multiplex has $N=10000$ nodes, power-law degree distribution with exponent $\gamma =2.2$, average degree $\overline{k}\approx 6$, and temperature $T=0.5$ (i.e., average clustering coefficient $\overline{c}=0.45$). We consider various combinations of the model parameters $\nu$ and $g$. Results in each case are obtained by taking the average value over 100 realizations. Shaded areas denote regions corresponding to one standard deviation away from the average. (a) Relative size $S(k,k)$ of the $(k,k)$-core as a function of the threshold $k$. The curve corresponding to the monoplex is obtained by measuring $S\left(k\right)$ for the $k$-core of the individual layers, and then taking the average value. [(b) and (c)] Same as in (a) but for different choices of the model parameters. [(d)–(f)] We consider the same data as in (a)–(c), respectively but we monitor the metrics of angular coherence ${\xi }_{k,k}$ and ${\xi }_k$ as functions of the threshold value $k$.

Figure 8

$\mathbf{k}$-core structure of synthetic multiplex networks. Same as in Fig. 7 but for a different value of the degree exponent $\gamma =3.5$. Results for model parameter $g=0.75$ are also shown in this figure. All other model parameters are identical to those used in Fig. 7.

Figure 9

Quantifying the effect of interlayer degree and similarity correlations in the $\mathbf{k}$-core structure of synthetic multiplex networks. [(a) and (b)] Relative difference $D_S=\left[{\sum }_{k}S\left(k\right)-{\sum }_{k}S(k,k)\right]/{\sum }_{k}S\left(k\right)$ between the monoplex and multiplex relative sizes, $S\left(k\right)$ and $S(k,k)$, in two-layer synthetic multiplexes constructed as in Figs. 7 and 8. We consider various combinations of the model parameters $\nu$ and $g$. Results in each case are obtained by taking the average value over 100 realizations. Error bars correspond to one standard deviation away from the average. Reference [39], Fig. 30 shows also the relative difference $D_{\xi }=\left[{\sum }_k{\xi }_k-{\sum }_k{\xi }_{k,k}\right]/{\sum }_k{\xi }_k$ between the angular coherences ${\xi }_k$ and ${\xi }_{k,k}$ of the networks of (a) and (b). (c) is the same as (a) and (b) but for different values of the degree exponent $\gamma$ and parameters $\nu$ and $g$ as shown in the legend.

Figure 10

Coreness in single layers vs coreness in the multiplex. (a) Coreness $k_s$ in arXiv1 of the nodes that have coreness ${(k,k)}_s$ in the multiplex network consisting of arXiv1 and arXiv2. The size of the symbols is proportional to the percentage of nodes with coreness ${(k,k)}_s$ in the multiplex that have coreness $k_s$ in arXiv1. (b) Same as (a) but for arXiv2. [(c) and (d)] Same as (a) and (b) but for the IPv4/IPv6 Internet.