Monday 24.06.2019 13.30 – 14.00
Seminar room A142, T-building
Efficient limited time reachability estimation in temporal networks
Time-limited states characterise several dynamical processes evolving on the top of networks: During epidemic spreading infected agents may recover after some times, or in travel routing systems passengers may not wait forever for a connection. These systems can be commonly described as limited waiting-time processes. As an efficient representation of temporal networks, temporal event graphs have been proposed recently, which could map time-respecting paths all at once to study how they form connected structures in the temporal network fabric. However, their analysis has been limited to their weakly connected components, which only give an upper bound for in- and out-components determining the downstream outcome of any dynamical processes. Here we propose a probabilistic counting algorithm, which gives estimates of the in- or out-reachability (with any chosen waiting-time limit) for every starting event in a temporal network. The computational complexity of this method allows measurements for temporal networks with hundreds of millions of events with current commodity computing hardware. This opens up the possibility to analyse reachability, spreading processes, and other dynamics in large temporal networks in completely new ways; to compute centralities based on global reachability for all events; or to find the exact node and time, which could lead to the largest epidemic outbreak with high probability.