Scholarlink

<p>In many real-world applications, the relationships between entities can be modeled as temporal graphs, where each edge is associated with a timestamp representing the interaction time. As a fundamental problem in network science, the connected component (CC) query has received tremendous research attention. Existing works on CC queries in the temporal graph find sets of vertices that are either connected in every timestamp of a time interval, or connected by paths with edges of increasing timestamps (i.e., time-respecting paths). However, these temporal constraints are too strict for applications without needing time-respecting paths. In this paper, we relax the above constraints by introducing a novel CC model, called window-CC, for both the undirected and directed temporal graphs in a given time window. We first propose online algorithms to query the window-CC, and further develop efficient and scalable index-based solutions. Besides, to handle queries on large dynamic temporal graphs, we also design efficient algorithms to dynamically update indices for new edges. Experimental results on real-world large-scale temporal graphs (both undirected and directed) demonstrate that our solutions achieve triple advantages: <OrderedList> <ListItem> <ItemNumber>1.</ItemNumber> <ItemContent> <p>Our best index-based query algorithms are up to four and two orders of magnitude faster than the two online algorithms, respectively.</p> </ItemContent> </ListItem> <ListItem> <ItemNumber>2.</ItemNumber> <ItemContent> <p>Compared with the baseline indices, our optimized indices cost much less space in both theory and practice.</p> </ItemContent> </ListItem> <ListItem> <ItemNumber>3.</ItemNumber> <ItemContent> <p>Experiments also demonstrate the high efficiency of our index construction and update algorithms.</p> </ItemContent> </ListItem> </OrderedList></p>

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

Efficiently querying connected components in large temporal graphs via scalable and maintainable indices

  • 期刊论文

  • 发表日期：

    2026年5月8日

查看全文
  • Yuyang Xia,
  • Haoxuan Xie,
  • Yixiang Fang,
  • Wensheng Luo,
  • Chenhao Ma,
  • Dong Wen

摘要

In many real-world applications, the relationships between entities can be modeled as temporal graphs, where each edge is associated with a timestamp representing the interaction time. As a fundamental problem in network science, the connected component (CC) query has received tremendous research attention. Existing works on CC queries in the temporal graph find sets of vertices that are either connected in every timestamp of a time interval, or connected by paths with edges of increasing timestamps (i.e., time-respecting paths). However, these temporal constraints are too strict for applications without needing time-respecting paths. In this paper, we relax the above constraints by introducing a novel CC model, called window-CC, for both the undirected and directed temporal graphs in a given time window. We first propose online algorithms to query the window-CC, and further develop efficient and scalable index-based solutions. Besides, to handle queries on large dynamic temporal graphs, we also design efficient algorithms to dynamically update indices for new edges. Experimental results on real-world large-scale temporal graphs (both undirected and directed) demonstrate that our solutions achieve triple advantages: 1.

Our best index-based query algorithms are up to four and two orders of magnitude faster than the two online algorithms, respectively.

2.

Compared with the baseline indices, our optimized indices cost much less space in both theory and practice.

 3.

Experiments also demonstrate the high efficiency of our index construction and update algorithms.