Source-linked AI summary
Causality-Driven Slow-Down and Speed-Up of Diffusion in Non-Markovian Temporal Networks
Ingo Scholtes, Nicolas Wider, Rene Pfitzner, Antonios Garas, Claudio Juan Tessone, Frank Schweitzer
TL;DR
Static aggregates do not capture how interaction ordering changes causality and diffusion, and an analytical explanation for these effects has been lacking. The paper uses higher-order, causality-preserving representations and Markov models to predict diffusion changes, showing across empirical systems that non-Markovian ordering can either slow down or speed up diffusion.
Problem
Existing studies emphasize inter-event-time distributions, but the analytical influence of interaction ordering and causality on diffusion remains insufficiently explained.
Method
The paper constructs higher-order time-aggregated representations and Markov models that preserve statistics of time-respecting paths, then analyzes transition-matrix eigenvalue spectra.
Results
Non-Markovian characteristics can both slow down and speed up diffusion relative to time-aggregated networks, with predictions validated on six empirical data sets.
Takeaways & Limitations
Understanding temporal-network dynamics requires considering causality structures alongside activity patterns because interaction ordering can mitigate or enforce topology-driven limits on diffusion.
Takeaways & Limitations
The analytical slow-down prediction assumes sufficiently large k or sufficiently small total variation distance, a primitive null model, and a non-degenerate second eigenvalue.
Abstract
from arXiv · showhide
Recent research has highlighted limitations of studying complex systems with time-varying topologies from the perspective of static, time-aggregated networks. Non-Markovian characteristics resulting from the ordering of interactions in temporal networks were identified as one important mechanism that alters causality, and affects dynamical processes. So far, an analytical explanation for this phenomenon and for the significant variations observed across different systems is missing. Here we introduce a methodology that allows to analytically predict causality-driven changes of diffusion speed in non-Markovian temporal networks. Validating our predictions in six data sets, we show that - compared to the time-aggregated network - non-Markovian characteristics can lead to both a slow-down, or speed-up of diffusion which can even outweigh the decelerating effect of community structures in the static topology. Thus, non-Markovian properties of temporal networks constitute an important additional dimension of complexity in time-varying complex systems.
1 Introduction
Temporal networks differ from static aggregates because interaction timing and ordering shape diffusion through causality. The paper addresses the missing analytical explanation for these effects by introducing a causality-preserving framework that predicts both diffusion slow-down and speed-up.
- Temporal-network research has examined concurrency, interaction duration, and non-Poissonian inter-event times as influences on dynamical processes.
- Heavy-tailed inter-event times produce bursty interaction patterns that influence spreading and diffusion speed in dynamic social systems.
- Time-stamped edges form a causal path only when consecutive interactions occur in the required temporal order.
- Analytical explanations for how causality structures influence real-world dynamical processes and why effects vary across systems remain missing.
- The paper introduces higher-order time-aggregated representations and Markov models that preserve causality, using transition-matrix spectra to predict diffusion changes.
- Validated on six empirical data sets, the approach shows that interaction ordering can either slow down or speed up diffusion relative to time-aggregated networks.
2 Results
The paper represents causality in temporal networks through higher-order time aggregation and links the resulting spectral structure to diffusion speed. Analytical predictions and empirical comparisons show that interaction ordering can produce either diffusion slow-down or speed-up relative to the weighted aggregate network.
- Causality-preserving representations: Two-paths capture causality because consecutive interactions must occur in temporal order and within a specified waiting-time window.The paper defines time-respecting paths of length two as the simplest temporal structures beyond individual edges that encode causal ordering.
- Causality-preserving representations: The same weighted first-order aggregate network can correspond to temporal networks with different interaction orderings, second-order structures, and causal paths.In the four-node example, d →b →c exists in one temporal network but not the other when τ = 1.
- Empirical validation: Across six data sets, the model estimates causality-driven diffusion changes from higher-order transition spectra and compares them with random-walk convergence in weighted aggregate networks.The empirical study uses convergence thresholds, mean random walks beginning at every node, and a predicted S∗ reference.
- Causality-preserving representations: Second-order aggregate networks preserve temporal transitivity, enabling diffusion analysis through the spectral properties of their transition matrices.This property is absent from first-order aggregate networks, where adjacent edges do not necessarily form a time-respecting path.
- Causality-driven diffusion regimes: Non-Markovian characteristics can slow down or speed up diffusion, with the direction depending on how temporal ordering changes causal topology relative to the first-order aggregate network.In the community model, inhibited cross-community two-paths slow diffusion, whereas enforced cross-community paths mitigate community-driven deceleration.
3 Discussion
The paper concludes that higher-order, causality-preserving representations explain and predict how interaction ordering changes diffusion, including slow-downs and speed-ups across real-world temporal networks. These causal effects can reinforce, mitigate, or outweigh static topological effects such as community structures.
- Method and representation: Higher-order aggregate networks preserve the statistics of time-respecting paths while retaining the weighted aggregate network for non-Markovian contact sequences.The approach uses higher-order Markov models to represent causal temporal structure.
- Analytical prediction: The eigenvalue spectra of higher-order transition matrices analytically predict both the direction and magnitude of causality-driven diffusion changes.The prediction distinguishes slow-downs from speed-ups relative to first-order time-aggregated networks.
- Empirical findings: Diffusion slows by more than a factor of seven in one system and speeds up by a factor of four in another relative to the first-order time-aggregated network.These changes arise from the ordering of interactions and its effects on causal topology.
- Implications: Causality structures can reinforce, mitigate, or outweigh diffusion effects associated with static topological features such as community structures.This establishes causal topology as an additional temporal dimension of complexity.
- Implications: Accounting for both activity patterns and interaction ordering is necessary to understand temporal effects on diffusion, including systems where only link ordering is known.Airline and subway passenger itineraries illustrate settings without absolute timestamps but with inferable causal link order.
- Future applications: The framework may support temporal community detection, ordering-sensitive centrality measures, and visualization methods for time-varying networks.These applications are presented as prospective uses of the higher-order representation.
Methods
The study models diffusion in six empirical temporal networks using random-walk convergence and higher-order representations that preserve time-respecting path statistics.
- Empirical temporal networks: Diffusion is studied in six empirical data sets spanning ant interactions, campus contacts, company emails, airline itineraries, and London Underground journeys.The supplied passages identify the data-set domains and describe strongly connected components of 116 airports and 132 underground stations.
- Diffusion dynamics: Random-walk convergence measures diffusion by tracking node-visitation probabilities until they approach a stationary distribution.The analysis uses total variation distance between observed visitation probabilities and the stationary distribution.
- Diffusion dynamics: Convergence time t_agg(ϵ) is the minimum number of steps k for which the total variation distance Δ(π_k, π) falls below ϵ.This provides the baseline convergence time for a random walk on the weighted time-aggregated network.
- Higher-order Markov models: A second-order walk preserves observed two-path frequencies, whereas the maximum-entropy model preserves first-order edge weights while making consecutive links independent.Transition rates in the weighted second-order network are proportional to edge weights and normalized over outgoing edges; the transition matrix can be restricted to a largest strongly connected component when needed.
- Higher-order representations: Higher-order time-aggregated networks represent time-respecting paths as nodes and edges, allowing temporal interaction sequences to retain causality-related structure.Second-order nodes represent first-order aggregate edges, while second-order edges represent possible time-respecting continuations.
- Higher-order Markov models: The entropy growth rate quantifies information loss about the current state in a second-order Markov process.It is zero for deterministic transitions and reaches a size-dependent maximum when every state is equally reachable at each step.
Supplementary Information
The supplementary information derives a spectral prediction for diffusion slow-down or speed-up and develops a two-community non-Markovian model that preserves the weighted aggregate network.
- Spectral derivation: The transition matrix T(2) is analyzed through its eigenvalues and eigenvectors to derive random-walk convergence behavior.The stationary distribution arises from the leading eigenvector, while subleading eigenvalues govern convergence toward stationarity.
- Assumptions: The prediction assumes sufficiently large k, a primitive null-model transition matrix, and a non-degenerate second eigenvalue.The asymptotic approximation uses |λ2| > |λ3| and sufficiently small total variation distance ϵ.
- Spectral derivation: The slow-down factor compares convergence times of a non-Markovian transition matrix with a Markovian null model based on the same weighted aggregate network.The prediction is defined from t(ϵ)/˜t(ϵ) and in the small-ϵ limit depends on the corresponding second-order networks.
- Spectral derivation: A larger Markovian spectral gap than non-Markovian spectral gap gives S∗(T(2)) > 1 and slows convergence, whereas the reverse gives S∗(T(2)) < 1 and speeds it up.These cases correspond respectively to larger conductance in the Markovian second-order network and larger conductance in the non-Markovian one.
- Toy model: Non-Markovian ordering can either inhibit or enforce time-respecting paths across communities, producing diffusion slow-down or speed-up despite an unchanged weighted aggregate network.For σ ≠ 0, the transition matrices differ while preserving the same stationary activation frequencies and stationary distribution as the Markovian counterpart.