Huanhuan Wu
Abstract
Shortest path is a fundamental graph problem with numerous applications. However, the concept of classic shortest path is insufficient or even flawed in a temporal graph, as the temporal information determines the order of activities along any path. In this paper, we show the shortcomings of classic shortest path in a temporal graph, and study various concepts of "shortest" path for temporal graphs. Computing these temporal paths is challenging as subpaths of a "shortest" path may not be "shortest" in a temporal graph. We investigate properties of the temporal paths and propose efficient algorithms to compute them. We tested our algorithms on real world temporal graphs to verify their efficiency, and also show that temporal paths are essential for studying temporal graphs by comparing shortest paths in normal static graphs.
- A. Casteigts, P. Flocchini, W. Quattrociocchi, and N. Santoro. Time-varying graphs and dynamic networks. International Journal of Parallel, Emergent and Distributed Systems, 27(5):387--408, 2012. Google Scholar
Digital Library
- J. Cheng, S. Huang, H. Wu, and A. W.-C. Fu. Tf-label: a topological-folding labeling scheme for reachability querying in a large graph. In SIGMOD Conference, pages 193--204, 2013. Google ScholarDigital Library
- J. Cheng, Y. Ke, S. Chu, and C. Cheng. Efficient processing of distance queries in large graphs: a vertex cover approach. In SIGMOD Conference, pages 457--468, 2012. Google ScholarDigital Library
- J. Cheng, Z. Shang, H. Cheng, H. Wang, and J. X. Yu. K-reach: Who is in your small world. PVLDB, 5(11):1292--1303, 2012. Google ScholarDigital Library
- J. Cheng, Z. Shang, H. Cheng, H. Wang, and J. X. Yu. Efficient processing of k-hop reachability queries. VLDB J., 23(2):227--252, 2014.Google ScholarCross Ref
- D. Eppstein and J. Wang. Fast approximation of centrality. In SODA, pages 228--229, 2001. Google ScholarDigital Library
- A. W.-C. Fu, H. Wu, J. Cheng, and R. C.-W. Wong. Is-label: an independent-set based labeling scheme for point-to-point distance querying. PVLDB, 6(6):457--468, 2013. Google ScholarDigital Library
- P. Holme and J. Saramäki. Temporal networks. CoRR, abs/1108.1780, 2011.Google Scholar
- S. Huang, J. Cheng, and H. Wu. Temporal graph traversals: Definitions, algorithms, and applications. CoRR, abs/1401.1919, 2014.Google Scholar
- D. Kempe, J. M. Kleinberg, and A. Kumar. Connectivity and inference problems for temporal networks. J. Comput. Syst. Sci., 64(4):820--842, 2002. Google ScholarDigital Library
- G. Kossinets, J. M. Kleinberg, and D. J. Watts. The structure of information pathways in a social communication network. In KDD, pages 435--443, 2008. Google ScholarDigital Library
- V. Kostakos. Temporal graphs. Physica A: Statistical Mechanics and its Applications, 388(6):1007--1023, 2009.Google ScholarCross Ref
- V. Nicosia, J. Tang, M. Musolesi, G. Russo, C. Mascolo, and V. Latora. Components in time-varying graphs. CoRR, abs/1106.2134, 2011.Google Scholar
- R. K. Pan and J. Saramäki. Path lengths, correlations, and centrality in temporal networks. Phys. Rev. E, 84: 016105, 2011.Google ScholarCross Ref
- N. Santoro, W. Quattrociocchi, P. Flocchini, A. Casteigts, and F. Amblard. Time-varying graphs and social network analysis: Temporal indicators and metrics. CoRR, abs/1102.0629, 2011.Google Scholar
- J. Tang, M. Musolesi, C. Mascolo, and V. Latora. Temporal distance metrics for social network analysis. In Proceedings of the ACM Workshop on Online Social Networks, pages 31--36, 2009. Google ScholarDigital Library
- J. Tang, M. Musolesi, C. Mascolo, and V. Latora. Characterising temporal distance and reachability in mobile and online social networks. Computer Communication Review, 40(1):118--124, 2010. Google ScholarDigital Library
- J. Tang, S. Scellato, M. Musolesi, C. Mascolo, and V. Latora. Small-world behavior in time-varying graphs. Physical Review E, 81(5):055101, 2010.Google ScholarCross Ref
- H. Wu, J. Cheng, S. Huang, Y. Ke, Y. Lu, and Y. Xu. Path problems in temporal graphs (preliminary version). www.cse.cuhk.edu.hk/~hhwu/temsp.pdf, 2013.Google Scholar
- L. Xiang, Q. Yuan, S. Zhao, L. Chen, X. Zhang, Q. Yang, and J. Sun. Temporal recommendation on graphs via long- and short-term preference fusion. In KDD, pages 723--732, 2010. Google ScholarDigital Library
- B.-M. B. Xuan, A. Ferreira, and A. Jarry. Computing shortest, fastest, and foremost journeys in dynamic networks. Int. J. Found. Comput. Sci., 14(2):267--285, 2003.Google ScholarCross Ref
Recommendations
Longest Path Problems on Ptolemaic Graphs
Longest path problem is a problem for finding a longest path in a given graph. While the graph classes in which the Hamiltonian path problem can be solved efficiently are widely investigated, there are few known graph classes such that the longest path ...
Path eccentricity of graphs
AbstractLet G be a connected graph. The eccentricity of a path P, denoted by ecc G ( P ), is the maximum distance from P to any vertex in G. In the Central path (CP) problem, our aim is to find a path of minimum eccentricity. This problem was ...
Highlights- Every connected biconvex graph has a dominating path.
- Tight upper bound for ...
From path graphs to directed path graphs
WG'10: Proceedings of the 36th international conference on Graph-theoretic concepts in computer scienceWe present a linear time algorithm to greedily orient the edges of a path graph model to obtain a directed path graph model (when possible). Moreover we extend this algorithm to find an odd sun when the method fails. This algorithm has several ...
Comments