Title
Listing all maximal cliques in large graphs on vertex-centric model
Abstract
Maximal Clique Enumeration (MCE), which consists to enumerate all maximal complete subgraphs in a given graph, is a fundamental problem in graph theory, and it is used in several applications. It is one of Karp’s 21 NP-complete problems. In the literature, this problem has been widely studied. One of the most notable, efficient, successful and extensively used solutions is the Bron–Kerbosch (BK) algorithm. The latter is a sequential algorithm which is able to enumerate all maximal cliques in an undirected graph without duplication. Furthermore, it is used to solve large problems such as maximum clique problem, community detection and graph clustering. However, for large graphs, sequential algorithms are slow and do not scale well. Thus, processing efficiently this kind of graphs needs to develop distributed algorithms under parallel and distributed platforms or large graph mining frameworks. In this setting, we propose new efficient distributed algorithms for maximal clique enumerating based on the vertex-centric model. These algorithms use the BK algorithm principle to deal with the MCE problem on large cluster. The proposed algorithms are implemented in Giraph and evaluated by using real-world graphs and computer-generated benchmark networks. Our experiments on a Hadoop cluster show that the proposed algorithms can effectively process a variety of large real-world and computer-generated graphs and scale well with increasing the dataset size and the number of nodes in the cluster. Furthermore, the proposed algorithms are provably work-efficient compared with other algorithms including BK algorithm.
Year
DOI
Venue
2019
10.1007/s11227-019-02770-4
The Journal of Supercomputing
Keywords
Field
DocType
Maximal clique enumerating problem, Giraph, Pregel, Large-scale graph framework, Vertex-centric model, Bron–Kerbosch (BK)algorithm
Graph theory,Clique,Vertex (geometry),Computer science,Enumeration,Parallel computing,Theoretical computer science,Distributed algorithm,Clustering coefficient,Sequential algorithm,Clique problem
Journal
Volume
Issue
ISSN
75.0
SP8.0
1573-0484
Citations 
PageRank 
References 
0
0.34
40
Authors
4
Name
Order
Citations
PageRank
Assia Brighen110.69
Hachem Slimani212.38
Abdelmounaam Rezgui331431.39
Hamamache Kheddouci433953.61