Community detection, link prediction, and layer interdependence in multilayer networks

Complex systems are often characterized by distinct types of interactions between the same entities. These can be described as a multilayer network where each layer represents one type of interaction. These layers may be interdependent in complicated ways, revealing different kinds of structure in the network. In this work we present a generative model, and an efficient expectation-maximization algorithm, which allows us to perform inference tasks such as community detection and link prediction in this setting. Our model assumes overlapping communities that are common between the layers, while allowing these communities to affect each layer in a different way, including arbitrary mixtures of assortative, disassortative, or directed structure. It also gives us a mathematically principled way to define the interdependence between layers, by measuring how much information about one layer helps us predict links in another layer. In particular, this allows us to bundle layers together to compress redundant information and identify small groups of layers which suffice to predict the remaining layers accurately. We illustrate these findings by analyzing synthetic data and two real multilayer networks, one representing social support relationships among villagers in South India and the other representing shared genetic substring material between genes of the malaria parasite.

Figure 1

$\mathrm{Te}\underset{\_}{n}$pa$\begin{array}{c}\\ \mathrm{t}\\ .\end{array}\begin{array}{c}\\ \mathrm{t}\\ .\end{array}$i Village community partition. On the left we show the division by caste membership. To the right we show the membership in each of the four communities for each node (each figure represents one community), with color ranging from white if the normalized outgoing membership $u_{ik}=0$ to black if $u_{ik}=1$. Values in between denote overlapping membership (grey). The fact that caste membership partially overlaps with the communities identified by our algorithm suggests a relationship between topological structure and caste, a topic that will be investigated in a future paper.

Figure 2

Layer interdependence in the Indian social support networks. On the $x$ axis are the layers' labels used in the test data set, and the $y$ axis shows the AUC obtained through the cross-validation schemes for measuring layer interdependence. Bold lines are for $\mathrm{Te}\underset{\_}{n}$pa$\begin{array}{c}\\ \mathrm{t}\\ .\end{array}\begin{array}{c}\\ \mathrm{t}\\ .\end{array}$i Village, dashed for $\mathrm{A}\underset{\_}{l}$akāpuram Village. $L=1$ refers to single-layer AUC, where the algorithm is only given access to that layer. $L=2,3,12$ show the increase in the AUC for that layer when the algorithm is given access to $L$ layers; for $L=2$ and $L=3$ we choose the best set of $L-1$ additional layers using the greedy procedure described in the previous section.

Figure 3

Layer interdependence in the malaria network. Each of the nine layers corresponds to a so-called highly variable region (HVR) of the malaria parasite genes, indicated on the $x$ axis, and the $y$ axis shows the AUC obtained through the cross-validation schemes for measuring layer interdependence. $L=1$ refers to single-layer AUC, where the algorithm is only given access to that layer. $L=2,3,9$ show the increase in the AUC for that layer when the algorithm is given access to $L$ layers; for $L=2$ and $L=3$ we choose the best set of $L-1$ additional layers using the greedy procedure described in the previous section. Points and error bars are the average and standard deviation over the fivefold cross validation. Unlike the social support networks, we see that the accuracy of predicting one layer actually decreases when we include others in the training set, indicating that the different layers have independent structure.

Figure 4

Clusters of the affinity matrices in the layers of the Indian village networks, for $\mathrm{Te}\underset{\_}{n}$pa$\begin{array}{c}\\ \mathrm{t}\\ .\end{array}\begin{array}{c}\\ \mathrm{t}\\ .\end{array}$i on the left and $\mathrm{A}\underset{\_}{l}$akāpuram on the right. Cluster labels were obtained using the $k$-means algorithm, treating each $w^{\left(\alpha \right)}$ as a $K^2$-dimensional vector, and we use principal component analysis to visualize them in two dimensions.