Abstract
Time-varying networks describe a wide array of systems whose constituents and interactions evolve over time. They are defined by an ordered stream of interactions between nodes, yet they are often represented in terms of a sequence of static networks, each aggregating all edges and nodes present in a time interval of size $\Delta t$. In this work we quantify the impact of an arbitrary $\Delta t$ on the description of a dynamical process taking place upon a time-varying network. We focus on the elementary random walk, and put forth a simple mathematical framework that well describes the behavior observed on real datasets. The analytical description of the bias introduced by time integrating techniques represents a step forward in the correct characterization of dynamical processes on time-varying graphs.
Introduction
In the real world, networks are inherently dynamic: people communicate, neurons fire, and sensors exchange data at specific timestamps. However, researchers frequently simplify this continuous stream by "slicing" data into discrete time windows ($\Delta t$), aggregating all interactions within that window into a single static snapshot. This choice of $\Delta t$ is often treated as a matter of convenience, but it fundamentally alters the perceived "physics" of any dynamical process—such as viral spread or information flow—running on the network. This paper addresses the lack of a rigorous analytical framework to quantify the bias introduced by such temporal aggregation.
Modeling Activity-Driven Networks
The authors utilize activity-driven networks as their primary theoretical framework. In this model, each node is characterized by an intrinsic "activity rate" ($a$), representing the probability per unit of time that it initiates an interaction.
The core methodology involves:
- Transition Probabilities: Deriving a formula ($Q_{a|a'}$) for the probability of a random walker moving between nodes of different activity levels within a window $\Delta t$.
- Analytical Limits: Solving for the "stationary distribution" ($\rho_a$)—the probability of finding a walker at a node with activity $a$—in extreme cases of high and low temporal resolution.
- Numerical Validation: Comparing mathematical predictions against simulations on synthetic networks and real-world datasets, including the PRL Co-authorship Network and the Yahoo! Music Dataset.
Results and Validation
The study reveals that the perceived importance of a node is highly dependent on the observer's temporal resolution. In long time windows, highly active nodes emerge as "hubs" that dominate traffic. Conversely, in very short windows, these hubs lose their influence because the probability of them being active in any specific micro-second is low. In the limit of very small $\Delta t$, the occupation probability becomes $1/N$, rendering the network effectively homogeneous.
As shown in the results, for large $\Delta t$, the probability of finding a walker at a node becomes proportional to its activity ($\rho_a \propto a$), aligning with the behavior of static networks. The theoretical curves (solid lines) demonstrate a remarkable fit with empirical data from the PRL and Yahoo! datasets, confirming that the activity-driven model captures the essential mechanics of temporal distortion.
Conclusion
This work provides a closed-form solution for the occupation probability $\rho_a$, offering a way to correct for the biases introduced by time-binning. While the current framework assumes a memoryless (Markovian) process and focuses on discrete-time random walks, it lays the groundwork for future research into continuous-time processes and more complex dynamics like epidemic spreading. Understanding these temporal biases is a critical step toward the accurate characterization of dynamical processes on time-varying graphs.
Summary updated