Source-linked AI summary
Growing multiplex networks
Vincenzo Nicosia, Ginestra Bianconi, Vito Latora, Marc Barthelemy
TL;DR
The paper analyzes how degree structure evolves in growing multiplexes under different attachment, coupling, and arrival-time settings. It develops mean-field and master-equation treatments and finds that delays, attachment rules, and edge-count fluctuations produce distinct degree-distribution behavior.
Problem
The paper examines the time evolution of node degrees and degree distributions across layers in growing multiplexes under different modeling conditions.
Method
The authors use mean-field and master-equation approaches to derive degree distributions and inter-layer degree correlations for multiplex growth models, including delayed layer arrival.
Results
The resulting topology depends on attachment rules and delays: linear attachment yields P(k) ∼k−3, semi-linear attachment can yield exponential degree distributions, and delayed-arrival effects vary with β.
Takeaways & Limitations
At large times, random variation in the number of added edges becomes negligible, while delay width and attachment structure remain important determinants of multiplex degree behavior.
Takeaways & Limitations
The master-equation treatment assumes that, at large t, the probability of a node acquiring links simultaneously in both layers can be neglected.
Abstract
from arXiv · showhide
We propose a modeling framework for growing multiplexes where a node can belong to different networks. We define new measures for multiplexes and we identify a number of relevant ingredients for modeling their evolution such as the coupling between the different layers and the arrival time distribution of nodes. The topology of the multiplex changes significantly in the different cases under consideration, with effects of the arrival time of nodes on the degree distribution, average shortest paths and interdependence.
Mean-field theory
The paper uses a mean-field approach to analyze how multiplex node degrees evolve across layers. It derives long-time degree distributions and inter-layer degree correlations for several growth cases.
- The analysis first treats linear attachment, then semi-linear attachment, and finally random numbers of new edges.These cases organize the model's mean-field treatment.
- The approach focuses on degree evolution, layer-specific degree distributions, and correlations between degrees across layers.
Linear attachment kernel on both layers
For linear attachment without delay, the model represents cross-layer coupling with a coefficient matrix and analyzes degree evolution through a solvable linear dynamical system. When layers evolve independently, each layer has a power-law degree distribution with exponent γ = 3.
- The attachment probability can depend on the degrees of a node's replicas across multiplex layers.
- For simultaneous arrivals, replica degrees evolve according to a linear system governed by the coupling matrix C.The matrix coefficients are constrained by nonnegative entries and row sums equal to 1.
- The system is solved using eigenvalues, eigenvectors, diagonalization, and a state-transition matrix determined by the node's initial state and arrival time.
- When a = 1 and b = 0, the two layers evolve independently.
- γ = 3 for each layer's power-law degree distribution when both layers use linear attachment without delay.
Semi-linear attachment kernel
The semi-linear attachment case is formulated as a time-varying linear system, with solutions and degree distributions depending on the coupling parameters. Special parameter choices can produce exponential or parameter-dependent distributions.
- The semi-linear attachment dynamics are represented by a non-homogeneous time-varying linear system with an external forcing function.
- The corresponding homogeneous system uses a state-transition matrix whose form depends on the coupling parameter a.
- The degree distributions are derived from the mean-field temporal evolution of the layer degrees.
- When a = 0, the first-layer degree distribution is exponential, P(k[1]) ∼e−k.
- When a = 0 and b > 0, the functional form of the second-layer degree distribution depends on b.
Fluctuations in the number of edges
The framework can be extended to nodes bringing a random number of edges per layer. At large times, the system's behavior is governed by the average number of added edges rather than this randomness.
- Each new node may bring a random number ξ[α] of edges on layer α, drawn from a specified distribution.The resulting dynamics can be represented by stochastic differential equations.
- At large times, randomness in the number of edges becomes negligible, and the behavior is governed by the average ⟨ξ[α]⟩ added in each layer.
Master Equation approach for the model without delay
The model uses a master equation to derive the joint degree distribution for a multiplex growing synchronously across two layers. It tracks nodes by their degrees in both layers while assuming simultaneous acquisition of links in both layers is negligible at large times.
- The analysis defines N_k,q(t) as the average number of nodes with degree k in layer 1 and degree q in layer 2.
- Each arriving node adds m edges simultaneously to layer 1 and m edges to layer 2.
- Attachment probabilities depend on the target node’s degrees in both layers through layer-specific kernels Π and Π[2].
- For t ≫1, the model assumes Ak,q/t and Bk,q/t are sufficiently small to neglect simultaneous link acquisition in both layers.
- Assuming N_k,q=tP(k,q) at large times yields master equations for the joint probability that a node has degrees k and q across the two layers.
Solution of the master equation in three simple cases
The master equation is solved for three attachment kernels, producing recursive expressions for the joint and marginal degree distributions. The resulting forms depend on the selected kernel and can be summed across layers to obtain single-layer distributions and conditional mean degrees.
- Linear attachment kernel: Linear attachment uses c[1,1]=c[2,2]=1 and c[1,2]=c[2,1]=0, with normalization fixing P(m,m).
- Summing the joint distribution over layer-2 degree produces the layer-1 degree distribution P(k).
- Analogous summation yields P(q) and the conditional mean degree ⟨q(k)⟩.
- Uniform attachment kernel: Uniform attachment is characterized by equal target-selection probability and its own recursive master equations.
- Linear attachment kernel: The linear case is solved recursively for the joint distribution P(k,q).
- Semi-linear attachment kernel: The semi-linear case is likewise reduced to recursive equations whose solution gives the joint distribution.
Role of β in the delayed arrival
The delay-width parameter β controls how delayed node arrivals shape the high-degree tail. Larger β moves the maximum-degree growth exponent toward the synchronous-arrival value and broadens the rightmost degree-distribution region.
- kM(t) ∼(t/s)^δ, and increasing β makes δ approach 0.5, the synchronous-arrival value.
- When β is close to 1, the rightmost part of the degree distribution is broader; as β decreases, it becomes more similar to P(k) ∼k^-3.
Finite size effects
The model’s large-size mean-field predictions remain qualitatively accurate for relatively small multiplexes. Simulations with N = 1000 show degree distributions and inter-layer degree correlations similar to the large-N predictions.
- Mean-field predictions for degree distributions and inter-layer degree correlations are formally valid in the large-N limit.
- For N = 1000, degree distributions and inter-layer degree-degree correlations remain similar to the large-N predictions.
Time complexity
The multiplex-sampling algorithm constructs cumulative probabilities and samples candidate neighbours by binary search, yielding complexity linear in layers and quadratic in nodes.
- Time complexity: O(t) construction plus O(m log(t)) sampling gives O(N^2 + mN log(N)) operations for one layer.The cumulative-probability vector is rebuilt at each time, while each sampled edge uses binary search.
- Time complexity: O(M(N^2 + mN log(N))) steps are required to construct an M-layer multiplex.The cost scales linearly with the number of layers.
- Time complexity: For fixed m, the algorithm is dominated by O(MN^2), making it linear in layers and quadratic in nodes.The authors note that smarter updates to the cumulative-probability array could improve the construction algorithm.
Randomly-chosen master layer
The randomly-chosen master-layer variant assigns each node's master layer uniformly among the multiplex layers. Its degree distributions and hub scaling remain similar to the equal-master-layer case, while shortest paths and interdependence differ in characteristic ways.
- Randomly-chosen master layer: RML chooses each node's master layer uniformly with probability p = 1/M among the M layers.A node then arrives on the other layer after a power-law distributed delay.
- Layer balance: The random choice of master layer produces a more balanced distribution of super hubs between the two layers.The reported impact extends to the resulting network’s structural distributions.
- Degree distributions: The random master-layer choice does not sensibly change the degree-distribution shape for β = 1.1 and β = 2.0.The comparison covers EML and RML degree distributions on the first layer.
- Hub scaling: The largest-hub degree scales as (t/s)^δ, with δ approaching 0.5 as β increases and taking values similar to EML.This is the temporal-scaling result reported for RML.
- Distances and interdependence: For RML, shortest-path lengths resemble synchronous arrival more closely, whereas node interdependence deviates from synchronous arrival and differs from EML.The figure compares both distributions across RML, EML, and synchronous-arrival cases.