2019/08/30 by Anne-Sophie Himmel, Matthias Bentert, Himmel, Anne-Sophie +5 · 3 citations
Computer Science · Social Sciences · #Caching and Content Delivery #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Human Mobility and Location-Based Analysis #Opportunistic and Delay-Tolerant Networks
paper · pdf · doi:10.48550/arxiv.1909.01152
openalex publication_date 2019/08/30 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28
Node connectivity plays a central role in temporal network analysis. We\nprovide a comprehensive study of various concepts of walks in temporal graphs,\nthat is, graphs with fixed vertex sets but edge sets changing over time. Taking\ninto account the temporal aspect leads to a rich set of optimization criteria\nfor "shortest" walks. Extending and significantly broadening state-of-the-art\nwork of Wu et al. [IEEE TKDE 2016], we provide an algorithm for computing\noptimal walks that is capable to deal with various optimization criteria and\nany linear combination of these. It runs in O (|V| + |E| \log |E|) time where\n|V| is the number of vertices and |E| is the number of time edges. A\ncentral distinguishing factor to Wu et al.'s work is that our model allows to,\nmotivated by real-world applications, respect waiting-time constraints for\nvertices, that is, the minimum and maximum waiting time allowed in intermediate\nvertices of a walk. Moreover, other than Wu et al. our algorithm also allows to\nsearch for walks that pass multiple subsequent edges in one time step, and it\ncan optimize a richer set of optimization criteria. Our experimental studies\nindicate that our richer modeling can be achieved without significantly\nworsening the running time when compared to Wu et al.'s algorithms.\n