Efficient limited time reachability estimation in temporal networks

Arash Badie Modiri 1 Márton Karsai 2 Mikko Kivelä 3
2 DANTE - Dynamic Networks : Temporal and Structural Capture Approach
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme, IXXI - Institut Rhône-Alpin des systèmes complexes
Abstract : Time-limited states characterise several dynamical processes evolving on the top of networks. During epidemic spreading infected agents may recover after some times, in case of information diffusion people may forget news or consider it out-dated, or in travel routing systems passengers may not wait forever for a connection. These systems can be described as limited waiting-time processes, which can evolve along possible network paths strongly determined by the time-limited states of the interacting nodes. This is particularly important on temporal networks where the time-scales of interactions are heterogeneous and correlated in various ways. The structure of the temporal paths has previously been studied by finding the reachability from a sampled set of sources or by simulating spreading processes. Recently temporal event graphs were proposed as an efficient representation of temporal networks mapping all time-respecting paths at once so that one could 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 their physically important in- and out-components determining the downstream outcome of any dynamical processes. Here we propose a probabilistic counting algorithm, which gives simultaneous and precise estimates of the in- and out-reachability (with any chosen waiting-time limit) for every starting event in a temporal network. Our method is scalable allowing measurements for temporal networks with hundreds of millions of events. 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 with high probability the exact node and time, which could lead to the largest epidemic outbreak.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

https://hal.inria.fr/hal-02388408
Contributor : Márton Karsai <>
Submitted on : Sunday, December 1, 2019 - 8:37:28 PM
Last modification on : Monday, February 10, 2020 - 12:17:19 PM

Links full text

Identifiers

  • HAL Id : hal-02388408, version 1
  • ARXIV : 1908.11831

Citation

Arash Badie Modiri, Márton Karsai, Mikko Kivelä. Efficient limited time reachability estimation in temporal networks. 2019. ⟨hal-02388408⟩

Share

Metrics

Record views

21