Stable Subgraph Isomorphism Search in Temporal Networks

Qi Zhang, Rong-Hua Li, Hongchao Qin, Guoren Wang, Zhiwei Zhang, Ye Yuan

Abstract

In this paper, we study a new problem of seeking stable subgraph isomorphisms for a query graph in a temporal graph. To solve our problem, we first develop a pruning-based search algorithm using several new pruning tricks to prune the unpromising matching results during the search procedure. To further improve the efficiency, we propose a novel index structure called <inline-formula><tex-math notation="LaTeX">${{\mathsf {BCCIndex}}}$</tex-math></inline-formula> , based on an idea of bi-connected component decomposition of the query graph, which can efficiently support the stable subgraph isomorphism search. Equipped with the <inline-formula><tex-math notation="LaTeX">${{\mathsf {BCCIndex}}}$</tex-math></inline-formula> , we present an efficient query processing algorithm based on a carefully designed tree join technique. We conduct extensive experiments to evaluate our algorithms on four large real-life datasets, and the results demonstrate the efficiency and effectiveness of our algorithms.
BibTeX
@article{zhang2023stable,
  author = {Qi Zhang and Rong-Hua Li and Hongchao Qin and Guoren Wang and Zhiwei Zhang and Ye Yuan},
  title = {{Stable Subgraph Isomorphism Search in Temporal Networks}},
  journal = {IEEE Trans. Knowl. Data Eng.},
  year = {2023},
  doi = {10.1109/tkde.2022.3175800},
}

Loading related content...

Figure