On fast enumeration of maximal cliques in large graphs. (January 2022)

• Record Type: Journal Article
• Authors: Jin, Yan; Xiong, Bowen; He, Kun; Zhou, Yangming; Zhou, Yi
• Is Part Of: Expert systems with applications. Volume 187(2022)
• Publication Date: 2022-01
• Subjects: Maximal clique enumeration -- Exact algorithm -- NP-hard -- Bron–Kerbosch algorithm -- Social network; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2021.115915
• Languages: English
• ISSNs: 0957-4174

Abstract

Abstract: 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. Highlights: Enumerating maximal cliques in large graphs is computationally challenging. An exact method on fast maximal clique enumeration is presented. We introduce a new dynamic branching heuristic based on the degeneracy order. The method is highly competitive with the current leading methods. The method is efficient for solving the real-world social network benchmarks.