buTCS: An Optimized Algorithm for Estimating the Size of Transitive Closure

Abstract

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. TC size is very important in many applications but the cost of TC size computation is high in both time and space, which makes computing accurate TC size not applicable to the scenario where we need to know the TC size quickly for large graphs. Considering that existing approaches are either inefficient or inaccurate, we propose an algorithm, namely buTCS, to efficiently make more accurate estimation. Our approach works in linear time and space. The basic idea is to compute a node’s TC size 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 that buTCS achieves better estimation on TC size efficiently.

Keywords

• Directed graph
• transitive closure size
• spanning tree