Statistical Mechanics of Multiplex Ensembles: Entropy and Overlap

Ginestra Bianconi

Source-linked AI summary

Statistical Mechanics of Multiplex Ensembles: Entropy and Overlap

Ginestra Bianconi

arXiv:1303.4057v2Mar 17, 2013cond-mat.dis-nncond-mat.stat-mechphysics.soc-ph

TL;DR

Multiplexes often contain overlapping links across simultaneously shared network layers, but existing network methods require extension to capture their structure. The paper develops microcanonical and canonical multiplex ensembles, distinguishes correlated from uncorrelated cases, and derives their entropy for inference applications.

Problem
Existing statistical-mechanics methods for networks must be extended to analyze multiplex data with links distributed across multiple layers and potentially significant overlap.
Method
The paper constructs microcanonical and canonical multiplex ensembles with hard or soft constraints, using correlated formulations to model interlayer link dependence and overlap.
Results
The paper characterizes uncorrelated and correlated multiplex ensembles and provides entropy expressions for these ensembles.
Takeaways & Limitations
The framework provides null models for multiplexes, including models with significant global or local overlap, and supports inference problems involving multiplexes.

Abstract

from arXiv · show

There is growing interest in multiplex networks where individual nodes take part in several layers of networks simultaneously. This is the case for example in social networks where each individual node has different kind of social ties or transportation systems where each location is connected to another location by different types of transport. Many of these multiplex are characterized by a significant overlap of the links in different layers. In this paper we introduce a statistical mechanics framework to describe multiplex ensembles. A multiplex is a system formed by N nodes and M layers of interactions where each node belongs to the M layers at the same time. Each layer $α$ is formed by a network $G^α$. Here we introduce the concept of correlated multiplex ensembles in which the existence of a link in one layer is correlated with the existence of a link in another layer. This implies that a typical multiplex of the ensemble can have a significant overlap of the links in the different layers. Moreover we characterize microcanonical and canonical multiplex ensembles satisfying respectively hard and soft constraints and we discuss how to construct multiplex in these ensembles. Finally we provide the expression for the entropy of these ensembles that can be useful to address different inference problems involving multiplexes.

I. INTRODUCTION

Multiplex systems combine several network layers, motivating statistical-mechanics null models that represent interlayer overlap and correlations. The paper defines multiplex ensembles, their entropy, and correlated versus uncorrelated constructions.

Multiplexes represent systems in which the same nodes participate simultaneously in multiple network layers, including social, transportation, climatic, economic, energy, and brain networks.
Further theoretical frameworks are needed to extract information from multiplex and interacting-network data.
Network ensembles provide randomized null models under hard microcanonical or average canonical structural constraints.
Multiplex entropy measures the logarithm of the typical number of multiplexes satisfying an ensemble’s constraints and can support inference problems.
The paper treats multiplex ensembles as null models, distinguishing factorized uncorrelated ensembles from correlated ensembles with interlayer link dependence.
Multilinks encode which layers connect each node pair, while global and local overlap count shared links between two layers.

IV. CANONICAL MULTIPLEX ENSEMBLES OR EXPONENTIAL RANDOM MULTIPLEXES

Canonical multiplex ensembles model soft structural constraints by maximizing entropy, producing probabilities determined by constraints and a partition function. The framework supports uncorrelated and correlated ensembles, with entropy decreasing as constraints are added.

Canonical multiplex ensembles contain multiplexes satisfying structural constraints in average and are constructed by maximizing ensemble entropy.
The resulting multiplex probability has an exponential form normalized by the canonical partition function, whose Lagrange multipliers enforce the soft constraints.
Uncorrelated canonical ensembles require constraints expressible as combinations of functions defined separately on individual layers.
Correlated canonical ensembles can constrain expected overlap, expected multilinks, multidegree sequences, or combinations involving community structure.
Adding constraints is expected to reduce the typical number of multiplex realizations and therefore decrease ensemble entropy.
Multiplex entropy provides a first-principles measure of ensemble complexity that can be used in inference problems.
For fixed average links per layer, the canonical ensemble’s Shannon entropy is expressed through the layer link probabilities pα = 2Lα/[N(N −1)].

2. Multiplex ensemble with given expected degree sequence in each layer

This section develops uncorrelated canonical multiplex ensembles by constraining expected degrees, optionally adding community-level link counts, and derives their Shannon entropies.

The ensemble fixes the expected degree kα_i of every node i in each layer α using M × N constraints.
The canonical probability is expressed through a partition function and Lagrange multipliers enforcing the expected-degree constraints.
The resulting Shannon entropy is obtained from the multiplex probability distribution for the degree-constrained ensemble.
In the sparse large-network limit, each layer is uncorrelated and e^-λi,α ≃ ⟨kα⟩N.
Community-aware variants additionally constrain expected links between communities, with probabilities depending on node communities and layer.
Their Shannon entropies are likewise derived from the corresponding canonical probabilities, including a large-N expression when the constraint count is non-extensive.

C. Properties of the uncorrelated canonical multiplex ensembles under consideration

The section examines overlap in uncorrelated canonical multiplex ensembles and finds that it is negligible in the sparse large-network regime, even when degree correlations are considered under stated conditions.

The average global and local overlaps between two layers are calculated for the considered uncorrelated multiplex ensembles.
For fixed expected layer link counts, if Lα = O(N) for every layer, global overlap remains finite while local overlap vanishes as the network grows.
Consequently, overlap is negligible relative to the total number of links in either layer in this sparse regime.
When degree sequences across layers are uncorrelated, the global and local overlaps follow the corresponding uncorrelated expressions.
Degree correlation between layers can enhance overlap, but the section still reports negligible overlap under the stated asymptotic conditions.

D. Construction of a uncorrelated multiplex in an uncorrelated canonical multiplex ensemble under consideration

Uncorrelated canonical multiplexes are generated by independently sampling every layer after calculating each layer’s link probabilities; correlated ensembles instead require multilink-based probabilities.

In uncorrelated ensembles, the multiplex probability factorizes into the probabilities of the individual layer networks.
Construction first calculates pα_ij for each node pair and layer, then independently places each link with that probability.
If the multiplex probability does not factorize, links across layers can be correlated and ordinary layer-wise sampling is insufficient.
Correlated multiplexes are represented with multilinks, encoding the combination of layers in which each node pair is connected.
For correlated canonical ensembles, expected multilink counts are imposed through constraints, a partition function, and Lagrange multipliers determining multilink probabilities.
The Shannon entropy is then calculated from the correlated multiplex probability distribution and has a finite-layer expression.

2. Multiplex ensemble with given expected multidegree sequence

This section extends correlated canonical multiplex ensembles by fixing expected multidegree sequences and community-specific multilink counts, then derives their probabilities and entropies.

The ensemble can constrain the expected multidegree k⃗m_i of every node, with separate constraints for multilink types and nodes.
Canonical multiplex probabilities use a partition function and Lagrange multipliers that enforce the multidegree constraints and determine multilink probabilities.
The corresponding Shannon entropy is calculated from this constrained probability distribution.
In the sparse limit, the entropy has a specialized expression for multilinks containing at least one layer link.
A further correlated ensemble constrains expected multilinks between nodes in different communities, with probabilities depending on community labels and multilink type.
Its entropy is derived from the canonical distribution, with a large-N form when the number of constraints is non-extensive.
Related uncorrelated variants combine node-level expected multidegrees with community-pair multilink counts and derive their canonical probabilities and Shannon entropies.

F. Overlap in correlated canonical ensembles under consideration

Correlated canonical multiplex ensembles produce layer-dependent probabilities that cannot be factorized across individual layers, while retaining a simple joint form. Their global and local link overlaps can therefore remain significant even when layers are sparse.

Correlations between layers prevent the multiplex probability PC(G⃗) from factorizing into probabilities for individual layers.
The correlated ensembles considered retain a simple expression for the joint multiplex probability.
The Shannon entropy S of these ensembles also takes a simple form.
Average total and local overlaps between two layers can be calculated within the considered ensembles.
Significant global and local overlap can persist in sparse two-layer multiplexes.The paper identifies this behavior in the case M = 2.

G. Case of a two layers multiplex, i.e. M = 2

For correlated two-layer multiplex ensembles, multilink probabilities define the joint network and its entropy, while overlap remains non-negligible under sparse-network conditions. Canonical construction samples one multilink independently for each node pair, whereas microcanonical ensembles impose graphical hard constraints.

The entropy of the two-layer correlated multiplex is determined from the joint multilink probabilities.
The ensembles define both average total overlap and average local overlap between the two layers.
Assuming L11, L10, and L01 scale with N, overlapping links remain non-negligible globally and locally even when both layers are sparse.
Provided that ⟨k11⟩ is finite, global and local overlap can likewise remain significant for ensembles fixing expected multidegrees.
Canonical correlated multiplexes are constructed by calculating multilink probabilities and sampling one multilink for every node pair.Each sampled multilink places links in exactly the layers whose multilink components equal one.
Microcanonical multiplex ensembles contain equally probable multiplexes satisfying graphical hard constraints.
The microcanonical partition function counts multiplexes satisfying the hard constraints, and nonzero Ω indicates nonequivalence with the conjugated canonical ensemble as N becomes large.

A. Uncorrelated microcanonical multiplex ensembles

Uncorrelated microcanonical multiplex ensembles factor across layers when each hard constraint concerns only one layer. Their Gibbs entropy decomposes into layer entropies, with equivalence to canonical ensembles depending on constraint growth and the ensemble considered.

An uncorrelated multiplex has a probability that factorizes into the probabilities of its single-layer networks.
Microcanonical uncorrelatedness requires every hard constraint to involve only one layer.
The multiplex Gibbs entropy decomposes into the Gibbs entropies of the layer-specific network ensembles.
Given total number of links in each layer: When the number of constraints M is sublinear in N, the fixed-link microcanonical and canonical ensembles are equivalent in the thermodynamic limit, with Σ ≃ S/N.
Given degree sequence in each layer: For fixed degree sequences in each layer, finite M yields Σ = S/N − Ω for sparse networks, so the microcanonical and conjugated canonical ensembles are not equivalent.
Given degree sequence in each layer: The resulting entropy expression generalizes the Bender formula for networks with a given degree sequence.

3. Multiplex ensemble with given number of links in each layer between nodes of different communities

Community-constrained uncorrelated multiplex ensembles fix intercommunity link counts, with partition functions and Gibbs entropies obtained layer by layer. In the sparse large-network limit, equivalence with canonical ensembles requires a sublinear number of constraints.

Each node is assigned a community label, and the ensemble fixes the number of links between every pair of communities in each layer.
The partition function counts multiplexes by multiplying, across layers, the numbers of networks satisfying the intercommunity link constraints.
For each community pair, the number of admissible links is selected from the possible links between those communities.
The Gibbs entropy for this ensemble is obtained from the corresponding microcanonical counting expression.
The entropy satisfies Σ = S/N in the large-network limit only when the number of constraints P is sublinear in N.
A related ensemble can simultaneously fix every node’s degree in each layer and the intercommunity link counts.
For the combined degree-and-community constraints, the Gibbs entropy is expressed using the canonical entropy and a correction term Ω.

5. Multiplex with given degree-degree correlations in each layer α

This section constructs multiplex ensembles with specified degree-degree correlations in each layer and derives their entropy properties. It distinguishes correlated from uncorrelated layers and examines when microcanonical and canonical descriptions agree.

Construction: A microcanonical uncorrelated multiplex ensemble can fix degree-degree correlations separately within each layer.The construction fixes each node’s degree and the number of links between nodes of specified degrees in layer α.
Entropy: For sparse networks, the entropy of each layer is expressed through its typical ensemble size and Shannon entropy.The section introduces the entropy expression for large variations and the corresponding layer-level Shannon entropy.
Correlations: Correlated multiplex ensembles have non-factorizable probabilities, so link configurations across layers are statistically dependent.This dependence permits overlap between links in different layers.
Correlated ensembles: The fixed-total-multilink correlated ensemble has a multinomial count of multiplexes, whose logarithm gives the Gibbs entropy.Every node pair is assigned one multilink, producing the stated total number of multiplexes.
Ensemble equivalence: When K = 2M constraints is sublinear in N, the microcanonical and conjugated canonical ensembles are equivalent as N becomes large.In this limit, the Gibbs entropy per node satisfies Σ ≃ S/N.
Ensemble equivalence: For fixed multidegrees in sparse multiplexes with finite M, Σ = S/N − Ω, so microcanonical and canonical ensembles are not equivalent thermodynamically.Here Ω remains finite in the large-network limit.

3. Multiplex ensemble with given number of multilinks⃗m in between nodes of different communities

This section studies correlated multiplex ensembles constrained by multilinks between communities. It derives their multiplex counts and entropy, and identifies constraint scaling as the condition governing microcanonical–canonical equivalence.

Construction: The ensemble assigns each node a community label and fixes multilink counts between every pair of communities.The constraints are required to be graphical and are indexed by multilink type and community pair.
Ensemble equivalence: When the number of constraints P is sublinear in N, the microcanonical and canonical ensembles are equivalent in the thermodynamic limit.Their entropies satisfy Σ ≃ S/N.
Scope: The framework supports multiplex ensembles with multilink, multidegree, and community-based constraints in both microcanonical and canonical forms.These constructions are part of the paper’s broader statistical-mechanics treatment of multiplex ensembles.
Entropy: For sparse networks, the entropy correction Ω is characterized using a Poisson distribution with an average determined by the constraints.The resulting expression applies when the number of constraints grows proportionally to N.
Ensemble equivalence: When constraints are extensive, the microcanonical and canonical ensembles are not equivalent.The conclusion extends this non-equivalence to multiplex ensembles with extensive constraint sets.