Research On Transitive Reduction For Large Graphs

Given a directed acyclic graph(DAG) G, the transitive reduction of G is the smallest DAG that has the same transitive closure with G. Transfer reduction is one of the classic problems in graph theory, and it is widely used to solve the reduction problem in practice. The reduction problem includes the transitive closure, knapsack problem, reachability query. However, the existing methods need the high cost. With the emergence of new applications and the rapid development of network technology, the scale of graph is growing. Considering that existing algorithms on transitive reduction cannot scale to large graphs in practice for the memory limit, the paper solves the shortcoming from the following aspects:Firstly, we propose an algorithm based bottom-up, named BUTR. BUTR firstly gets path decomposition, then processes nodes of each path in bottom-up way and can utilize the parent-child relationship of nodes in each path p to avoid the redundant cost of repeatedly visiting many vertexes and edges, and guarantees that each involved edge is visited only once after processing a path. We get the transitive reduction graph until all paths are processed. The time and space complexities of BUTR are O(km) and O(n), where m is the number of nodes and n is the number of edges in G.Secondly, we propose an algorithm TDTR to reduce the redundant computation in the BUTR. TDTR processes the transitive reduction through the stack to cache node and mark its inverse transitive closure. And it uses the relationships between nodes to avoid redundant computation in BUTR as early as possible. The time and space complexities are O(wavgm) and O(n), wavg is the average number of accessing edges in TDTR.Finally, our experimental results on 26 real datasets and 10 synthetic datasets show that compared with existing algorithms, BUTR and TDTR achieve better time and space scalability.