Source-linked AI summary
Layer aggregation and reducibility of multilayer interconnected networks
M. De Domenico, V. Nicosia, A. Arenas, V. Latora
TL;DR
Multilayer networks raise the question of how many distinct layers are needed to represent a system accurately. The paper introduces an information-theoretic aggregation method based on entropy, Jensen–Shannon distances, hierarchical clustering, and quality maximization, finding that reducibility varies across synthetic and biological networks.
Problem
The paper asks how much information is necessary to represent multilayer systems and whether layers can be aggregated without a sensible information loss.
Method
The method compares layer similarity with quantum Jensen–Shannon distances, hierarchically clusters layers, and selects the partition maximizing relative information gain.
Results
Synthetic benchmarks aggregate highly overlapping layers first, while biological networks range from non-reducible cases to networks where redundant layers can be merged.
Takeaways & Limitations
The method provides a practical way to choose between preserving separate layers and reducing them, depending on their redundancy and structural similarity.
Abstract
from arXiv · showhide
Many complex systems can be represented as networks composed by distinct layers, interacting and depending on each others. For example, in biology, a good description of the full protein-protein interactome requires, for some organisms, up to seven distinct network layers, with thousands of protein-protein interactions each. A fundamental open question is then how much information is really necessary to accurately represent the structure of a multilayer complex system, and if and when some of the layers can indeed be aggregated. Here we introduce a method, based on information theory, to reduce the number of layers in multilayer networks, while minimizing information loss. We validate our approach on a set of synthetic benchmarks, and prove its applicability to an extended data set of protein-genetic interactions, showing cases where a strong reduction is possible and cases where it is not. Using this method we can describe complex systems with an optimal trade--off between accuracy and complexity.
QUANTIFYING THE INFORMATION CONTENT OF A MULTIPLEX NETWORK
The paper uses quantum-information concepts to quantify information in multiplex networks. Each layer is represented through graph-based matrices, allowing the multilayer system’s entropy to be computed from a normalized Laplacian supra-matrix.
- A multilayer network can be treated as an ensemble of possible system states, with its information quantified using Von Neumann entropy.Each layer represents one possible state, and the full network is described as an ensemble of states.
- A multiplex network is an edge-colored multigraph represented by a set of layer-specific adjacency matrices.The representation assumes inter-layer connections between node replicas but does not define or use their weights.
- The adjacency matrices are placed on the diagonal of a block supra-adjacency matrix, with zero off-diagonal blocks.This constructs a flattened representation of the multilayer adjacency tensor.
- The multiplex entropy hA is computed from the N × M eigenvalues of the normalized Laplacian supra-matrix.For an edge-colored multigraph, this entropy reduces to the sum of the Von Neumann entropies of the individual layers.
QUANTIFYING THE INFORMATION LOSS IN (PARTIALLY) AGGREGATED MULTIPLEX NETWORKS
The method measures information loss from aggregating layers and searches for a reduced representation that maximizes retained information. It uses Jensen–Shannon distances and hierarchical clustering to avoid exhaustive enumeration of all layer partitions.
- Aggregating a multiplex into one graph can reduce storage and computational requirements, motivating a test of whether separate layers provide necessary information.The required space and computational power increase at least linearly with the number of layers.
- The fully separated multiplex and aggregated graph are compared through their Von Neumann entropies, with a rescaling factor M − 1 for correct comparison.The separated representation is denoted N, the aggregated graph L, and their entropies are h⊗ and h⊕.
- The relative entropy q(M) measures the additional information provided by an M-layer multiplex compared with its aggregated graph.Identical layers give q(M) = 0, whereas higher q(M) indicates a more informative multilayer representation.
- Because exhaustive optimization over all layer partitions is NP-hard, the method uses quantum Jensen–Shannon distances to hierarchically cluster similar layers.The resulting dendrogram represents candidate layer merges while avoiding enumeration of every partition.
- The procedure computes pairwise Jensen–Shannon distances, clusters layers hierarchically, evaluates relative entropy, and selects the partition maximizing information gain.The process stops at the partition with the highest quality function value.
Layer aggregation of synthetic multiplex networks
Synthetic benchmarks show that the procedure aggregates similar, highly overlapping layers first while retaining distinct layers when their redundancy is low. In the rewiring benchmark, the best representation keeps all layers separate.
- The benchmark rewires different percentages of edges from an initial layer, producing layers with increasing edge overlap.The clustering procedure first merges layers associated with less than 50% edge rewiring, then merges layers with higher rewiring.
- The relative entropy q(•) decreases monotonically during aggregation, indicating that the best representation keeps all layers distinct.This behavior holds in the reported rewiring benchmark.
- An overall edge overlap smaller than 5% corresponds to relatively low average redundancy between layer pairs.Each rewired layer carries information not included in the others, regardless of the fraction of edges rewired.
- Layers with high overlap and similar topology tend to be aggregated first, supporting the procedure’s minimum-information-loss principle.The benchmark results link early aggregation to structural similarity between layers.
Layer aggregation of multilayer biological networks
The procedure evaluates whether layers in multilayer biological networks carry redundant information and identifies partitions that balance reduced complexity against information loss. BioGRID networks show organism-specific reducibility: some layers can be aggregated, while others should remain distinct.
- The method was applied to protein-genetic interaction multiplex networks from 13 BioGRID organisms.The data represent different types of genetic interactions as separate layers.
- C. elegans has no advisable layer aggregation because the quality maximum occurs with all six layers distinct.
- Mus and Candida contain layer pairs with redundant information that can be aggregated without sensible information loss.
- Saccharomyces cerevisiae and Drosophila melanogaster show a global quality maximum after two hierarchical merges.
- The European airport multiplex could not be reduced to fewer layers, indicating nonredundant connectivity for each airline.
- Across the 13 organisms, the quality function identifies partitions that minimize layer redundancy at the cost of a small information loss.
Von Neumann entropy of single-layer networks
The Von Neumann entropy of a graph is defined from its normalized Laplacian and can equivalently be expressed using that matrix’s eigenvalues.
- The Von Neumann entropy of graph G is defined using its normalized Laplacian LG.LG is constructed from the identity matrix, node-degree matrix, and adjacency matrix.
- The normalized Laplacian is LG = I − D^-1A, where I is the identity matrix and D contains node degrees.
- The entropy can be written in terms of the eigenvalues λ1, λ2, . . . , λN of LG.
Jensen–Shannon distance between graphs
The Jensen–Shannon distance provides a symmetric metric for comparing graph-associated density operators and their normalized Laplacian matrices in information terms.
- The Kullback–Leibler divergence measures information gained about σ when expectations are based on ρ.
- The Jensen–Shannon divergence is symmetric, while the Kullback–Leibler divergence is neither symmetric nor a metric.
- The Jensen–Shannon divergence uses the mixture μ = 1/2(ρ + σ) of two density operators.
- The square root of the Jensen–Shannon divergence is a metric with values in [0, 1].It quantifies information gain or loss between normalized Laplacian matrices associated with distinct networks.
Hierarchical clustering
Layers are hierarchically clustered using Jensen–Shannon distances, producing candidate aggregations whose quality can be evaluated across the resulting dendrogram.
- Layers with small Jensen–Shannon distance are hypothesized to be safely mergeable into a single layer.
- Hierarchical clustering repeatedly aggregates the closest layer clusters and updates distances using Ward’s linkage.
- After M − 1 iterations, the procedure produces a dendrogram with original layers as leaves and layer merges as internal nodes.
- The dendrogram’s root represents the fully aggregated graph.