Mammal Clique Enumeration (MCE) is one of the most fundamental problems in graph theory, and it has extensive applications in graph data analysis. The state-of-art approach (called as MCE_(degeneracy) in this paper) that solves MCE problem in real-world graphs first computes the degeneracy ordering of the vertices in a given graph, and then for each vertex, conducts the BK_(pivot) algorithm in its neighborhood (called as degeneracy neighborhood in this paper). In real-world graphs, the process of degeneracy ordering produces a large number of dense degeneracy neighborhoods. But, the BK_(pivot) algorithm, with its down-to-top nature, adds just one vertex into the result set at each level of recursive calls, and cannot efficiently solve the MCE problem in these dense degeneracy neighborhoods. In this paper, we propose a new MCE algorithm, called as BK_(rcd), to improve the efficiency of MCE in a dense degeneracy neighborhood by recursively conducting core decomposition in it. Contrary to BK_(pivot), BK_(rcd) is a top-to-down approach, that repeatedly chooses and "removes" the vertex with the smallest degree until a clique is reached. We further integrate BK_(rcd) into MCE_(degeneracy) to form a hybrid approach named as MCE_(degeneracy)~(hybrid), that chooses BK_(rcd) or BK(pivot) adap-tively according to the structural properties of the degeneracy neighborhoods. Experimental results conducted in real-world graphs show that MCE_(degeneracy)~(hybrid)achieves high overall performance improvements on the graphs. For example, MCE_(degeneracy)~(hybrid)achieves 1.34 × to 2.97 × speedups over MCE_(degeneracy) in web graphs taken in our experiments.
展开▼
