Efficient limited-time reachability estimation in temporal networks
Loading...
Access rights
openAccess
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Date
2020-05-07
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
11
Series
Physical Review E, Volume 101, issue 5
Abstract
Time-limited states characterize 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 modeled 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 an 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 analyze 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.Description
Keywords
SIZE
Other note
Citation
Badie-Modiri, A, Karsai, M & Kivela, M 2020, ' Efficient limited-time reachability estimation in temporal networks ', Physical Review E, vol. 101, no. 5, 052303 . https://doi.org/10.1103/PhysRevE.101.052303