The goal of the project is to implement for graphs modeling social networks
enumerating algorithms for communities (i.e. sets of densely connected vertices).
connected vertices). This kind of algorithm has many practical applications, for example for
advertising targeting. For this project, we will use the approach proposed in the scientific paper .
In particular, let a graph G = (V, E) with V the set of vertices and E the set of edges
of G. We represent a community by a clique. A clique of G is a set K of
vertices of the graph all connected two by two. The clique K is maximal if there is no
vertex in V ∖ K connected to all the vertices of K. The problem we consider is
to enumerate all maximal cliques in a graph. In a first step, you will implement
the two sequential algorithms presented in . These algorithms are parameterized by the
degeneracy of the input graph, which you will have to compute. You will use the
Bron-Kerbosch algorithm as an enumeration subroutine. In a second step, you will try to
parallelize these algorithms. In all the steps of the project you will wait until the algorithms
algorithms are presented theoretically, then compared on different instances in terms of time and
Hello I was working with such tasks before, but I can help only with C/C++ implementations using MPI/OpenMP (or hybrid). Thus If you need Python implementation, just ignore my bid. Regards