Source-linked AI summary
Random walks on temporal networks
Michele Starnini, Andrea Baronchelli, Alain Barrat, Romualdo Pastor-Satorras
TL;DR
The paper asks how random walks behave when networks evolve over time, where empirical evidence and the role of temporal structure remain limited. It analyzes contact-based temporal networks with randomized benchmarks and finds that exploration is slower than on aggregate projections, especially because of correlations between consecutive contacts. The study also examines how finite observation durations affect random-walk exploration.
Problem
Temporal network dynamics can affect processes on networks, but many questions remain about how random walks unfold on evolving rather than aggregated networks.
Method
The study analyzes empirical temporal contact networks and introduces randomized sequences and network-dynamics quantities to isolate the effects of different temporal properties.
Results
Random-walk exploration is slower on temporal networks than on aggregate projected networks after time rescaling, with temporal correlations between consecutive contacts playing a fundamental role.
Takeaways & Limitations
Random walks show that temporal correlations and finite network duration can materially constrain exploration, providing a basis for understanding more complex dynamics on evolving networks.
Abstract
from arXiv · showhide
Many natural and artificial networks evolve in time. Nodes and connections appear and disappear at various timescales, and their dynamics has profound consequences for any processes in which they are involved. The first empirical analysis of the temporal patterns characterizing dynamic networks are still recent, so that many questions remain open. Here, we study how random walks, as paradigm of dynamical processes, unfold on temporally evolving networks. To this aim, we use empirical dynamical networks of contacts between individuals, and characterize the fundamental quantities that impact any general process taking place upon them. Furthermore, we introduce different randomizing strategies that allow us to single out the role of the different properties of the empirical networks. We show that the random walk exploration is slower on temporal networks than it is on the aggregate projected network, even when the time is properly rescaled. In particular, we point out that a fundamental role is played by the temporal correlations between consecutive contacts present in the data. Finally, we address the consequences of the intrinsically limited duration of many real world dynamical networks. Considering the fundamental prototypical role of the random walk process, we believe that these results could help to shed light on the behavior of more complex dynamics on temporally evolving networks.
I. INTRODUCTION
The paper motivates studying dynamical processes on temporally evolving networks rather than only on static projections, focusing on random walks as a simple diffusion model with searching applications.
- Real networks change as connections appear, disappear, or are rewired across multiple timescales.
- Most earlier complex-network studies represented networks statically or as aggregates, omitting much temporal information.
- Random walks provide a simple diffusion model for studying processes on temporal networks and a baseline for searching with only local information.
- The study uses high-resolution face-to-face contact sequences from several social settings, recording contact start and end times.
- The paper analyzes empirical dynamical networks, introduces randomization procedures, develops mean-field equations, and studies exploration, mean first-passage times, and finite-duration effects.
II. A SHORT OVERVIEW OF RANDOM WALKS ON STATIC NETWORKS
The section defines standard random-walk quantities on static networks, including transition and occupation probabilities, mean first-passage time, coverage, and a rescaled time for temporal networks.
- A random walker at vertex i hops to a nearest neighbor j at the next time step.
- In binary networks, the walker chooses uniformly among vertex i’s k_i neighbors, while weighted networks select neighbors proportionally to edge weight.
- The occupation probability ρ_i is the steady-state probability that the walker occupies vertex i.
- Mean first-passage time measures the average time to reach a target vertex, while coverage counts distinct vertices visited by time t.
- For sufficiently small ρ_i t, coverage is linear, C(t) ∼ t, because a new vertex is visited at each initial time step.
- Temporal-network walks may become trapped when a node loses all active links, so their dynamics is evaluated using the rescaled time pt.
A. Basics on temporal networks
Temporal networks are represented as time-indexed contact sequences, while static projections retain aggregate connectivity but discard temporal ordering and time-respecting constraints.
- A temporal network is represented by contact triplets (i, j, t) over a sequence of times, or by a temporal adjacency function χ(i, j, t).
- Binary projections record whether actors ever interacted, whereas weighted projections also encode total interaction time.
- Static projections coarse-grain temporal information that can matter for dynamical processes.
- Temporal dynamics must follow time-respecting paths, so not every aggregate-network link is available at every time.
- The temporal organization of contacts includes bursty link appearances and disappearances, further distinguishing temporal from aggregated networks.
B. Empirical contact sequences
The study analyzes face-to-face contact sequences across four social contexts, characterizing their heterogeneous, bursty temporal structure and the time-respecting paths it creates. Although most node pairs are causally connected, temporal constraints can make navigation slow and difficult.
- Empirical datasets: The datasets cover conferences, a congress, and a primary school, using time-resolved face-to-face proximity contacts recorded by SocioPatterns.Each contact records its starting and ending times.
- Temporal structure: The datasets differ substantially in interaction density, average degree, average strength, and activity regularity.Some show low-activity periods followed by bursty peaks, whereas others exhibit more regular interactions.
- Temporal structure: Contact duration, pairwise contact time, and individual and global gap-time distributions are heavy-tailed, revealing bursty interactions.The same heavy-tailed behavior appears across the four empirical contact sequences.
- Temporal paths: Time-respecting paths are evaluated by existence, hop length, duration, and comparisons with fastest paths and projected-network shortest paths.Fastest paths minimize elapsed time, while shortest time-respecting paths minimize intermediate steps.
- Temporal paths: Most node pairs are causally connected, so nearly every actor can potentially influence nearly every other actor during the observed evolution.This broad causal connectivity does not remove temporal navigation constraints.
- Temporal paths: Shortest time-respecting paths have short-tailed hop lengths resembling projected-network paths, whereas their durations are broad-tailed and much longer than fastest-path durations.The average duration of shortest paths is on the order of the full contact-sequence duration T.
- Temporal paths: A temporal network can therefore be topologically well connected while remaining difficult to navigate or search because temporal dynamics constrain available paths.These path properties matter for spreading and searching processes.
C. Synthetic extensions of empirical contact sequences
The study extends empirical contact sequences through replication and two randomization procedures that preserve different temporal and contact statistics. These extensions expose how temporal correlations and finite observation durations affect analyses of random walks.
- Motivation: Finite empirical contact sequences may be too short for dynamical processes such as random walks to reach a steady state.For the considered datasets, the effective number of walker hops is limited relative to network size.
- Extensions: SRep periodically repeats the empirical sequence, preserving its statistical properties after accounting for the changed duration.Only small topological corrections to time-respecting paths and node influence sets are introduced.
- Extensions: SRan randomizes interaction time ordering, preserving projected weighted-network characteristics on average while destroying temporal correlations and producing Poisson contact-duration and individual-gap distributions.Each time step samples an empirical instantaneous network independently from the original sequence.
- Extensions: SStat generates sequences from randomly selected conversations, preserving contact statistics except the individual gap-time distribution Pi(τ).Overlapping contacts between the same agents are excluded when constructing the synthetic sequence.
- Preserved properties: SRep preserves P(w), P(∆t), and Pi(τ), whereas SRan preserves only P(w), and SStat preserves P(w) and P(∆t) but not Pi(τ).The comparison concerns the original sequence properties retained by each synthetic extension.
- Gap distributions: The aggregate gap distribution P(τ) remains broadly distributed in SRan and SStat despite bounded individual burstiness, yielding P(τ) ∼ (1 + τ/N)^-2 when the strength distribution is exponential.The total gap distribution follows from combining individual gap distributions with the probability of starting a conversation.
IV. RANDOM WALKS ON EXTENDED CONTACT SEQUENCES
The random walk advances through each instantaneous contact network by choosing an available neighbor uniformly, or waits when its current node is isolated. Temporal correlations complicate analysis, while SRan provides an uncorrelated reference case.
- Walk definition: At each time step, the walker at node i hops to a randomly chosen neighbor in the instantaneous network.If node i is isolated, the walker remains there and time advances by one step.
- Analytical treatment: Temporal correlations between contacts hinder analytical treatment of random walks on empirical contact sequences.Contacts between a given pair are neither fixed nor completely random, but exhibit long-range temporal correlations.
- Analytical treatment: SRan is analytically tractable because successive contacts are uncorrelated by construction.In this extension, the probability of choosing a connection between i and j is proportional to its original contact count ωij.
- Coverage analysis: The coverage calculation can be approximated by replacing a sum over vertex strengths with an integral.The resulting expression depends on the strength distribution P(s).
V. NUMERICAL SIMULATIONS
Numerical simulations evaluate random-walk coverage on extended contact sequences and mean first-passage times between nodes under controlled sequence durations and repeated independent runs.
- Simulation setup: Coverage simulations use sequences lasting 50 times the original duration T.This setting supports numerical exploration of the extended contact sequences.
- Simulation setup: Mean first-passage-time simulations run until a maximum time tmax = 10^8.The reported results average at least 10^3 independent runs.
A. Network exploration
Random-walk exploration is slower on empirical temporal sequences than on randomized counterparts, primarily because irregular interaction timing can trap walkers and delay discovery. Aggregate contact-duration heterogeneity matters less than temporal organization, though low-strength nodes can prevent near-complete coverage.
- Coverage comparison: Rescaled coverage is slowest for SRep, while SRan follows Eq. (13) and SStat is close but systematically slower.SRep preserves the empirical temporal sequence; SRan randomizes contact order, whereas SStat evens interaction activity.
- Temporal slowing: Irregular interaction timing slows SRep exploration because walkers can remain trapped on isolated nodes during low-activity periods.SRan and SStat destroy this temporal structure by balancing low- and high-activity periods.
- Role of durations: SRan and SStat show similar coverage despite differing contact-duration distributions, indicating limited sensitivity to heterogeneous conversation durations.Their behavior is accounted for by the projected network’s weight distribution.
- Asymptotic behavior: At large times, eswc and ht approach the predicted residual-coverage decay, whereas school is approximately exponential and 25c3 decays much more slowly.Some SRan deviations are attributed to the preserved topology of the projected weighted network.
B. Mean first-passage time
Mean first-passage times follow mean-field predictions for randomized temporal sequences but deviate strongly for empirical repeated sequences. Across datasets, node strength largely determines MFPT, while bursty contact timing produces substantial fluctuations.
- Mean-field comparison: SRan and SStat MFPTs fit mean-field theory, whereas SRep shows deviations and much stronger fluctuations around the average.The mean-field prediction states that τ_i is inversely proportional to strength s_i.
- Temporal correlations: MFPT deviations in SRep originate from bursty temporal correlations between consecutive contacts, not from the distribution of contact durations when cumulative link weights are preserved.This parallels the coverage result for empirical correlated sequences.
- Search consequence: Searching is slower on the empirical correlated network than on randomized versions, consistent with its smaller coverage.The comparison links temporal correlations to slower exploration and longer search behavior.
- Strength dependence: Across different datasets, MFPT data collapse after rescaling, and MFPT is largely determined by node strength.Higher strength implies more contacts and a greater probability of being reached, although equal-strength nodes can have different MFPTs.
VI. RANDOM WALKS ON FINITE CONTACT SEQUENCES
Finite temporal sequences constrain random-walk exploration: coverage varies across datasets, new-node discovery has broad-tailed delays, and reachability remains below static-network mean-field expectations. Aggregate strength predicts reachability only approximately, with strong fluctuations and saturation at large strength.
- Finite duration: Finite contact sequences impose a constraint on the length of realistic searching strategies.The limitation is especially relevant to searches conducted during bounded human gatherings.
- Coverage variability: Coverage varies considerably across datasets after rescaling by pt/N, unlike the collapse observed for randomized extensions.The time-lag distribution between successive discoveries is broad-tailed rather than exponentially decaying.
- Effective timescale: Coverage correlates strongly with the cumulative number of new conversations, although the relationship is not strictly linear.This suggests that the effective exploration timescale follows integrated interaction activity rather than average time alone.
- Starting-node effects: Coverage from different starting nodes remains heterogeneous even after equalizing the available walking duration.For static networks, coverage over a fixed duration would be independent of the starting node.
- Reachability: Reachability increases with strength and approximately collapses across datasets after rescaling, but saturates below 1 at large strengths.The observed values remain well below the static-network mean-field prediction.
- Finite-time effects: Reachability fluctuates strongly at fixed strength, and the fluctuations are larger for walks of length T/2 than for the full sequence.Shorter walks are less correlated with strength measured over the entire sequence.
VII. DISCUSSION AND CONCLUSIONS
The study shows that temporal correlations and finite observation windows fundamentally alter random-walk exploration on empirical contact networks. Randomized benchmarks separate these effects and provide a framework for studying diffusion on evolving networks.
- Empirical contact sequences exhibit heterogeneous, bursty behavior, including long-tailed conversation lengths, strengths, and inter-contact gaps.
- Randomizing temporal order removes temporal correlations, while statistically extended sequences preserve most original time-series properties except consecutive-conversation gap distributions.
- Random-walk coverage and mean first passage times are systematically slower than mean-field predictions on empirical sequences.
- The slowdown is attributed uniquely to temporal correlations between consecutive conversations, rather than heterogeneity in conversation lengths.
- Finite empirical durations prevent full exploration, and starting nodes produce different average coverages unlike static graphs.
- Randomized benchmarks and dynamical quantities offer a general framework for interpreting random walks and more complex diffusion on temporal networks.