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.
