Badie-Modiri Arash, Karsai Márton, Kivelä Mikko
Department of Computer Science, School of Science, Aalto University, FI-0007, Finland.
Department of Network and Data Science, Central European University, H-1051 Budapest, Hungary.
Phys Rev E. 2020 May;101(5-1):052303. doi: 10.1103/PhysRevE.101.052303.
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.
受疾病感染的个体经过一段时间后会康复，人们会忘记在社交网络上传播的消息，或者乘客不会永远等待转机。这些动态过程可被描述为有限等待时间过程，对于建模为时间网络的系统尤为重要。这些过程已通过模拟进行了研究，这等同于从源节点和时间反复找到所有有限等待时间的时间路径。我们提出了一种方法，能以更高效几个数量级的方式来跟踪此类时间路径的可达性。我们的方法能同时估计从每个可能的起始点和时间的入可达性或出可达性（具有任何选定的等待时间限制）。它可在当前商用计算硬件上处理具有数亿个事件的非常大的时间网络。这开辟了以全新方式分析大型时间网络上传播过程的可达性和动态性的可能性。例如，现在可以基于所有事件的全局可达性计算中心性，或者可以高概率地找到会导致最大规模疫情爆发的受感染节点和时间。
