标题: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
出版年:2019
卷:11446
页码:641-658
DOI:10.1007/978-3-030-18576-3_38
摘要: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.
收录类别:CPCI-S;EI
资源类型:会议论文
TOP