Efficient Temporal Shortest Path: Navigating the Evolution of Social Graphs

TL;DR

As social networks evolve, the "shortest path" between users is not static. This paper introduces a highly efficient framework for querying historical shortest paths using Temporally Evolving Graphs (TEG). By injecting temporal validity into Contraction Hierarchies (CH) and utilizing Temporal Partitioning, the researchers achieved query speeds up to 10x faster than traditional snapshot-based methods.

The Evolution Problem: Snapshots vs. Continuity

In a dynamic world, LinkedIn or Facebook aren't just one graph; they are thousands of versions of the same graph. To find out how "close" two people were three years ago, most systems do one of two things:

1. Snapshot Reconstruction: Rebuild the graph from a specific date using deltas (Extremely slow).
2. Graph Sequences: Store every version separately (Massive storage waste).

The authors argue that we should treat time as a first-class citizen within the graph structure itself, leading to the TEG (Temporally Evolving Graph) model.

Methodology: Temporal Contraction Hierarchies

The core innovation lies in adapting the Contraction Hierarchies (CH)—a master-class technique typically used for GPS road networks—to a temporal context.

1. Integrated Temporal Storage

Instead of having multiple copies of an edge, a single edge is represented as <u, v, w, ts, te>. If a friendship lasts from $t_1$ to $t_5$, it exists in the graph only during that interval.

2. Temporal Shortcuts

CH works by "contracting" (removing) unimportant nodes and replacing them with "shortcuts" that preserve shortest path distances. The authors extended this by adding validity intervals to these shortcuts. If a shortcut is formed by two edges that only coexist for a specific window, the shortcut inherits that intersection as its lifetime.

Figure: The transition from snapshot sequences (a-e) to a single Integrated TEG (f), and the resulting Contraction Hierarchy (Figure 2).

3. TISP-all: The Continuous Query

Unlike a standard Dijkstra search, the Time Interval Shortest Path (TISP-all) query doesn't stop when it finds one path. It continues until the entire requested time window is covered by the shortest possible segments.

Experiments: Speeding up the History

The researchers tested their approach on real-world YouTube metadata (165 days of evolution).

• Point Queries: On the YouTube dataset, Temporal CH outperformed Dijkstra and BFS by a factor of 6x.
• Interval Queries: For a 25-day window, the "Integrated" TISP-Dijkstra was 2x faster than running individual snapshots, and the CH-optimized version was 10x faster than the baseline.

Table: Note the drastic improvement in Query Time (ms) when moving from BFS to CH.

Scalability via Temporal Partitioning

To handle a massive synthetic dataset with 10 billion edges, the authors used "Temporal Partitioning." By splitting the TEG into fixed-time windows (e.g., 15-day chunks), they could distribute the query load across a cluster. This parallelization yielded a 30-60% gain in performance over a single "Super-TEG" structure.

Depth Insight: Why it Works

The brilliance of this work is the realization that temporal validity is just another constraint in the relaxation step of Dijkstra. By preprocessing these constraints into a hierarchical index (CH), we avoid the "Cold Start" problem of reconstructing snapshots.

However, there is a trade-off: Preprocessing Time. While queries are fast, building a Temporal CH for the YouTube dataset took nearly 4 hours. This suggests the method is ideal for "Read-Heavy" historical archives where deep temporal analysis is performed frequently.

Conclusion

This paper provides a robust blueprint for temporal graph management. As we move toward real-time social analytics, the ability to "scroll back" the shortest-path distance efficiently becomes a prerequisite for understanding influence, information flow, and community evolution.

Future Outlook: The next frontier is likely Incremental CH Updates, allowing the index to evolve alongside the graph in real-time without requiring a 4-hour re-calculation.