.png){kind=icon}
返回
Efficiently Counting Four-Node Motifs in Large-Scale Temporal Graphs
.png){kind=icon}
PRE
AI
DOI：10.1007/s00778-025-00926-8.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
时间模式是频繁出现在时间戳序列中的紧凑子图模式。它们揭示了图数据中的隐含洞察，并指导明智的决策制定。然而，当前用于精确统计时间模式的现有方法在模式涉及四个节点时面临高时间复杂度和不适用的挑战，且难以扩展到更大的时间图。本文提出了一种新颖的精确统计框架，专门针对时间窗口大小受限于固定区间的四节点、三边和四边单交互时间模式。为了加速统计过程，我们首先根据结构特征对所有四节点时间模式进行分类。随后，我们提出了三个快速且精确的子算法，分别用于统计各自类别的模式。为了加速统计过程，我们实现了一系列简单且高效的高效计数器。我们的算法巧妙地利用这些计数器，基于边的信息和相互关系来识别和记录所有时间模式实例，显著提高了统计效率，尤其适用于大规模时间图。我们在14个大型真实世界时间图上的广泛实验证明了我们在效率方面的优越性。结果表明，我们的工作显著优于所有当前最优基线方法，实现了高达25,816倍的性能提升。
Keyword:
Temporal motif
Motif counting
4-node motif
Temporal graph
期刊
IF:
3.8
论文数:
83
被引数:
2.4K
机构
引用论文
.png){kind=icon}
分享收藏
查看更多内容