Research On The Compression Algorithm Of Big Graph And Operation On Graph

The information of many applications can be regarded as graphs when entity isregarded as node and the relationship between entities is regarded as edge. It cansolve the practical problems very well if we solve the graph problems first. But asthe accumulation of data, the scale of the graph is growing huge gradually. It leadsto the problem that the applications can·t be resolved with traditional algorithms inthe aspect of time complexity and space complexity. Facing this problem, themethod of compressing graph is born at the right time. It reduces the scale of graphby merging nodes or edges. Then the operation is carried out on compressed graphfor reducing the time and space. Based on the point, we come up with the notion ofna ve similarity and compress graph with this notion. At the same time, we recordthe adjacent relationship between nodes by edge code to ensure that thecompression process is lossless. Besides, we can get the original graph from thecompressed graph. What·s more, the compressed graph we get by the compressmethod can support most operations on graph.The operation of cut vertex detection is a traditional operation on graph. Thecut vertex decides the connectivity of graph. We will present the cut vertexdetection algorithm which is called improved deep first search tree algorithm oncompressed graph. It can confirm if the graph has cut vertex or not quickly afterrunning. If the graph has cut vertices, it will return all the cut vertices quickly andaccurately. Triangle list has been researched for ages too. This operation will get allthe clique whose size is3, i.e. triangle. It is helpful to analyze the inside structure ofgraph. We will present triangle list algorithm on compressed graph. This algorithmcan return all the triangles quickly and accurately.The feature of current data is that the scale of data is huge and the speed ofupdate is rapid. The problem will be solved very well while the two characteristicare dealt well. The compress algorithm solves the problem of huge scale of data.But many traditional algorithms can·t solve another feature and they must computeagain for each update every time. This makes even a linear algorithm loss itsadvantage for computing many times. In order to solve this problem, we present the dynamic maintenance algorithm for update. We update graph partly on compressedgraph without decompression dynamically. Then we run the algorithms on theupdated graph to reduce the running time.