Multilayer Stochastic Block Models Reveal the Multilayer Structure of Complex Networks

In complex systems, the network of interactions we observe between systems components is the aggregate of the interactions that occur through different mechanisms or layers. Recent studies reveal that the existence of multiple interaction layers can have a dramatic impact in the dynamical processes occurring on these systems. However, these studies assume that the interactions between systems components in each one of the layers are known, while typically for real-world systems we do not have that information. Here, we address the issue of uncovering the different interaction layers from aggregate data by introducing multilayer stochastic block models (SBMs), a generalization of single-layer SBMs that considers different mechanisms of layer aggregation. First, we find the complete probabilistic solution to the problem of finding the optimal multilayer SBM for a given aggregate-observed network. Because this solution is computationally intractable, we propose an approximation that enables us to verify that multilayer SBMs are more predictive of network structure in real-world complex systems.

Popular Summary

Complex systems often consist of components that interact via different mechanisms to produce networks made up of multiple “layers.” Recent studies have revealed that the existence of multiple interaction layers can have a dramatic impact on the dynamical processes occurring on these systems; the behavior of multilayer networks is qualitatively different from that of single-layer systems. Unfortunately, we typically observe only aggregate networks in which all information about the constitutive layers has been lost. In these cases, one cannot be sure that the network is the outcome of multiple processes. Here, we investigate whether real networks are better described as the outcome of a single mechanism or as the superposition of layers generated by multiple mechanisms.

We consider two aggregation possibilities for combining layers: AND and OR, and we parametrize the average connectivity between nodes. We investigate how well we can detect both missing and spurious interactions in the single-layer projection of a network with multiple known interaction layers (for the yeast S. cerevisiae) and for other (hypothetically) aggregated real-world networks such as air transportation over eastern Europe, a university’s Email network, and the collaborations of jazz musicians. We find that, for real networks, multilayer models are more predictive of network structure than single-layer models, which supports the idea that even those networks that are presented to us as single layer may indeed be projections of multilayer networks.

While our method is computationally expensive, we expect that our results will motivate future studies to simplify models of complex networks.

Figure 1

Network aggregation mechanisms. In aggregated multilayer networks, different networks containing the same nodes but with different adjacency matrices are combined into an observed network with adjacency matrix $A^{\mathcal{O}}$, where all information about the original layers has been lost. We consider two aggregation mechanisms of two-layer networks with adjacency matrices $A^1$ and $A^2$: (a) AND aggregation, in which $A_{ij}^{\mathcal{O}}=A_{ij}^1{A}_{ij}^2$, so that $A^{\mathcal{O}}=1$ if, and only if, $i$ and $j$ are connected in both layers, and (b) OR aggregation in which $A_{ij}^{\mathcal{O}}=1-(1-A_{ij}^1)(1-A_{ij}^2)$, so that $A^{\mathcal{O}}=1$ if $i$ and $j$ are connected in at least one layer.

Figure 2

Exact and approximate multilayer SBM ensembles. (a) Two independent single-layer SBMs aggregated using the AND mechanism. We represent each single-layer SBM by its node-to-node connection probability matrix (indicated in the shades of green shown in the color bar; note that node ordering is different in each SBM). The aggregation of the two layers can also be represented as a single-layer SBM, in which each group comprises the nodes that belong to the same pair of groups $\alpha$ in layer 1 and $\gamma$ in layer 2; this is the intersection partition ${\mathcal{P}}_I$. Moreover, if group $r$ in ${\mathcal{P}}_I$ corresponds to groups $\alpha$ in ${\mathcal{P}}_1$ and $\gamma$ in ${\mathcal{P}}_2$, and group $s$ in ${\mathcal{P}}_I$ corresponds to groups $\beta$ in ${\mathcal{P}}_1$ and $\delta$ in ${\mathcal{P}}_2$, then the probability of connection in the single-layer SBM is $q_{rs}^{\text{AND}}=q_{\alpha \beta }^1{q}_{\gamma \delta }^2$. (b) For a fixed pair of partitions ${\mathcal{P}}_1$ and ${\mathcal{P}}_2$, we integrate over the ensemble of all possible probability matrices $Q_1$ and $Q_2$ [Eq. (3)]. For each pair $(Q_1,Q_2)$, the resulting $q_{rs}^{\text{AND}}$ are therefore correlated. In our approximation, we assume that the elements of the intersection $q_{rs}^{\text{AND}}$ are randomly drawn and independent of each other.

Figure 3

Performance of missing and spurious link identification on synthetic aggregated two-layer networks. Each row shows results for the different sets of two-layer SBMs illustrated in (a),(d),(g). We consider networks of $N=168$ (a),(d) and $N=240$ (g) nodes divided into uniform groups in each layer. In the connection probability matrices, dark green represents a high connection probability $p_h$ and light green a low connection probability $p_l$. We generate synthetic networks varying two parameters: the low-to-high connectivity ratio $\lambda =p_l/p_h<1$ and the average connectivity $k$ (see Supplemental Material [48]). To compare the performance of the different approaches at detecting missing links (b),(e),(h), we randomly remove a fraction $f=0.25$ of the links (false negatives) from the real network and calculate the reliability of each unobserved link. Then we calculate the AUC statistic; that is, we rank the links by decreasing reliability and calculate how often a removed link (false negative) has a higher reliability than a link that does not exist in the original network (true negative). Analogously, to detect spurious links (c),(f),(i), we randomly add a fraction $f=0.25$ of links (false positives), calculate the reliability of the observed links, and calculate how often an added link (false positive) has a lower reliability than a link that exists in the original network (true positive). For each pair of parameter values, we generate 30 different synthetic networks. We compare the average performance (AUC) at detecting missing links (b),(e),(h) and spurious links (c),(f),(i) of the approximate multilayer SBM approach, ${\mathrm{AUC}}_{2L}$, against that of the single-layer SBM approach, ${\mathrm{AUC}}_{1L}$. The size of the circles represents the ${\mathrm{AUC}}_{2L}$ of the multilayer approach. The color of the circles represents the logarithm of the ratio ${\mathrm{AUC}}_{2L}/{\mathrm{AUC}}_{1L}$, so that blue circles correspond to instances where the multilayer approach outperforms the single-layer approach, and conversely for red circles. [See Supplemental Material [48] for results for other values of $f$ (fraction of false negatives/false positives) and for synthetic networks generated for different numbers of nodes and/or groups.]

Figure 4

Performance of missing and spurious link identification on a real multilayer network. We show the accuracy at detecting (a) missing and (b) spurious interactions in the protein-protein interaction network of S. cerevisiae, obtained from the BioGRID database [50], by aggregating two layers as described in the text. To compare the performance of the different approaches at detecting missing links (a), we randomly remove a fraction of the links (false negatives) from the real network and calculate the reliability of each unobserved link. Then we calculate the AUC statistic; that is, we rank the links by decreasing reliability and calculate how often a removed link (false negative) has a higher reliability than a link that does not exist in the original network (true negative). Analogously, to detect spurious links (b), we randomly add a fraction of links (false positives), calculate the reliability of the observed links, and calculate how often an added link (false positive) has a lower reliability than a link that exists in the original network (true positive).

Figure 5

Performance of missing and spurious link identification on real aggregated networks. We proceed as in Fig. 4 to compare the performance of the different approaches at detecting missing links (a),(c),(e),(g),(i) and spurious links (b),(d),(f),(h),(j). We show results for five real-world networks (see Supplemental Material for results on other networks [48]): (a),(b) the air transportation network in Eastern Europe [51], (c),(d) the neural network of C. elegans [52], (e),(f) the Email network within an organization [53], (g),(h) the network of books about U.S. politics in 2004 elections [54], and (i),(j) the transcriptional regulation network of yeast S. cerevisiae [55]. Red lines represent the ${\mathrm{AUC}}_{1L}$ obtained with single-layer SBMs, blue circles correspond to AND two-layer SBMs, and green circles to OR two-layer SBMs.

Figure 6

Model comparison using Bayes factors. We show the Bayes factor $K$ [Eq. (7)] for all the real-world network examples we analyze (see text). Black dots show results for the Bayes factor considering the two-layer AND SBM and the single-layer SBM. Orange diamonds show the Bayes factor considering the single-layer SBM with a degeneracy factor and the single-layer SBM. The regions in different shades of gray indicate the qualitative scale introduced by Kass and Raftery to map $K$ values to human perceptions of strength of evidence [60] (“negative,” $K<1$; “not worth more than a bare mention,” $1<K<3$; “positive,” $3<K<20$; “strong,” $20<K<150$; “very strong,” $K>150$).