Graph simulation on large scale temporal graphs

Yuliang Ma, Ye Yuan*, Meng Liu, Guoren Wang, Yishu Wang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)

Abstract

Graph simulation is one of the most important queries in graph pattern matching, and it is being increasingly used in various applications, e.g., protein interaction networks, software plagiarism detection. Most previous studies mainly focused on the simulation problem on static graphs, which neglected the temporal factors in daily life. In this paper, we investigate a novel problem, namely, temporal bounded simulation on temporal graphs. Specifically, given a pattern query Q with bound constraint and a temporal graph G, we aim to find out the matches Q(G) of Q on G, such that Q(G) satisfies temporal reachability and bound constraint of Q. To tackle this problem efficiently, we propose a simulation matching framework, which consists of three phases, namely pattern segmentation, temporal bounded simulation of pattern segments, and result integration. We first divide the Q into simple small subgraphs (segments). We construct a temporal reachable tree of G. Based on the tree, we propose a basic matching algorithm for the pattern segments. Furthermore, we propose two optimization algorithms by leveraging multi-layer partition strategy to accelerate query processing. After that, we integrate the simulation results obtained from the pattern segments according to the constraints of temporal reachability and the bound of query pattern. Finally, we use real temporal and synthetic datasets to empirically verify the efficiency and effectiveness of our solutions for temporal bounded simulation matching.

Original languageEnglish
Pages (from-to)199-220
Number of pages22
JournalGeoInformatica
Volume24
Issue number1
DOIs
Publication statusPublished - 1 Jan 2020

Keywords

  • Graph simulation
  • Pattern match
  • Temporal graph

Fingerprint

Dive into the research topics of 'Graph simulation on large scale temporal graphs'. Together they form a unique fingerprint.

Cite this