Efficiently Answering Span-Reachability Queries in Large Temporal Graphs
Authors:
- 1 April 2020
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1153-1164
Abstract
Reachability is a fundamental problem in graph analysis. In applications such as social networks and collaboration networks, edges are always associated with timestamps. Most existing works on reachability queries in temporal graphs assume that two vertices are related if they are connected by a path with non-decreasing timestamps (time-respecting) of edges. This assumption fails to capture the relationship between entities involved in the same group or activity with no time-respecting path connecting them. In this paper, we define a new reachability model, called span-reachability, designed to relax the time order dependency and identify the relationship between entities in a given time period. We adopt the idea of two-hop cover and propose an index-based method to answer span-reachability queries. Several optimizations are also given to improve the efficiency of index construction and query processing. We conduct extensive experiments on 17 real-world datasets to show the efficiency of our proposed solution.Keywords
This publication has 31 references indexed in Scilit:
- Temporal networksPhysics Reports, 2012
- Time-varying graphs and dynamic networksInternational Journal of Parallel, Emergent and Distributed Systems, 2012
- Hierarchical Hub Labelings for Shortest Paths2012
- Graph Reachability Queries: A Survey2010
- Structure and time evolution of an Internet dating communitySocial Networks, 2004
- Time-stamped graphs and their associated influence digraphsDiscrete Applied Mathematics, 2003
- COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKSInternational Journal of Foundations of Computer Science, 2003
- Reachability and Distance Queries via 2-Hop LabelsSIAM Journal on Computing, 2003
- Connectivity and Inference Problems for Temporal NetworksJournal of Computer and System Sciences, 2002
- A Greedy Heuristic for the Set-Covering ProblemMathematics of Operations Research, 1979