buTCS: An Optimized Algorithm for Estimating the Size of Transitive Closure
Xiaozhe Li, Xuan Wang, Junfeng Zhou, Ming Du · IEEE Access · 2021
Given a directed graph and a node$v$, the transitive closure (TC) of$v$is the set of nodes that$v$can reach in the graph.TCsize is very important in many applications but the cost ofTCsize computation is high in both time and space, which makes computing accurateTCsize not applicable to the scenario where we need to know theTCsize quickly for large graphs. Considering that existing approaches are either inefficient or inaccurate, we propose an algorithm, namelybuTCS, to efficiently make more accurate estimation. Our approach works in linear time and space. The basic idea is to compute a node’sTCsize based on that of its out-neighbors and perform a top-down verification. We further propose two optimizations to improve the estimation accuracy. The experimental results on 13 real datasets show thatbuTCSachieves better estimation onTCsize efficiently.