Abstract
Reachability over a massive graph is a fundamental graph problem with numerous applications. However, the concept of a classic reachability algorithm is insufficient for a temporal graph, as it does not consider the temporal information, which is vital for determining the reachability between two nodes. In this paper, we propose an efficient algorithm for answering the reachability problem in a temporal graph. Our approach fully explores the time constraints among edges in a temporal graph, and utilizes an index to speed up the computation. Furthermore, online graph update is supported. Various experimental results demonstrate that our algorithm outperforms competitors greatly.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Cheng, J., Huang, S., Wu, H., Fu, A.W.-C.: TF-label: a topological-folding labeling scheme for reachability querying in a large graph. In: Proceedings of the SIGMOD Conference, pp. 192–204 (2013)
Cheng, J., Ke, Y., Chu, S., Cheng, C.: Efficient processing of distance queries in large graphs: a vertex cover approach. In: Proceedings of the SIGMOD Conference, pp. 457–468 (2012)
Cheng, J., Shang, Z., Cheng, H., Wang, H., Yu, J.X.: Efficient processing of k-hop reachability queries. VLDB J. 23(2), 227–252 (2014)
Kempe, D., Kleinberg, J.M., Kumar, A.: Connectivity and inference problems for temporal networks. J. Comput. Syst. Sci. 64(4), 820–842 (2002)
Tang, J., Musolesi, M., Mascolo, C., Latora, V.: Temporal distance metrics for social network analysis. In: Proceedings of the ACM Workshop on Online Social Networks, pp. 31–36 (2009)
**ang, L., Yuan, Q., Zhao, S., Chen, L., Zhang, X., Yang, Q., Sun, J.: Temporal recommendation on graph via long- and short-term preference fusion. In: Proceedings of the KDD, pp. 723–732 (2010)
Xuan, B.-M.B., Ferreira, A., Jarry, A.: Computing shortest, fastest, and foremost journeys in dynamics networks. Int. J. Found. Comput. Sci. 14(2), 267–285 (2003)
Wu, H., Cheng, J., Huang, S., Ke, Y., Lu, Y., Xu, Y.: Path problems in temporal graphs. In: Proceedings of the VLDB Conference, pp. 721–732 (2014)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Liu, K., Fan, X. (2017). Reachability Problem in Temporal Graphs. In: Yuan, H., Geng, J., Bian, F. (eds) Geo-Spatial Knowledge and Intelligence. GRMSE 2016. Communications in Computer and Information Science, vol 698. Springer, Singapore. https://doi.org/10.1007/978-981-10-3966-9_45
Download citation
DOI: https://doi.org/10.1007/978-981-10-3966-9_45
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-10-3965-2
Online ISBN: 978-981-10-3966-9
eBook Packages: Computer ScienceComputer Science (R0)