摘要
随着海量数据的迅猛增长以及大数据时代的开启,涌现出大量的基于超大规模时序图的应用,并对经典图论算法中的可达性问题提出新的挑战。传统的可达性算法缺少对非静态性、时效性的充分考虑,因此在时序图上的运行可能导致错误结果,并且不能充分利用时序图的特性提升运行效率。考虑到时序性对于时序图的重要性,提出一种新颖的算法Bi-BFS,通过充分利用结点之间的时序性约束,并借助于现有的高效索引结构,可以快速地确定超大规模时序图上任意两个结点之间的可达性。与同类算法之间的实验表明,新算法的运行效率得到较大的提升。
Reachability over a massive graph is a fundamental graph problem with numerous applications. However, the concept of a classic reacha-bility algorithm is insufficient for a temporal graph, as it does not consider the temporal information, which is vital for determining the reachability between two nodes. Proposes an efficient online algorithm Bi-BFS for answering the reachability problem in a massive tempo-ral graph. The proposed approach fully explores the time constraints among edges in a temporal graph, and utilizes an index to speed up the computation. Various experimental results demonstrate that the algorithm outperforms competitors greatly.
关键词
可达性
时序图
算法
Reachability
Temporal Graph
Algorithm
