Tensorial and bipartite block models for link prediction in layered networks and temporal networks

Many real-world complex systems are well represented as multilayer networks; predicting interactions in those systems is one of the most pressing problems in predictive network science. To address this challenge, we introduce two stochastic block models for multilayer and temporal networks; one of them uses nodes as its fundamental unit, whereas the other focuses on links. We also develop scalable algorithms for inferring the parameters of these models. Because our models describe all layers simultaneously, our approach takes full advantage of the information contained in the whole network when making predictions about any particular layer. We illustrate the potential of our approach by analyzing two empirical data sets: a temporal network of e-mail communications, and a network of drug interactions for treating different cancer types. We find that multilayer models consistently outperform their single-layer counterparts, but that the most predictive model depends on the data set under consideration; whereas the node-based model is more appropriate for predicting drug interactions, the link-based model is more appropriate for predicting e-mail communication.

Figure 1

Validation of the inference algorithms on synthetic networks. We generate networks using the tensorial model, T-MBM (left column), and the bipartite model, B-MBM (right column). All networks have $K=J=L=4$ groups, 128 nodes, and 12, 24, or 36 layers (see text for details). We plot the AUC (top), precision (middle), and recall (bottom) as a function of the number of groups assumed by the inference algorithm. Each point shows the average of a fivefold cross validation, and the error bars represent the standard error of the mean (they are typically smaller than symbol sizes). The dashed line represents the naive baseline, and the dotted line the naive independent layers baseline (see text). The solid line indicates the maximum possible performance, obtained by assigning to each link a probability that is exactly the probability that was used to create the network using the model.

Figure 2

Predictive performance of the models for e-mail networks. The left column shows results for Unit 1 and the right column shows results for Unit 5. Top: AUC; middle: precision; bottom: recall. Each bar represents the average of the fivefold cross validation for a given model (see Appendix pp3). The error bars (shown as a vertical line, which is small and not visible in some cases) represent the standard error of the mean.

Figure 3

Probabilistic calibration of the models for e-mail networks. We show results for Unit 1 (left) and Unit 5 (right). Each point in each line represents the average of the fivefold cross validation for a given model, with error bars representing the standard error of the mean. The Naive I.L. model is not included as it only assigned tiny probabilities that resulted in a single data point near the origin.

Figure 4

Marginal calibration of the models for e-mail networks. Each line corresponds to a different model, and each point in a line corresponds to a different e-mail network (see Table 1). Each point represents the average over the fivefold cross validation for a given model. Error bars are smaller than symbols.

Figure 5

Predictive performance of the models for drug-drug interaction networks. We show results for the prediction of antagonistic interactions (left column) and synergistic interactions (right column). Top: AUC statistic. Middle: precision. Bottom: recall. Each bar represents the average of the fivefold cross validation for a given model, with error bars (shown as a vertical line for clarity) representing the standard error of the mean.

Figure 6

Probabilistic calibration of the models for drug-drug interaction networks. We show results for the prediction of antagonistic interactions (left column) and synergistic interactions (right column). Each point in each line represents the average of the fivefold cross validation for a given model. Error bars represent the standard error of the mean. The vertical dashed lines show the density of each training set.

Figure 7

Marginal calibration of the models for drug-drug interaction networks. For each of the models we consider (see legend) we plot the average probability for links being of a certain type (antagonistic or synergistic) with respect to the density of links of that type in the training set. Each point represents the average over the five training sets for a given model. Error bars are smaller than symbols.

Figure 8

Performance as a function of the number of groups for e-mail networks. Each point represents the average of the fivefold cross validation for a given model. The error bars (shown as a vertical line, which is small and not visible in some cases) represent the standard error of the mean. The dashed vertical lines indicate the selected values for $K$ and $L$ in the T-MBM, and $J$ and $L$ in the B-MBM. The results we show correspond to Unit 1.

Figure 9

Performance as a function of the number of groups for drug interaction networks. We show results for the prediction of antagonistic interactions (left column) and synergistic interactions (right column). Each point represents the average of the fivefold cross validation for a given model. The error bars (shown as a vertical line, which is small and not visible in some cases) represent the standard error of the mean. The dashed vertical lines indicate the selected values for $K$ and $L$ in the T-MBM, and $J$ and $L$ in the B-MBM.