Source-linked AI summary
Multilayer stochastic block models reveal the multilayer structure of complex networks
Toni Valles-Catala, Francesco A. Massucci, Roger Guimera, Marta Sales-Pardo
TL;DR
Real-world interaction data can collapse multiple layers into one aggregate, obscuring the original layer structure. The paper generalizes SBMs to model different aggregation mechanisms and approximates an intractable complete inference solution; its results suggest that many real-world networks are projections of multiple layers.
Problem
Observed aggregate networks lose information about their underlying interaction layers, leaving the layer structure to be inferred from the aggregate.
Source: §I · p. 1Method
The paper introduces multilayer SBMs and an approximation that represents them through an intersection partition to make inference tractable.
Source: §I · p. 1, §II · pp. 2–3Results
Multilayer SBM predictions are consistently more accurate for real networks, slightly but significantly in most cases and especially at low observational noise; the results suggest many are multilayer projections.
Source: §IV · p. 5, §V · p. 5Takeaways & Limitations
The approximation provides a way to assess whether observed networks are better described as projections of multiple layers or as single-layer networks.
Source: §V · p. 5Under the approximation, partitions with the same intersection partition are equally likely, so the multilayer SBM cannot be uniquely identified.
Source: §II · p. 3
Abstract
from arXiv · showhide
In complex systems, the network of interactions we observe between system's 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.
I. MULTILAYER STOCHASTIC BLOCK MODELS
The multilayer SBM models nodes as belonging to groups in distinct layers, with group-dependent link probabilities, while the observed network aggregates the layers and loses their identities. For two layers, the section defines AND and OR aggregation and formulates inference as finding the layer partitions most probable given the aggregate network.
I. MULTILAYER STOCHASTIC BLOCK MODELS
- Each layer has its own node groups and group-dependent link probabilities, while aggregation produces an observed adjacency matrix that loses layer information.The model is called the multilayer SBM.Source: §I · p. 1
- For two layers, AND aggregation retains links present in both layers, whereas OR aggregation retains links present in at least one layer.The paper gives protein interactions as a plausible AND example and meme sharing across platforms as a plausible OR example.Source: §I · pp. 1–2
- Inference seeks the joint probability of the layer partitions given the aggregate network, so the most probable partition pair identifies the best-fitting multilayer SBM.The link probabilities are defined for pairs of groups in each layer.Source: §I · p. 2
- For the AND model, independent links must be present in both layers to appear in the aggregate, and the likelihood is integrated over link probabilities using a uniform prior.The calculation uses counts of links and non-links across the layer-group combinations.Source: §I · p. 2
- Although the complete probabilistic solution defines the inference target, evaluating it is numerically intractable even with a small number of groups.In principle, maximizing the posterior would identify the layer partitions and enable comparison with regular SBMs.Source: §I · p. 2
II. LINK RELIABILITY WITH APPROXIMATE MULTILAYER STOCHASTIC BLOCK MODELS
The section approximates multilayer link reliability by representing aggregated layers through an intersection partition, then evaluating predictions over those partitions. Its independence assumption makes this computation tractable but prevents uniquely identifying the underlying multilayer SBM.
II. LINK RELIABILITY WITH APPROXIMATE MULTILAYER STOCHASTIC BLOCK MODELS
- For AND aggregation, a multilayer SBM maps to a single-layer SBM whose groups are intersections of layer groups and whose connection probabilities are products of layer probabilities.The mapping fully determines the equivalent single-layer SBM.Source: §II · p. 2, Figure 2 · p. 3
- The approximation treats the intersection SBM's probability-matrix elements as independent, making all layer-partition pairs with the same intersection partition equally likely.Consequently, the approximation cannot uniquely determine the multilayer SBM that best describes the observed topology.Source: §II · p. 3
- Link reliability is the probability that a node pair truly has a link given a noisy observation, and the method assesses it for detecting missing and spurious links.The assessment compares a removed link's reliability with that of absent links, or an added link's reliability with that of original links, using AUC.Source: §II · p. 3
- Under this approximation, link reliability is computed by summing over single-level intersection partitions rather than pairs of layer partitions.The expression accounts for the number of layer-partition pairs that yield each intersection partition.Source: §II · p. 3
- A Markov Chain Monte Carlo algorithm computes link reliability numerically, with the intersection-partition energy interpreted as an ensemble-average quantity.The energy includes the single-SBM term plus a term arising from product-form probabilities; the authors interpret this term and partition degeneracy as non-uniform priors.Source: §II · pp. 3–4
III. VALIDATION OF LINK RELIABILITY ESTIMATION IN MODEL NETWORKS
The authors compare single-layer and two-layer SBMs on synthetic networks aggregated with AND and OR models. Two-layer approaches generally improve missing- and spurious-link detection, with performance depending on the aggregation and network structure.
III. VALIDATION OF LINK RELIABILITY ESTIMATION IN MODEL NETWORKS
- The tests use two-layer networks with clearly differentiated block structures, aggregated according to AND or OR.The comparison evaluates single- and two-layer approaches for detecting missing and spurious interactions.Source: §III · p. 4
- Two-layer SBMs outperform single-layer SBMs for AND networks under small or moderate noise and in most tested OR-network situations.For AND networks, the advantage is strongest as intersection-group count and connectivity grow.Source: §III · p. 4
- Only for very blurry AND-network blocks does the single-layer approach perform better, and all approaches perform poorly there.Source: §III · p. 4
- For OR networks, the largest two-layer improvements occur in hard cases with lower connectivity, while OR aggregation tends to produce dense networks and AND aggregation sparser ones.Source: §III · pp. 4–5
IV. MULTILAYER STOCHASTIC BLOCK MODELS ARE MORE PREDICTIVE FOR REAL NETWORKS
On three real-world networks, the authors compare single-layer models with a two-layer AND model. The two-layer model detects missing and spurious interactions more accurately, though its improvements are slight and most often significant at low observational noise.
IV. MULTILAYER STOCHASTIC BLOCK MODELS ARE MORE PREDICTIVE FOR REAL NETWORKS
- The evaluation covers the Eastern European air transportation network, the C. elegans neural network, and a university email network.Source: §IV · p. 5
- The two-layer AND model consistently detects missing and spurious interactions more accurately than the single-layer approach on the three real-world networks.Source: §IV · p. 5
- The improvement is slight but significant in most cases, especially when observational noise is low.Source: §IV · p. 5
V. DISCUSSION
The discussion presents multilayer SBMs as a way to infer hidden layers from aggregate networks, with a tractable approximation supporting the conclusion that many real networks are projections. It distinguishes this task from inference on networks with observed layers and from latent-feature link prediction.
V. DISCUSSION
- The authors propose a tractable approximation to the probabilistically complete solution for inferring an optimal multilayer SBM from an aggregate network, and results suggest many real networks are projections.Source: §V · p. 5
- Unlike inference on multigraphs with observed layers, this work learns multilayer models from aggregate networks where layer information has been lost.Source: §V · p. 5
- Latent-feature models use weighted sums of layer interactions for link probabilities, but their parameters do not give a physical interpretation of layers or their combination.Source: §V · p. 5
- The proposed multilayer SBM is the simplest group-based multilayer model the authors identify.Source: §V · p. 5