| Given a data graph G,clique is a subgraph of G,in which there is an edge between each pair of vertices,and maximal clique is a clique which is not included by other cliques.Maximal clique enumeration researches how to mine all maximal cliques of the given graph,which is widely applied to communication network,protein interaction network,biosystem control network and social networks and so on.With the rapid development of Internet technology,graph datas are often uncertain because of the differences of their resources.In this paper,the problem of maximal cliques enumeration on uncertain graphs is researched.The research contents are as follows.Firstly,through the deeply analysis of the existing algorithms,we find the problem of low efficiency and poor expansibility of the existing algorithms.Secondly,we propose a maximal clique enumeration algorithm named EUMC that is based on subgraph partition.First of all,the algorithm treats the given uncertain graph as a deterministic graph and gets the maximal cliques.Then,based on the obtained maximal clique,with the uncertain information in the graph,the uncertain maximal clique set is enumerated.At last,the uncertain maximal clique set is sorted in descending order according to the uncertain maximal clique size.Thirdly,we propose an efficient algorithm about pseudo maximum clique verification,named DPMC.On the basis of sorting the maximum cliques enumerated,when the DPMC algorithm checks whether each maximal clique is contained by a clique,it is not necessary to compare all the cliques in front of it.The basic idea of the verification is to dynamically construct the inverted list of each vertex,which contains the number of the corresponding verified clique.In this way,the verification of cliques is converted into the set intersection operation of the inverted list corresponding to the vertex number.Finally,based on the experiments of 9 real data sets,we verify the efficiency of the algorithm proposed in this paper. |
PDF Full Text Request