标题：Fast Maximal Clique Enumeration for Real-World Graphs
作者：Li, Yinuo; Shao, Zhiyuan; Yu, Dongxiao; Liao, Xiaofei; Jin, Hai
通讯作者：Li, Yinuo;Li, YN;Shao, ZY
作者机构：[Li, Yinuo; Shao, Zhiyuan; Liao, Xiaofei; Jin, Hai] Huazhong Univ Sci & Technol, Sch Comp Sci & Technol, Cluster & Grid Comp Lab, Serv Comp Technol & 更多
会议名称：24th International Conference on Database Systems for Advanced Applications (DASFAA)
会议日期：APR 22-25, 2019
来源：DATABASE SYSTEMS FOR ADVANCED APPLICATIONS (DASFAA 2019), PT I
摘要：Maximal 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 MCEdegeneracy 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 BKpivot 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 BKpivot 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 BKrcd, to improve the efficiency of MCE in a dense degeneracy neighborhood by recursively conducting core decomposition in it. Contrary to BKpivot, BKrcd 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 BKrcd into MCEdegeneracy to form a hybrid approach named as MCEdegeneracyhybrid, that chooses BKrcd or BKpivot adaptively according to the structural properties of the degeneracy neighborhoods. Experimental results conducted in real-world graphs show that MCEdegeneracyhybrid achieves high overall performance improvements on the graphs. For example, MCEdegeneracyhybrid achieves 1.34x to 2.97x speedups over MCEdegeneracy in web graphs taken in our experiments.