Efficient computation of optimal temporal walks under waiting-time constraints

Applied Network Science - Tập 5 Số 1 - 2020
Matthias Bentert1, Anne-Sophie Himmel1, André Nichterlein1, Rolf Niedermeier1
1Technische Universität Berlin, Faculty IV, Algorithmics and Computational Complexity, Berlin, Germany

Tóm tắt

AbstractNode connectivity plays a central role in temporal network analysis. We provide a broad study of various concepts of walks in temporal graphs, that is, graphs with fixed vertex sets but arc sets changing over time. Taking into account the temporal aspect leads to a rich set of optimization criteria for “shortest” walks. Extending and broadening state-of-the-art work of Wu et al. [IEEE TKDE 2016], we provide an algorithm for computing shortest walks that is capable to deal with various optimization criteria and any linear combination of these. It runs in O(|V|+|E|log|E|) time where |V| is the number of vertices and |E| is the number of time-arcs. A central distinguishing factor to Wu et al.’s work is that our model allows to, motivated by real-world applications, respect waiting-time constraints for vertices, that is, the minimum and maximum waiting time allowed in intermediate vertices of a walk. Moreover, other than Wu et al. our algorithm also allows to search for walks that pass multiple subsequent time-arcs in one time step, and it can deal with a richer set of optimization criteria. Our experimental studies indicate that our richer modeling can be achieved without significantly worsening the running time when compared to Wu et al.’s algorithms.

Từ khóa


Tài liệu tham khảo

Ahuja, RK, Magnanti TL, Orlin JB (1993) Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Upper Saddle River.

Axiotis, K, Fotakis D (2016) On the size and the approximability of minimum temporally connected subgraphs In: Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP ’16), 149–114914.. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Saarbrücken.

Barabási, A-L (2016) Network Science. Cambridge University Press, Cambridge.

Bast, H, Delling D, Goldberg A, Müller-Hannemann M, Pajor T, Sanders P, Wagner D, Werneck RF (2016) Route planning in transportation networks In: Algorithm Engineering - Selected Results and Surveys. Lecture Notes in Computer Science, 19–80.. Springer.

Buß, S, Molter H, Niedermeier R, Rymar M (2020) Algorithmic aspects of temporal betweenness In: Proceedings of the 26th SIGKDD Conference on Knowledge Discovery and Data Mining (KDD ’20), 2084–2092.. ACM.

Casteigts, A, Flocchini P, Godard E, Santoro N, Yamashita M (2015) On the expressivity of time-varying graphs. Theor Comput Sci 590:27–37.

Casteigts, A, Flocchini P, Quattrociocchi W, Santoro N (2012) Time-varying graphs and dynamic networks. Int J Parallel Emergent Distrib Syst 27(5):387–408.

Casteigts, A, Himmel A-S, Molter H, Zschoche P (2019) The computational complexity of finding temporal paths under waiting time constraints. arXiv preprint arXiv:1909.06437. To appear at ISAAC ’20.

Dean, BC (2004) Algorithms for minimum-cost paths in time-dependent networks with waiting policies. Networks 44:41–46.

Fluschnik, T, Molter H, Niedermeier R, Renken M, Zschoche P (2020) Temporal graph classes: A view through temporal separators. Theor Comput Sci 806:197–218.

Fluschnik, T, Niedermeier R, Schubert C, Zschoche P (2020) Multistage s-t path: Confronting similarity with dissimilarity. arXiv preprint arXiv:2002.07569. To appear at ISAAC ’20.

Himmel, A, Bentert M, Nichterlein A, Niedermeier R (2019) Efficient computation of optimal temporal walks under waiting-time constraints In: Proceedings of the 8th International Conference on Complex Networks and Their Applications (COMPLEX NETWORKS ’19). Studies in Computational Intelligence, 494–506.. Springer, New York.

Holme, P (2015) Modern temporal network theory: a colloquium. Eur Phys J B 88(9):234.

Holme, P (2016) Temporal network structures controlling disease spreading. Phys Rev E 94(2):022305.

Holme, P, Saramäki J (2012) Temporal networks. Physics Reports 519(3):97–125.

Holme, P, Saramäki J (2013) Temporal networks as a modeling framework. In: Holme P Saramäki J (eds)Temporal Networks, 1–14.. Springer, New York.

Holme, P, Saramäki J (2019) Temporal Network Theory. Springer, New York.

Kempe, D, Kleinberg J, Kumar A (2002) Connectivity and inference problems for temporal networks. J Comput Syst Sci 64(4):820–842.

Kim, H, Anderson R (2012) Temporal node centrality in complex networks. Phys Rev E 85(2):026107.

Kivelä, M, Cambe J, Saramäki J, Karsai M (2018) Mapping temporal-network percolation to weighted, static event graphs. Sci Rep 8(1):12357.

KONECT (2017) DNC emails network dataset. Inst Web Sci Technol. http://konect.uni-koblenz.de/networks/dnc-temporalGraph. Accessed 2017.

Lightenberg, W, Pei Y, Fletcher G, Pechenizkiy M (2018) Tink: A temporal graph analytics library for Apache Flink In: Proc. of WWW ’18, 71–72.. ACM, New York.

Masuda, N, Holme P (2013) Predicting and controlling infectious disease epidemics using temporal networks. F1000prime Rep 5.

Mertzios, GB, Michail O, Spirakis PG (2019) Temporal network optimization subject to connectivity constraints. Algorithmica 81(4):1416–1449.

Modiri, AB, Karsai M, Kivelä M (2019) Efficient limited time reachability estimation in temporal networks. arXiv preprint arXiv:1908.11831.

Newman, MEJ (2018) Networks. Oxford University Press, Oxford.

Nicosia, V, Tang J, Mascolo C, Musolesi M, Russo G, Latora V (2013) Graph metrics for temporal networks In: Temporal Networks, 15–40.. Springer, New York.

Nicosia, V, Tang J, Musolesi M, Russo G, Mascolo C, Latora V (2012) Components in time-varying graphs. Chaos Interdisc J Nonlinear Sci 22(2):023101.

Pan, RK, Saramäki J (2011) Path lengths, correlations, and centrality in temporal networks. Phys Rev E 84(1):016105.

Rad, AA, Flocchini P, Gaudet J (2017) Computation and analysis of temporal betweenness in a knowledge mobilization network. Comput Soc Netw 4(1):5.

Salathé, M, Kazandjieva M, Lee JW, Levis P, Feldman MW, Jones JH (2010) A high-resolution human contact network for infectious disease transmission. Proc Natl Acad Sci 107(51):22020–22025.

Santoro, N, Quattrociocchi W, Flocchini P, Casteigts A, Amblard F2011. Time-varying graphs and social network analysis: Temporal indicators and metrics.

Wu, H, Cheng J, Ke Y, Huang S, Huang Y, Wu H (2016) Efficient algorithms for temporal path computation. IEEE Trans Knowl Data Eng 28(11):2927–2942.

Xuan, BB, Ferreira A, Jarry A (2003) Computing shortest, fastest, and foremost journeys in dynamic networks. Int J Found Comput Sci 14(02):267–285.

Zschoche, P, Fluschnik T, Molter H, Niedermeier R (2020) The complexity of finding small separators in temporal graphs. J Comput Syst Sci 107:72–92.

Thông tin
Thông tin xuất bản

Applied Network Science

Tập 5 Số 1

Thông tin tác giả