Efficient limited-time reachability estimation in temporal networks

Abstract

Time-limited states characterise many dynamical processes on networks: disease infected individuals recover after some time, people forget news spreading on social networks, or passengers may not wait forever for a connection. These dynamics can be described as limited waiting-time processes, and they are particularly important for systems modelled as temporal networks. These processes have been studied via simulations, which is equivalent to repeatedly finding all limited-waiting time temporal paths from a source node and time. We propose a method yielding orders of magnitude more efficient way of tracking the reachability of such temporal paths. Our method gives simultaneous estimates of the in- or out-reachability (with any chosen waiting-time limit) from every possible starting point and time. It works on very large temporal networks with hundreds of millions of events on current commodity computing hardware. This opens up the possibility to analyse reachability and dynamics of spreading processes on large temporal networks in completely new ways. For example, one can now compute centralities based on global reachability for all events or can find with high probability the infected node and time, which would lead to the largest epidemic outbreak.

arXiv commentSoftware implementation available at https://doi.org/10.5281/zenodo.3369893

References in corpus (11)

• Statistical physics of social dynamics
• Epidemic processes in complex networks
• Temporal Networks
• Nonequilibrium Critical Phenomena and Phase Transitions into Absorbing States
• Small But Slow World: How Network Topology and Burstiness Slow Down Spreading
• Modern temporal network theory: A colloquium
• A fast Monte Carlo algorithm for site or bond percolation
• Network reachability of real-world contact sequences
• Optimal Containment of Epidemics in Temporal and Adaptive Networks
• Multiscale Analysis of Spreading in a Large Communication Network
• The Temporal Event Graph

Cited by in corpus (7)

• Fast and principled simulations of the SIR model on temporal networks
• Directed Percolation in Temporal Networks
• Directed Percolation in Random Temporal Network Models with Heterogeneities
• Reticula: A temporal network and hypergraph analysis software package
• Quantifying agent impacts on contact sequences in social interactions
• Hidden dependence of spreading vulnerability on topological complexity
• DyANE: Dynamics-aware node embedding for temporal networks