Abstract
Increasingly, enterprises require efficient graph processing capabilities to store and analyze the evolution of the graph topology over time. While a static graph captures information about the connectedness of vertices at a certain point in time, a time-varying graph keeps track of every data manipulation—insertion and removal of a vertex or an edge—performed on the graph and allows detecting topological changes, such as cluster growth and subgraph densification, and discovering behavioral patterns of the connected entities in the graph. Although temporal graph processing has been an active research area in the past decade, most well-known graph algorithms are defined on static graphs only.
In this paper we study the problem of graph traversals and reachability in the presence of a temporal dimension and derive three classes of temporal traversals from a set of realistic use cases. We validate our prototypical implementations against two graph processing systems, a columnar graph execution engine and a native graph database management system. Our experimental evaluation on a large real-world graph dataset demonstrates the generality and applicability of our solution and shows the scalability of our proposed temporal traversal operators to different graph sizes.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Allen, J.F.: Maintaining knowledge about temporal intervals. Commun. ACM 26(11), 832–843 (1983)
Casteigts, A., Flocchini, P., Mans, B., Santoro, N.: Measuring temporal lags in delay-tolerant networks. In: Proceedings of the IPDPS, pp. 209–218. IEEE (2011)
Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. Int. J. Parallel Emerg. Distrib. Syst. 27(5), 387–408 (2012)
Cattuto, C., Quaggiotto, M., Panisson, A., Averbuch, A.: Time-varying Social Networks in a graph database: A Neo4j use case. In: Proceedings of the GRADES 2013, pp. 1–6 (2013)
Kempe, D., Kleinberg, J., Kumar, A.: Connectivity and inference problems for temporal networks. J. Comput. System Sci. 64(4), 820–842 (2002)
Martínez-Bazan, N., Águila Lorente, M.A., Muntés-Mulero, V., Dominguez-Sal, D., Gómez-Villamor, S., Larriba-Pey, J.L.: Efficient graph management based on bitmap indices. In: Proceedings of the IDEAS, pp. 110–119 (2012)
Nicosia, V., Tang, J., Mascolo, C., Musolesi, M., Russo, G., Latora, V.: Graph metrics for temporal networks. In: Holme, P., Saramäki, J. (eds.) Temporal Networks. UCS, pp. 15–40. Springer, Heidelberg (2013)
Pan, R.K., Saramäki, J.: Path lengths, correlations, and centrality in temporal networks. Phys. Rev. E 84(1), 197–206 (2011)
Paradies, M., Lehner, W., Bornhövd, C.: GRAPHITE: an extensible graph traversal framework for relational database management systems. In: Proceedings of the SSDBM, pp. 29: 1–29: 12 (2015)
Wu, H., Cheng, J., Huang, S., Ke, Y., Lu, Y., Xu, Y.: Path problems in temporal graphs. Proc. VLDB Endow. 7(9), 721–732 (2014)
Acknowledgments
We would like to express our gratitute to Martin Kaufmann, who assisted in carving out the ideas presented in this paper and has given insightful feedback on previous versions of it. Also, Christof Bornhövd has encouraged us in pursuing this research direction and supported us in various ways.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Wildemann, M., Rudolf, M., Paradies, M. (2016). The Time Has Come: Traversal and Reachability in Time-Varying Graphs. In: Wang, F., Luo, G., Weng, C., Khan, A., Mitra, P., Yu, C. (eds) Biomedical Data Management and Graph Online Querying. Big-O(Q) DMAH 2015 2015. Lecture Notes in Computer Science(), vol 9579. Springer, Cham. https://doi.org/10.1007/978-3-319-41576-5_13
Download citation
DOI: https://doi.org/10.1007/978-3-319-41576-5_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-41575-8
Online ISBN: 978-3-319-41576-5
eBook Packages: Computer ScienceComputer Science (R0)