This paper studies the problem of durable community search on temporal graphs. Given a temporal graph \(G_{[s,e]}\) , a positive integer k, and a keyword set Q, we attempt to detect all connected k-trusses H of \(G_{[s,e]}\)  with (1) the keywords of H cover Q, (2) H has the largest existence interval. (3) there is no such k-truss \(H'\supseteq H\) while also satisfying (1) and (2). This problem has many applications, such as bio-network analysis and anomaly detection. However, there is no efficient solution in the literature. In this paper, we first analyze the existence of durable communities among related time intervals and then devise a binary search-based method, namely BinaryDCS, which can skip fruitless intervals correctly. Besides, we optimize the intersection of snapshots by the segment tree. After that, we develop a novel framework, i.e., IncrementDCS, to enhance the pruning capacity by exploring the subintervals more orderly. Comprehensive performance studies on 3 real datasets show that our proposals outperform the baselines by up to 2 orders of magnitude.

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

Durable Community Search on Temporal Graphs

  • Jianhua Wang,
  • Jianye Yang,
  • Wu Yao,
  • Ziyi Ma,
  • Zhaoquan Gu,
  • Chengyuan Zhang

摘要

This paper studies the problem of durable community search on temporal graphs. Given a temporal graph \(G_{[s,e]}\) , a positive integer k, and a keyword set Q, we attempt to detect all connected k-trusses H of \(G_{[s,e]}\)  with (1) the keywords of H cover Q, (2) H has the largest existence interval. (3) there is no such k-truss \(H'\supseteq H\) while also satisfying (1) and (2). This problem has many applications, such as bio-network analysis and anomaly detection. However, there is no efficient solution in the literature. In this paper, we first analyze the existence of durable communities among related time intervals and then devise a binary search-based method, namely BinaryDCS, which can skip fruitless intervals correctly. Besides, we optimize the intersection of snapshots by the segment tree. After that, we develop a novel framework, i.e., IncrementDCS, to enhance the pruning capacity by exploring the subintervals more orderly. Comprehensive performance studies on 3 real datasets show that our proposals outperform the baselines by up to 2 orders of magnitude.