Hop-constrained s-t simple path enumeration (HcPE) is a fundamental problem in graph analysis and has broad applications in the real life. Given a graph G, two vertices s and t, and a hop constraint k, HcPE is to enumerate all simple paths from s to t with length not larger than k. Although there are some existing methods for solving HcPE, they still suffer from costly repeated vertex checks and large search space, leading to poor practical performance. To address the challenges above, we propose SimpleJoin, an efficient join-based method for HcPE which involves the following novel ideas. First, we define and utilize the one-way edge to reduce the number of repeated vertex checks. Second, we propose a new greedy strategy to guide the search for simple paths and reduce the search space. Third, an efficient four-step algorithm is proposed to solve HcPE, which consists of graph reduction to remove redundant vertices and edges, finding one-way edges for reducing repeated vertex checks, bidirectional partial path search guided by greedy strategy, and partial path join to produce the final results. Extensive experiments are conducted on nine real-world datasets to show the efficiency of our proposed method.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Hop-Constrained s-t Simple Path Enumeration: Towards Reducing Repeated Vertex Checks

  • Tong Pei,
  • Bin Wang,
  • Hengzhao Ma,
  • Xiaochun Yang,
  • Rui Ding,
  • Jiayi Qu,
  • Baoyan Song

摘要

Hop-constrained s-t simple path enumeration (HcPE) is a fundamental problem in graph analysis and has broad applications in the real life. Given a graph G, two vertices s and t, and a hop constraint k, HcPE is to enumerate all simple paths from s to t with length not larger than k. Although there are some existing methods for solving HcPE, they still suffer from costly repeated vertex checks and large search space, leading to poor practical performance. To address the challenges above, we propose SimpleJoin, an efficient join-based method for HcPE which involves the following novel ideas. First, we define and utilize the one-way edge to reduce the number of repeated vertex checks. Second, we propose a new greedy strategy to guide the search for simple paths and reduce the search space. Third, an efficient four-step algorithm is proposed to solve HcPE, which consists of graph reduction to remove redundant vertices and edges, finding one-way edges for reducing repeated vertex checks, bidirectional partial path search guided by greedy strategy, and partial path join to produce the final results. Extensive experiments are conducted on nine real-world datasets to show the efficiency of our proposed method.