Research On Transitive Reduction For Large Graphs

The graph has its extensive application in the Internet technology.However,with the rapid development of the Internet,the scale of the graph has also become very large.How to simplify the diagram to improve the scalability of the system is one of the hot topics that the research community is concerned about.The transfer protocol is the core operation in the graph operation,and the purpose of simplification is achieved by removing the redundant edges in the directed acyclic graph G.However,the existing transfer reduction algorithm has a large time and space complexity and cannot handle large-scale directed acyclic graphs.Aiming at the existing problems,this paper proposes a transfer protocol algorithm for large graphs.The specific research contents are as follows.First,based on the nature of redundant edges,the idea of using existing reachability query algorithm to accelerate redundant edge judgment is proposed.Considering that the complexity of calculating the reachability of each sibling is high,we propose an algorithm that processes the siblings according to the results of topology sorted in turn to obtain the result of passing the protocol.Secondly,large and small side redundant vertices may be present high cost of handling the problem for a degree,A method of ascending sorting is proposed to process each vertex(out-degree + in-degree)in order to avoid the existence of redundant computations.The advantage is that the small vertices are processed first,and when the post-processing vertices are large,the good polygons associated with the large vertices have been marked,this effectively reduces the number of processing edges that are associated with large vertices and reduces the processing cost of large vertices.Finally,the experiments in this paper are based on 28 real data sets of different sizes,and the experimental results are compared and analyzed from multiple angles,which verifies the high efficiency and scalability of the algorithm.