Time-Respecting Flow Graph Pattern Matching on Temporal Graphs
Yunjun Gao, Tianming Zhang, Linshan Qiu, Qingyuan Linghu, Gang Chen
Abstract
Graph pattern matching has been extensively investigated on general graphs without time information over decades. Nevertheless, few studies focus on temporal graphs, where a relationship between two vertices takes place at a specific moment and lingers for some time. In this paper, we propose a new notion so-called <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">time-respecting flow graph</i> , in which all paths are time-respecting (i.e., a sequence of contacts with non-decreasing time), and one vertex is distinguished as the root, from which other vertices can be reached via a time-respecting path. Based on this, we explore the problem of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">time-respecting flow graph pattern matching on temporal graphs</i> . This problem motivates important applications in epidemiology, information diffusion, crime detection, etc. To address it, we present one baseline algorithm as well as two optimized algorithms that utilize several efficient matching strategies and topological sort based technique to boost efficiency. Extensive experimental evaluation using both real and synthetic data sets demonstrates the effectiveness and efficiency of our proposed algorithms. Compared with baseline method, our optimized algorithms could achieve up to three orders of magnitude speedup.