Engineering a Parallel and Distributed Semi-synchronous Community Finding Algorithm

Community-finding in graphs is the process of identifying highly cohesive vertex subsets. Many community-finding algorithms are based on the optimisation of an objective through a process of iterative local update (ILU), in which vertices are successively moved to the community of one of their neighbours in order to achieve the highest local gain in the quality of the objective. Among these algorithms, the label propagation algorithm is the most basic, although ILU has proven one of the most effective strategies for optimising community objectives such as modularity and the map equation. In this paper, we study the parallelisation of ILU algorithms. We engineer the semi-sychronous approach recently proposed for label propagation and demonstrate its extension to other objectives. We show that it provides an effective compromise between the level of synchronisation required to maintain a consistent state during the optimisation and the amount of mixing required to converge in a small number of iterations. We engineer this approach for shared-memory multicore and distributed platforms by a careful choice of design parameters and perform an empirical study on a range of graphs and architectural platforms.