Research On Degeneracy Algorithm For Massive Graph

In recent years,massive graph data management and mining has become a research hotspot in the academic and industrial circles.In massive graph data,it usually contains a tightly connected community structure.Searching for a tightly connected community structure from massive graph data has important scientific value and a wide range of practical applications.The current mainstream community search technologies mainly include community search based on the maximal clique and community search based on the k-core or other dense subgraph model.The efficiency of these algorithms is usually depends on the degeneracy of the graph.Degeneracy is an important indicator for measuring network sparsity.Designing a fast degeneracy computation algorithm can greatly optimize the maximal clique enumeration algorithm.In addition,degeneracy is a2-approximation of the maximum subgraphs problem,and it is also the 2-approximation of the arboricity of the classical graph.Degeneracy is also an important indicator of the sparsity of the graph.Many network analysis algorithms,such as maximal clique enumeration,triangle enumeration,and truss decomposition,work very well in graphs with small degeneracy.In view of the important application of degeneracy,this paper studies the degeneracy computation algorithm of massive graph data.A semi-external algorithm based on binary search and node reduction techniques is proposed.The algorithm only needs O(n)memory space to compute the degeneracy of massive graph data,where n represents the number of nodes,so the algorithm can be adapted to super massive graph data.Moreover,this paper also applies this semi-external algorithm to solve the k-peak decomposition problem of massive graph data,and obtain a fast semi-external k-peak decomposition algorithm.In addition,this paper also proposes an efficient semi-external degeneracymaintenance algorithm for dynamic graph data.Finally,a large-scale experimental test is carried out on the real graph dataset,and the results verify the effectiveness and scalability of the proposed algorithm.Specifically,we systematically analyzed and calculated the degeneracy of 150 real graph data.This is the first systematic computation of the degeneracy of almost all published large graph data.These computation results can provide valuabel practical reference for designing efficient graph data mining algorithms.In addition,on these data sets,this paper also tests the performance of the dynamic maintenance algorithm.For example,in a GSH network with 930 million nodes and 13.3 billion edges,the semi-external degeneracy maintenance algorithm proposed in this paper can complete the dynamic maintenance of degeneracy in an average of 0.1 milliseconds,while the best previous algorithm needs 0.1 second.The algorithm in this paper is nearly three orders of magnitude faster than the the best previous algorithm.Finally,the performance of our proposed algorithm in computing k-peak decomposition is also tested.The experimental results show that our algorithm can compute the k-peak decomposition of massive graph data.