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

Caterina De Bacco; Eleanor A. Power; Daniel B. Larremore; Cristopher Moore

Source-linked AI summary

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

Caterina De Bacco, Eleanor A. Power, Daniel B. Larremore, Cristopher Moore

arXiv:1701.01369v6Jan 5, 2017cs.SIcond-mat.stat-mechphysics.soc-ph

TL;DR

Multilayer networks combine multiple relationship types whose shared and distinct structures complicate community detection, link prediction, and interdependence analysis. The paper introduces a generative model with overlapping common communities and layer-specific connectivity, fit by scalable expectation-maximization. Synthetic experiments show higher community-recovery performance than diagonal and BPTF algorithms across three tested structure types, while link prediction quantifies redundancy and interdependence among layers.

Problem
Multilayer analysis needs a way to detect overlapping communities, predict missing links, and determine whether layers provide shared or independent structural information.
Method
The paper fits a generative multilayer mixed-membership block model with shared node communities, layer-specific connectivity patterns, link prediction, and expectation-maximization.
Results
MULTITENSOR achieves significantly greater community-recovery performance than diagonal and BPTF algorithms in all three tested synthetic structure cases.
Takeaways & Limitations
Layer interdependence is measured by how much one or more layers improve link prediction in another, identifying redundancy and compact informative layer sets.

Abstract

from arXiv · show

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 substrings material between genes of the malaria parasite.

I. INTRODUCTION

The paper addresses multilayer networks whose relationship types may have related or unrelated structure, proposing one framework for community detection, link prediction, and layer interdependence. Its shared overlapping communities accommodate varied connectivity patterns across layers while supporting scalable inference and redundancy-aware layer selection.

Motivation: Multilayer community detection is difficult because layers may contain related, unrelated, or complementary structural information.Redundant layers can strengthen community evidence, while unrelated layers may reveal different information about the underlying structure.
Proposed framework: The proposed generative model infers a shared mixed-membership partition while allowing each layer to combine assortative, disassortative, and directed connectivity patterns.The framework applies to directed and undirected networks and integer-weighted links.
Evaluation and applications: An efficient expectation-maximization algorithm fits the model, with experiments covering synthetic benchmarks and two real multilayer networks.The real applications concern social support relationships in South India and shared genetic substrings among malaria-parasite genes.
Inference tasks: The model assigns probabilities to unobserved links of each type, enabling link prediction from incomplete multilayer data.This extends the framework beyond classifying nodes to probabilistic prediction of missing relationships.
Layer interdependence: Layer interdependence is quantified by whether information from additional layers improves link-prediction performance, revealing redundant layers and compact informative layer sets.The approach is motivated by settings where collecting every layer requires limited laboratory or field resources.
Limitations of prior approaches: Existing approaches often aggregate layers or analyze them separately, while modularity-based methods typically produce nonoverlapping partitions and do not assign link probabilities.These methods also inherit dependence on an appropriate null model from single-layer community detection.

II. THE MULTILAYER MIXED-MEMBERSHIP STOCHASTIC BLOCK MODEL

The model represents multilayer networks as tensor-valued edge data generated from overlapping node memberships and layer-specific affinity matrices. It uses Poisson structure for weighted or multigraph data and estimates parameters with expectation-maximization rather than Bayesian sampling.

Network representation: Each multilayer network has N nodes, L layers, and one adjacency matrix per layer, equivalently represented as an N × N × L tensor.The entry A(α)_ij counts edges from node i to node j in layer α.
Node memberships: The model generates networks from K overlapping groups, with each node assigned a nonnegative K-dimensional membership vector.Directed networks use separate outgoing and incoming membership vectors, while undirected networks set them equal.
Layer structure: Each layer has a K × K affinity matrix whose entries determine expected edge density between pairs of groups.Layer-specific matrices can encode assortative, disassortative, asymmetric directed, or core-periphery structure.
Degree heterogeneity: Unnormalized membership vectors allow heterogeneous degree distributions without changing the distribution of a node’s neighbors.Scaling a membership vector changes expected in- or out-degree while preserving neighbor proportions.
Distribution and inference: A Poisson formulation supports multigraphs and integer-weighted networks while yielding a tractable expectation-maximization algorithm.The applications focus on the sparse case where edge counts are 0 or 1.
Relation to prior models: Unlike related Bayesian tensor models, this approach estimates parameters directly with expectation-maximization rather than Monte Carlo sampling.The paper describes the model as closely related to recently proposed Poisson Tucker decompositions.

III. THE EXPECTATION-MAXIMIZATION ALGORITHM

The paper fits its multilayer model by maximum likelihood using a variational formulation and an efficient expectation-maximization algorithm. Alternating updates produce a locally optimal parameter estimate, with per-iteration cost scaling linearly in the total number of multilayer edges up to the K^2 factor.

Maximum-likelihood inference jointly estimates node membership vectors and layer-specific affinity matrices from the observed adjacency tensor.
A variational distribution ρ over group pairs for each observed edge makes the difficult likelihood optimization more tractable.ρ estimates the probability that an edge is attributable to each pair of groups.
The expectation-maximization algorithm alternates between updating edgewise marginals ρ and model parameters Θ until reaching a fixed point.The expectation step is especially simple because the Boltzmann distribution factorizes across edges.
The resulting fixed point is only a local maximum, so the implementation repeats EM from multiple random initializations and retains the run with the largest objective value.
O(MK^2) per iteration, where M is the total number of edges summed over layers and K is the number of groups.Because convergence typically occurs in few iterations, total runtime is roughly linear in dataset size.
MULTITENSOR yields soft overlapping community assignments by normalizing membership vectors, while distinct incoming and outgoing vectors support directed networks.Hard assignments can be obtained by selecting the largest membership entry.

IV. RESULTS ON SYNTHETIC NETWORKS

Synthetic benchmarks show that MULTITENSOR accurately recovers multilayer community structure and outperforms restricted diagonal and Bayesian tensor-factorization alternatives. Its advantage is strongest when layers combine different structural patterns, although all methods perform poorly in highly stochastic regimes.

Benchmark setup: MULTITENSOR is evaluated against a diagonal model and BPTF using cosine similarity and L1 error against ground-truth multilayer memberships.Cosine similarity measures alignment, while L1 error measures distributional distance after optimizing over group permutations.
Comparison methods: The competing diagonal model restricts each layer’s affinity matrix to diagonal structure, whereas BPTF uses Gamma-distributed parameters and Bayesian updates.
Benchmark setup: Higher layer interdependence p and lower mixing µ make the benchmark easier because layers are more correlated and links are more concentrated within communities.
Assortative benchmarks: In every benchmark case, MULTITENSOR achieves the highest cosine similarity and, in most cases, the smallest L1 error.
Assortative benchmarks: When either µ = 0.5 or p = 0.5, all three algorithms perform poorly because the network contains a high level of stochasticity.
Mixed structural layers: MULTITENSOR performs significantly better than the diagonal and BPTF algorithms on networks mixing assortative, disassortative, core-periphery, and biased directed layers.The comparison covers networks with L = 2 or L = 4 layers, K = 2 groups, and N = 300 nodes.

V. LEARNING LAYER INTERDEPENDENCE VIA LINK PREDICTION

The paper defines layer interdependence by testing whether information from one layer improves link prediction in another. This framework supports identifying related, redundant, or independently informative layers while using a computationally efficient greedy procedure for layer selection.

Why prediction-based dependence: The proposed measure captures relationships that partition correlations miss, including layers sharing group labels while differing between assortative and disassortative structure.Such layers can be statistically different yet mutually informative for prediction.
Link-prediction measure: AUC measures whether true missing links receive higher estimated expected-link values than false ones, with 1 indicating perfect prediction and 1/2 chance performance.The model ranks missing adjacency-tensor entries using M^(α)_ij, the expected number of links of type α between nodes i and j.
Link-prediction measure: The link-prediction evaluation hides 20% of a target adjacency matrix, trains with the remaining entries and optional other layers, and averages AUC across five folds.The held-out entries include zeros and ones, so accuracy is evaluated on both links and non-links.
Defining interdependence: Layer interdependence is defined by how much knowledge of one layer improves link prediction in another, including possible decreases for independent layers.Pairwise and multilayer AUCs compare prediction using a target layer alone with prediction augmented by other layers.
Selecting informative layers: A greedy bottom-up procedure adds the layer that most increases AUC at each step, efficiently finding small layer sets that predict links accurately.The procedure is computationally efficient but is not guaranteed to find the best subset of a given size.
Selecting informative layers: A top-down alternative would remove layers causing the smallest AUC decrease to compress redundant information, but the authors did not pursue it.The method also clusters inferred affinity matrices as a second notion of layer interdependence.

VI. LINK PREDICTION AND LAYER INTERDEPENDENCE IN REAL NETWORKS

The MULTITENSOR model is evaluated on two real multilayer networks, revealing shared structure across Indian social-support layers but independent structure across malaria-gene layers. Cross-layer link-prediction performance improves for the social networks and worsens for the malaria network, while the study explicitly leaves mechanisms of edge formation outside its scope.

Datasets: The study analyzes 12-layer directed social-support networks from two Tamil Nadu villages and a 9-layer undirected malaria-gene network spanning highly variable regions.The village networks contain N = 362 and N = 420 nodes; the malaria network contains N = 307 genes.
Scope: The authors state that mechanisms involving kinship, caste, promoter sequence, or parasite origin are beyond this paper’s scope, which focuses on algorithm effectiveness.The Tenpat.t.i partition partially overlaps caste membership, but the authors do not treat that correlation as an accuracy measure.
Social support networks: Social-network link-prediction AUC increases monotonically as additional layers enter the training dataset.The best group counts are K = 4 for the first village and K = 6 for the second.
Social support networks: AUCs for many social-support layers start just above 0.5, improve by about 0.05 with one added layer, and improve significantly with two or all additional layers.The greedy procedure selects added layers for L = 2 and L = 3.
Social support networks: The ImpIss layer helps predict many social-support layers, whereas Position, Work, Loan, and Babysit contribute less and are among the hardest layers to predict.Affinity-matrix clustering places these four layers farther from the others, suggesting structurally distinct layers.
Malaria network: In the malaria network, prediction is best without adding other layers and worsens monotonically as layers are added, indicating independent layer structure.The figure reports AUC averages and standard deviations over 5 cross-validation folds.

VII. CONCLUSIONS

The paper presents MULTITENSOR, a scalable generative model and expectation-maximization algorithm for multilayer community detection and link prediction. It quantifies layer interdependence through cross-layer prediction and applies the framework to networks with varied structure, including overlapping, directed, weighted, assortative, and disassortative cases.

Model and algorithm: MULTITENSOR extends the mixed-membership stochastic block model with shared overlapping communities and layer-specific assortative, disassortative, core-periphery, hierarchical, or mixed structures.It supports directed, undirected, and integer-weighted links.
Model and algorithm: A scalable expectation-maximization algorithm fits the model in time linear in total dataset size per iteration and converges quickly in practice.The model performs well on synthetic and real data for community detection and link prediction.
Layer interdependence: Layer interdependence is defined quantitatively by how much knowledge of one layer or a layer set improves link prediction in another layer.The same cross-validation framework can also help identify and avoid overfitting.
Implications: The framework can identify redundant layers and small layer sets that capture most information about the network, supporting decisions about which layers to collect or combine.The authors also note possible use in choosing weights for multilayer network measures.