Temporal networks with node-specific memory: unbiased inference of transition probabilities, relaxation times and structural breaks

1. Problem Statement

The study of time-varying (temporal) networks faces a critical challenge: the interplay between structural heterogeneity (different nodes and dyads having distinct statistical properties) and memory effects (link persistence over time).

• The Issue: Traditional models often assume homogeneous memory or ignore it entirely, leading to a superposition of timescales, sub-optimal parametrizations, and substantial estimation biases.
• The Gap: Existing methods struggle to disentangle hidden variables that jointly determine static network properties (like degree) and temporal properties (like link persistence). Furthermore, real-world networks often undergo structural breaks (sudden shifts in dynamics due to exogenous events), rendering stationary models invalid over long periods.

2. Methodology

The authors develop an unbiased Maximum Entropy (MaxEnt) framework to model empirical network trajectories. The methodology proceeds in four main stages:

A. Maximum Entropy Framework for Temporal Networks

The authors extend the Binary Configuration Model (BCM) to time-varying graphs. They define the probability distribution $P(G)$ of a graph trajectory $G = \{G_1, ..., G_T\}$ by maximizing the Shannon-Gibbs entropy subject to constraints on observed quantities.

• Constraints: They test models with varying levels of heterogeneity:
  1. Memory-less models: Constraints on time-averaged links, time-averaged degrees, or global average degrees.
  2. Memory models: Constraints on persisting connectivity (links existing at time $t$ and $t+1$) and persisting degrees (the number of links a node maintains over time).

B. Mapping to the 1D Ising Model

A key theoretical breakthrough is the exact mapping of the proposed MaxEnt models to a heterogeneous version of the one-dimensional Ising model.

• By introducing "spin" variables $\sigma_{ij}(t)$ representing the state of a link between nodes $i$ and $j$ at time $t$, the Hamiltonian of the network trajectory is transformed into a sum of non-interacting 1D Ising chains.
• This mapping allows for an analytic solution, avoiding the need for computationally expensive Monte Carlo simulations often required for Exponential Random Graph Models (ERGMs).

C. Analytic Solutions and Parameters

The solution yields exact expressions for:

• Connection Probability ($p_{ij}$): The marginal probability that nodes $i$ and $j$ are connected.
• Memory Function ($q_{ij}(\tau)$): The joint probability that a link exists at time $t$ and $t+\tau$.
• Transition Matrices: Stochastic matrices describing the evolution of each link, allowing the calculation of relaxation times (correlation lengths) for each pair of nodes.

D. Structural Break Detection

To handle non-stationary real-world data, the authors integrate a Binary Segmentation algorithm using the Akaike Information Criterion (AIC).

• The algorithm iteratively splits the time series into segments where the statistical properties (parameters) are stationary.
• It compares a single global model against a model with a structural break at time $t$, selecting the split if it significantly reduces the AIC (balancing likelihood and model complexity).

3. Key Contributions

1. Unbiased Inference Framework: A rigorous MaxEnt framework that simultaneously controls for structural heterogeneity (node fitness) and local link persistence without assuming a specific parametric form for memory.
2. Analytic Tractability: The mapping to the 1D Ising model provides exact analytic solutions for transition probabilities and correlation functions, a rarity in complex network modeling.
3. Node-Specific Memory: The model demonstrates that memory effects are best explained by node-specific latent variables (persisting degrees) rather than global or dyad-specific parameters.
4. Structural Break Detection: A model-dependent method to identify stationary regimes and exogenous events in temporal networks, improving the accuracy of parameter estimation.
5. Relaxation Time Characterization: The ability to compute the relaxation time ($\tau^c_{ij}$) for every node and link, quantifying how quickly the system returns to equilibrium after a perturbation.

4. Results (Application to MIT Proximity Network)

The method was applied to the MIT Reality Mining dataset (2004–2005), a proximity network of 92 individuals.

• Model Selection (AIC):
  • Among memory-less models, the degree-constrained model (Binary Configuration Model) outperformed link-specific and global models, confirming that node fitness drives topology.
  • Among memory models, the model constraining persisting degrees (node-specific memory) significantly outperformed models with persisting links or global memory. This confirms that memory is a local, node-specific phenomenon.
• Structural Breaks:
  • The algorithm identified 21 predicted change points. Within a $\pm 2$ day window, it successfully captured 11 out of 23 known external events (e.g., holidays, exams), demonstrating the model's sensitivity to exogenous shocks.
• Memory Decay:
  • Analysis of the identified stationary segments showed that the autocovariance of persisting degrees decays over time.
  • The percentage of nodes exhibiting significant memory (z-score > 1.96) dropped from ~97% at lag $\tau=1$ to near 0 at $\tau=3$ in shuffled data, but remained significant in the real data only when structural breaks were accounted for.
• Predictive Performance:
  • The node-specific memory model (H2) achieved the lowest Mean Squared Error (MSE) in predicting persisting degrees compared to other models.
  • The model successfully captured the relaxation dynamics, showing that different nodes have vastly different correlation times, implying diverse "personalities" in how they maintain social ties.

5. Significance

• Theoretical Advancement: The paper bridges statistical physics (Ising models) and network science, providing a solvable framework for temporal networks that was previously intractable.
• Practical Utility: The ability to detect structural breaks allows researchers to avoid the "averaging bias" often found in long-term network studies, ensuring that models reflect the true dynamics of specific regimes.
• Insight into Human Dynamics: The results suggest that social memory is not a uniform global property but a heterogeneous, node-specific trait. Some individuals or groups hold onto connections much longer than others, and these traits can be quantified via relaxation times.
• Event Detection: The framework offers a powerful tool for "reverse engineering" external events in complex systems by analyzing shifts in network memory and topology.

In summary, this work provides a robust, mathematically rigorous toolset for analyzing temporal networks, capable of disentangling static structure from dynamic memory and identifying when and how the underlying system dynamics change.