文献类型：期刊文献

英文题名：On fast enumeration of maximal cliques in large graphs

作者：Jin, Yan[1];Xiong, Bowen[1];He, Kun[1];Zhou, Yangming[2];Zhou, Yi[3]

机构：[1]Huazhong Univ Sci & Technol, Sch Comp Sci & Technol, Wuhan, Peoples R China;[2]East China Univ Sci & Technol, Sch Informat Sci & Engn, Shanghai, Peoples R China;[3]Univ Elect Sci & Technol China, Sch Comp Sci & Engn, Chengdu, Peoples R China

年份：2022

卷号：187

外文期刊名：EXPERT SYSTEMS WITH APPLICATIONS

收录：;EI(收录号：20214211023984);WOS:【SCI-EXPANDED(收录号:WOS:000709912500002)】；

语种：英文

外文关键词：Maximal clique enumeration; Exact algorithm; NP-hard; Bron-Kerbosch algorithm; Social network

摘要：Maximal Clique Enumeration (MCE) is a fundamental and challenging problem in graph theory and various network applications. Numerous algorithms have been proposed in the past decades, however, only a few of them focus on improving the practical efficiency in large graphs. To this end, we propose an efficient algorithm called FACEN based on the Bron-Kerbosch framework. To optimize the memory and time consumption, we apply a hybrid data structure with adjacency list and partial adjacency matrix, and introduce a dynamic pivot selection rule based on the degeneracy order. FACEN is evaluated on a total of 64 benchmark instances from various sources. Computational results indicate that the proposed algorithm is highly competitive with the current leading MCE methods. In particular, our algorithm is able to enumerate all maximal cliques on the tested real-world social networks with millions of vertices and edges. For very large graphs, we provide an additional experiment for solving the MCE variant with lower bound, and investigate the benefits of FACEN.