Efficient numerical computation of traveler states in explicit mobility-based metapopulation models: Mathematical theory and application to epidemics
This work addresses a computational bottleneck for researchers modeling spatio-temporal disease spread using metapopulation frameworks, offering a more efficient simulation method.
The paper tackles the computational inefficiency of tracking traveler states in explicit mobility-based metapopulation models for epidemics, which scales quadratically with the number of patches, by introducing a Runge-Kutta stage-aligned computation method that reduces the system to linear scaling and achieves speedups of up to 76 times for first-order and 50 times for fourth-order methods.
Metapopulation models are powerful tools for capturing the spatio-temporal spread of infectious diseases. Models that explicitly account for traveler origins and destinations, such as Lagrangian metapopulation models, enable a detailed representation of mobility and traveling subpopulations. However, in densely connected networks, tracking these subpopulations leads to quadratic growth in system size with the number of spatial patches. While specific approaches reducing the effort of traveler state estimation have been proposed, these approaches are either model-specific or heuristic. Here, we introduce a Runge-Kutta (RK) stage-aligned computation of traveler states that leverages the precomputed intermediate stage values of explicit RK methods under the assumption of localized homogeneous mixing. We prove that the resulting numerical solution is identical to that of the standard Lagrangian formulation when solved with the corresponding RK method. For compartments without inflows, we further show that the exact same results can be obtained using a simple algebraic scaling based on the initial traveler share. When embedded in a recently proposed metapopulation framework that combines local dynamics with discrete mobility, the stage-aligned approach eliminates the need for heuristic traveler approximations. In contrast to the standard Lagrangian formulation, the resulting method enables efficient simulations by reducing the global ODE system to linear scaling in the number of patches, while the remaining quadratic interactions are handled through highly efficient algebraic updates. Numerical experiments confirm the theoretical results, demonstrating optimal convergence order. Benchmarks on fully connected networks with up to 1025 patches, 1024 local travel connections, and six age groups achieve speedups of up to 76 and 50 for first- and fourth-order Runge-Kutta methods, respectively.