PaperlayerView exact revision on arXiv

Source-linked AI summary

Path lengths, correlations, and centrality in temporal networks

Raj Kumar Pan, Jari Saramäki

arXiv:1101.5913v2physics.soc-phcond-mat.dis-nncs.SIphysics.data-an

TL;DR

Temporal paths are difficult to characterize because interactions occur as temporary, time-ordered events rather than static edges. The paper defines and computes average temporal distance, then compares temporal structure with static topology in communication and air-transport networks. Temporal and static distances correlate but can differ widely, while event correlations have opposite effects across the two empirical networks.

  • Problem

    Temporal-path properties are poorly understood because static or quasi-static network representations do not capture temporary, time-ordered interactions.

  • Method

    The paper defines average temporal distance, develops a vector-clock algorithm, and studies temporal paths, centrality, heterogeneities, and correlations in communication and air-transport event sequences.

  • Results

    Temporal and static distances correlate but show a wide spread, with some statically close nodes connected by slow paths or no temporal path; correlations increase communication distances but decrease air-transport distances.

  • Takeaways & Limitations

    Static topology alone can misrepresent dynamic reachability, so event timing and temporal heterogeneity should be included in models of information flow, epidemics, and related processes.

Abstract

from arXiv · show

In temporal networks, where nodes interact via sequences of temporary events, information or resources can only flow through paths that follow the time-ordering of events. Such temporal paths play a crucial role in dynamic processes. However, since networks have so far been usually considered static or quasi-static, the properties of temporal paths are not yet well understood. Building on a definition and algorithmic implementation of the average temporal distance between nodes, we study temporal paths in empirical networks of human communication and air transport. Although temporal distances correlate with static graph distances, there is a large spread, and nodes that appear close from the static network view may be connected via slow paths or not at all. Differences between static and temporal properties are further highlighted in studies of the temporal closeness centrality. In addition, correlations and heterogeneities in the underlying event sequences affect temporal path lengths, increasing temporal distances in communication networks and decreasing them in the air transport network.

I. INTRODUCTION

Temporal networks model recurrent, temporary interactions whose time ordering constrains information, resource, and epidemic spreading. The paper defines temporal distances and studies how temporal structure changes paths and centrality relative to static representations.

  • Motivation: Temporal networks consist of short-duration events occurring at specific times, making event-sequence structure part of the network representation.Examples include flights, calls, emails, and physical encounters.
  • Motivation: Causal temporal paths require interactions to occur in time order, so a static path may have no corresponding temporal path.Static adjacency records whether an interaction ever occurred, not whether events can be traversed causally.
  • Approach: The paper studies average temporal distance, the mean completion time of time-ordered shortest paths, as a quantity relevant to dynamical-process speed.The distance depends on temporal heterogeneity and correlations in event sequences.
  • Approach: The paper defines an observation-window-aware temporal distance, provides a vector-clock algorithm, and compares temporal with static distances in communication and air-transport networks.It also examines heterogeneities, correlations, waiting-time constraints, and temporal closeness centrality.
  • Findings: Correlations slow dynamics in human communication but produce faster dynamics in the air-transport network, while temporally peripheral-looking nodes can provide fast paths.The contrasting correlation effects show that temporal organization matters beyond static topology.

A. Temporal paths and temporal distances: definitions

The paper defines temporal distance using causal, time-ordered events and constructs an average that avoids artifacts from a finite observation window. Its boundary treatment preserves event timing invariance without creating paths absent from the observed window.

  • Temporal paths: A temporal path requires each event to begin after the previous event completes; its length includes waiting and the final event duration.For events e1=(i,j,t1,δt1) and e2=(j,k,t2,δt2), traversal requires t2 > t1 + δt1 and has length Δt = t2 − t1 + δt2.
  • Temporal paths: Temporal distance τij(t) is the shortest time to reach j from i at time t, and equals ∞ when no qualifying path exists.Because future events change with t, temporal distance is time-dependent and is not strictly a metric.
  • Finite observation windows: Averaging only where distances are finite biases results toward paths occurring early in the observation period.Late paths are penalized by the increasing frequency of infinite distances as the window endpoint approaches.
  • Finite observation windows: The average distance must be invariant to where an otherwise identical shortest-path sequence occurs within the observation window.This requirement rejects finite-range averaging and motivates a node-pair-specific boundary treatment.
  • Boundary condition: Repeating the first path for each node pair yields the periodic-boundary distance curve, while avoiding artificial connections that could span multiple observation windows.The construction makes a single path’s average distance independent of its placement in the window.

B. An algorithm for calculating temporal distances

The paper computes average temporal distances by detecting shortest temporal paths across an event sequence with vector clocks. A backward scan updates earliest reachable times and identifies path beginnings and durations.

  • The algorithm detects shortest temporal paths by processing the event list once in decreasing-time order.
  • Vector clocks record the earliest time each node can receive information from another through direct or time-ordered events.
  • Periodic boundary conditions make average temporal distance independent of where the path sequence occurs within the observation period.
  • Each vector-clock update identifies a new shortest temporal path and supplies its starting time and duration for averaging.
  • The implementation can be generalized to directed events with specific durations.

A. Data description

The study analyzes temporal and aggregated static versions of communication and air-transport networks. The datasets differ in event type, directionality, duration, observation window, and network scale.

  • The empirical analysis compares social communication events with flights transporting passengers between airports.
  • The mobile-phone dataset records instantaneous, undirected calls over 120 days.
  • The email network contains 2,993 users, 28,843 directed edges, and 202,687 emails observed over 81 days.
  • The air-transport dataset contains 279 airports, 4,152 directed edges, and 180,192 flights observed from 14th to 23rd December 2008.
  • Social-network observation periods reflect data availability, whereas the air-transport window was shortened because flight schedules are periodic.

B. Relationship between temporal and static distances

Average temporal distance generally increases with static graph distance, but the relationship has broad variation. Longer static paths are also less likely to correspond to finite temporal paths within the observation window.

  • Temporal and static distances correlate on average across the call, email, and air-transport networks.
  • At the same static distance in the mobile-call network, temporal distances can differ by a factor of 10^2.
  • In social networks, the static-to-temporal relationship is nonlinear, with a steeper slope at larger temporal distances.
  • The fraction of finite temporal paths decreases as static distance increases.
  • Finite temporal paths connect 95% of mobile-call pairs and 58% of directed-email pairs within their observation windows.

C. Effects of correlations on temporal distances

Event correlations and heterogeneities affect temporal distances differently across communication and air-transport networks. Randomized null models separate the effects of burstiness, cross-link correlations, and daily timing patterns.

  • Null models remove burstiness, event-event correlations, or daily patterns while retaining static-network structure.
  • Mobile-call temporal distances are longer than in time-shuffled and random-time sequences, while daily patterns and cross-link correlations contribute little.
  • Air-transport temporal distances are lower in the original sequence than in every null model.
  • Removing event-event correlations slightly increases air-transport distances, while daily patterns cause a minor increase.

D. Temporal paths with waiting time cutoff

A waiting-time cutoff limits which time-ordered paths exist, with markedly different reachability thresholds in the call and air transport networks. Event correlations and burstiness further alter temporal distances and path availability.

  • Cutoff definition: The waiting-time cutoff Δc is the maximum allowed interval between consecutive events on a temporal path.A path is valid only when consecutive events satisfy the cutoff condition.
  • Reachability: For the call network, connectivity emerges approximately when Δc > 2 days, so information must be forwarded for at least that long to percolate.The long threshold severely constrains global information cascades.
  • Reachability: For the air transport network, most temporal paths become finite when Δc > 30 minutes, while ffinite = 0.16 even at Δc = 1 sec.Direct connections and simultaneous arrivals and departures contribute to early reachability.
  • Null-model comparison: At Δc = 2 days in the call network, time-shuffled and random-time null models yield more finite paths but lower average temporal distances than the original sequence.Bursty event sequences create longer waiting times that limit existing paths, while the null models’ shorter distances slow SIR-like dynamics less.
  • Null-model comparison: With air-transport waiting times constrained to 30 minutes–5 hours, destroying event-event correlations produces longer temporal distances than the original sequence.The ordering of cumulative distributions remains similar across null models.

E. Temporal Closeness Centrality

Temporal closeness centrality measures how quickly a node can reach others through time-ordered paths, complementing static closeness based on topological shortest paths. Its relationship with degree and shell index differs between communication and air transport networks.

  • Centrality definition: Temporal closeness centrality CT measures how quickly all other nodes can be reached from a given node.It uses average temporal distances τij, while static closeness CS uses average static distances dij.
  • Mobile phone call network: In the call network, both CS and CT increase with degree k and k-shell index ks on average, despite substantial spread and exceptions.Nodes with high k or ks can still have low static or temporal closeness.
  • Mobile phone call network: For the call network, CS correlates with k and ks at C = 0.80 and C = 0.81, while CT correlates at C = 0.69 and C = 0.76.Both centralities remain fairly strongly associated with degree and shell index.
  • Air transport network: In the air transport network, static closeness correlates strongly with degree and shell index at C = 0.89 and C = 0.88, respectively.Figure 8 compares CS and CT against k and ks using mean values and conditional-probability shading.
  • Air transport network: Air-transport temporal closeness correlates much more weakly with degree and shell index at C = 0.45 and C = 0.46, respectively.Flight times and geographic embedding strongly influence temporal path lengths, making central airports’ location relevant alongside connectivity.
  • Air transport network: The central air-transport airports ranked highest by CT include Atlanta, Chicago, and Dallas, while some lower-degree central-state airports also rank highly.CHA, MGM, and ACT illustrate high temporal centrality despite low k and ks.

IV. CONCLUSIONS AND DISCUSSION

Temporal paths can differ substantially from static-network paths, affecting how quickly processes spread. Their measurement also depends on the observation window and on temporal heterogeneities in event sequences.

  • Temporal and static distances correlate, but static proximity can conceal long, reversed, or nonexistent temporal paths.Consequently, spreading processes may follow very different routes, and statically insignificant nodes may rapidly transmit information or disease.
  • Temporal-distance measures may become uninformative when the observation window is too short relative to event frequency.The authors therefore identify choosing an appropriate finite observation window as an important issue for temporal-graph analysis.
  • Event-sequence heterogeneities and correlations affect temporal distances even when networks retain the same topology and edge-event counts.The null models preserve static structure and total edge events, isolating differences associated with temporal organization.

Appendix A: Algorithm for computing temporal distances

The generalized algorithm computes temporal distances for directed events and events with nonzero completion durations. It processes events in reverse time order using vector-clock state and additional path-start information.

  • The generalized temporal distance algorithm extends the instantaneous, undirected procedure to directed and non-instantaneous events.Its main flow remains the same as in the instantaneous undirected case, with additional handling for direction and duration.
  • For directed events, the algorithm compares the source node’s vector clock elementwise with the destination’s while leaving the destination clock unchanged.This encodes the one-way nature of an event when updating temporal reachability.
  • For events with duration δt, each node maintains a vector ψ_i storing the last observed beginning times of temporal paths from i.The ψ_i elements are initialized to ∞ before processing begins.
  • If a path through an event from i to j finishes at t + δt, the algorithm records τ_ij(t) = δt.The update occurs when the relevant vector-clock condition φ^k_j > t + δt holds.
  • The procedure takes a reverse-time-sorted event list as input and returns D, the average temporal distance between nodes.The pseudocode also iterates over node pairs and handles first and last terms in the accumulation.
Loading 1101.5913v2…