Title: A parallel implementation of the Synchronised Louvain method,
Abstract: Community detection in networks is a very actual and important field of
research with applications in many areas. But, given that the amount of
processed data increases more and more, existing algorithms need to be adapted
for very large graphs. The objective of this project was to parallelise the
Synchronised Louvain Method, a community detection algorithm developed by
Arnaud Browet, in order to improve its performances in terms of computation
time and thus be able to faster detect communities in very large graphs. To
reach this goal, we used the API OpenMP to parallelise the algorithm and then
carried out performance tests. We studied the computation time and speedup of
the parallelised algorithm and were able to bring out some qualitative trends.
We obtained a great speedup, compared with the theoretical prediction of Amdahl
law. To conclude, using the parallel implementation of the algorithm of Browet
on large graphs seems to give good results, both in terms of computation time
and speedup. Further tests should be carried out in order to obtain more
quantitative results.