Temporal paths discovery with multiple constraints in attributed dynamic graphs

Anqi Zhao, Guanfeng Liu*, Bolong Zheng, Yan Zhao, Kai Zheng

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

Temporal path discovery in dynamic graphs is significant in many applications, such as the trip planning in transportation networks, and the disease progression tracking in gene networks. Attributed Dynamic Graph (ADG) contains multiple value-changed attributes on edges, such as the speed of a bus between two stations, and the price of the bus ticket in different time periods. The traditional methods for temporal path discovery in ADGs assume users only consider a single constraint on the attributes in their models, such as finding the fast route to reach the destination under the constraint of a given budget, which makes the path discovery problem simple though it still suffers expensive time cost. However, such an assumption is too strict in real applications, where users can specify multiple constraints, such as finding the fast route under the constraints of a given budget and the total number of stopovers. In such a situation, the temporal path discovery becomes more complicated as it subsumes the classical NP-Complete Multi-Constraint Path (MCP) problem, and thus the traditional methods cannot work for finding a new type of Temporal Path with Multiple Constraints (TPMC). In this paper, we propose a set of new Two-Pass approximation algorithms to bi-directionally search ADGs to find TPMC results. To the best of our knowledge, our Two-Pass algorithms are the first algorithms to support the discovery of the temporal paths with multiple constraints in ADGs. The experimental results on 12 real-world dynamic graphs demonstrate that our algorithms outperform the state-of-the-art methods in both efficiency and effectiveness.

Original languageEnglish
Pages (from-to)313-336
Number of pages24
JournalWorld Wide Web
Volume23
Issue number1
Early online date12 Mar 2019
DOIs
Publication statusPublished - Jan 2020

Keywords

  • Graph
  • Multiple constraints
  • Path discovery

Fingerprint Dive into the research topics of 'Temporal paths discovery with multiple constraints in attributed dynamic graphs'. Together they form a unique fingerprint.

Cite this