Research On Mining Algorithm Of Maximal Clique In Uncertain Graph

As an important data structure,maximal clique plays an important role in bioinformatics,wireless sensor networks,social networks and other fields.The mining of maximal clique in graph has a long history,and there have been many research results.However,in practical application,the differences of data sources and the limitations of acquisition technology make a large number of graph data uncertain.How to mine maximal clique in uncertain graph has become the latest challenge for researchers.The existing algorithms for mining maximal cliques of uncertain graphs usually adopt the clipping strategy and the recursive backtracking idea based on MULE algorithm to mine all maximal cliques in the reduced uncertain graph.However,due to the too many recursive times of the algorithm and the complexity of probability calculation,the algorithm is very timeconsuming.Starting from the above problems,this topic carries out the following research:Firstly,aiming at the problems of many recursions and the time-consuming updating of vertex sets in the classical maximal clique mining algorithm,combined with the definition of clique probability,a maximal clique mining algorithm in uncertain graph is proposed to calculate the set probability before recursion to reduce the number of recursion.Based on the existing algorithms,only the candidate vertex set is maintained,and the calculation of the used vertex set is deleted.According to the size of the candidate vertex set and the vertex set to be expanded,the expanded set probability is calculated from two cases,and it is verified whether it is α-clique.For all the excavated α-cliques,an improved maximal clique verification algorithm is proposed.Combined with the characteristic that the pseudo maximal clique is first included by the maximal clique with the largest number of vertices,the inverted table of vertices is used to remove the pseudo maximal clique.Secondly,a Top-K maximal clique mining algorithm in uncertain graphs is proposed to screen out the top K α-maximal cliques that satisfy the clique probability threshold and are the largest.In order to get a large maximal clique as soon as possible,this paper uses the algorithm based on binary search,takes the degree of vertex as the basis for dividing the interval,calls the improved maximal clique mining algorithm in the interval with large degree first,and constantly updates the search interval to obtain the Top-K maximal clique.In order to improve the efficiency of the algorithm,a clipping strategy based on edge probability is adopted,and the core number of vertices in the graph is used as a tighter upper limit of the search interval to narrow the search range of uncertain graphs.Finally,the improved maximal clique mining algorithm and Top-K maximal clique mining algorithm are verified and analyzed on different real data sets.