Inferring origin-destination distribution of agent transfer in a complex network using deep gated recurrent units

Vee-Liem Saw, Luca Vismara, Suryadi Suryadi, Bo Yang, Mikael Johansson, Lock Yue Chew

This paper presents a novel approach to a classic problem in network science: figuring out where everyone is going just by watching them pass by.

TL;DR

Researchers have developed a "network-free" deep learning framework (DNNGRU) that uses Gated Recurrent Units to infer origin-destination (OD) traffic patterns from simple edge-count time series. By leveraging temporal dependencies in traffic flow, the model consistently outperforms traditional statistical estimators and provides new insights into how network topology—specifically path overlap—limits our ability to "see" the full picture of agent movement.

What Problem Does This Paper Address?

In complex systems—whether it's the internet, a city's road network, or a campus shuttle service—managing flow requires knowing the Origin-Destination (OD) distribution. We want to know: if an agent starts at point A, what is the probability they are heading to point B?

The challenge is that direct tracking is often difficult, expensive, or invasive. It is much easier to simply count how many agents pass through a specific "link" or "edge" (like a router interface or a road sensor). However, estimating OD patterns from link counts is a "severely underdetermined" problem. Because many different paths share the same links, there are mathematically infinite ways to explain the observed traffic. Traditional statistical methods (like Vardi’s EM algorithm) struggle with this ambiguity and often require an explicit, perfect map of the network's routing to function.

Methods

The authors propose a Deep Neural Network with Gated Recurrent Units (DNNGRU).

  • Temporal Intelligence: Unlike traditional methods that treat snapshots of traffic as independent events, the GRU architecture captures the "memory" of the network. It accounts for temporal correlations, such as "bus bunching" or cascading traffic delays.
  • Network-Free Learning: The model is "network-free" because it doesn't need the explicit routing matrix (the map of every possible path) encoded into its logic. Instead, it learns the underlying structure of the system through supervised learning on time-series data of agent volumes.
  • Probability Regression: Rather than trying to predict the exact number of agents (which fluctuates), the model regresses for the "fan-out" probabilities ($\zeta_{ij}$)—the stationary likelihood of an agent at origin $i$ choosing destination $j$.

The authors compared their DNNGRU against several benchmarks: Linear Regression (LR), Vardi’s Expectation-Maximisation (EM), Entropy Maximisation, and Bayesian inference.

Datasets

The study evaluated the model across a diverse range of synthetic and real-world network topologies:

  • Synthetic Topologies: Lattice, Random, and Small-world networks.
  • Real-World Internet Networks: VinaREN (Vietnam) and MYREN (Malaysia) topologies from the Internet Topology Zoo.
  • Application Case Study: A bus loop service modeled after the NTU (Nanyang Technological University) campus shuttle, using real-world parameters for bus boarding and travel times.
  • Training Data: The models were trained on 250,000 simulated datasets where the ground-truth OD probabilities were known.

Key Insights and Ideas

  • The "Overlap" Penalty: The authors introduced a new index ($\chi_i$) to quantify the degree of path overlap. They found that as paths from different origins share more edges, the "signal" becomes blurred, making it harder for any model to disentangle who is going where.
  • Small-World Paradox: Interestingly, small-world networks—often praised for efficiency—can be harder to predict. Their "highway edges" (common paths that many agents prefer) create high overlap, which acts as a bottleneck for information inference.
  • The Power of Memory: The GRU’s ability to process time-series data was the "aha moment." By seeing how traffic builds up or clears over time, the model can distinguish between different OD pairs that might look identical in a single static snapshot.
  • Computational Efficiency: While Bayesian methods took three days to process just 1,000 datasets on a CPU, the trained DNNGRU could process 50,000 datasets in less than a minute on a GPU.

Key Results

  • Superior Accuracy: DNNGRU consistently outperformed Vardi’s EM and other traditional methods across all network types.
  • Near-Optimal Performance: In scenarios where an exact analytical solution was possible (like simple bus loops), the DNNGRU's performance was nearly identical to the theoretical optimum.
  • Scaling Law: The prediction error followed a power-law decay relative to the length of the time series ($T$), suggesting that more data leads to predictably better accuracy.
  • Real-World Utility: In the bus loop application, the model was highly effective at ranking destinations by popularity, which is critical for transit planning (e.g., deciding which stops to skip for express routes).

Limitations and Future Work

  • Data Hunger: The model requires a massive amount of labeled training data (250k datasets) to reach peak performance, which might not be available for all real-world systems.
  • Stationarity Assumption: The current framework assumes that the underlying OD probabilities ($\zeta_{ij}$) are stationary over the period of interest. It may struggle with systems where travel preferences shift rapidly (e.g., during a sudden emergency).
  • Future Directions: The authors suggest scaling the approach to city-wide networks and exploring its use in privacy-preserving traffic management, as the model can infer patterns without ever needing to track individual identities.

Summary updated

Abstract

Predicting the origin-destination (OD) probability distribution of agent transfer is an important problem for managing complex systems. However, prediction accuracy of associated statistical estimators suffer from underdetermination. While specific techniques have been proposed to overcome this deficiency, there still lacks a general approach. Here, we propose a deep neural network framework with gated recurrent units (DNNGRU) to address this gap. Our DNNGRU is \emph{network-free}, as it is trained by supervised learning with time-series data on the volume of agents passing through edges. We use it to investigate how network topologies affect OD prediction accuracy, where performance enhancement is observed to depend on the degree of overlap between paths taken by different ODs. By comparing against methods that give exact results, we demonstrate the near-optimal performance of our DNNGRU, which we found to consistently outperform existing methods and alternative neural network architectures, under diverse data generation scenarios.
BibTeX
@inproceedings{saw2023inferring,
  author = {Vee-Liem Saw and Luca Vismara and Suryadi Suryadi and Bo Yang and Mikael Johansson and Lock Yue Chew},
  title = {{Inferring origin-destination distribution of agent transfer in a complex network using deep gated recurrent units}},
  booktitle = {Scientific},
  year = {2023},
  doi = {10.1038/s41598-023-35417-9},
}
Figure