DynaMap: A Map Equation-based Parallel Algorithm for Detecting Communities on Dynamic Graphs

• Gabriel G. Santos PUCRS
• Kartik Lakhotia Intel Labs
• César A. F. De Rose PUCRS

Resumo

Community detection is a common graph workload used in various domains. With the rapid increase in volumes of data, a lot of research has been done on accelerating different community detection algorithms through parallelization. However, the vast majority of such works focus on static graph structures. In recent years, dynamic graphs have been gaining a lot of attention, since various applications require the ability to change their data and execute new analytics. Most of the work on dynamic community detection has been done on sequential modularity-based approaches. In this paper, we present a Map Equation-based approach to dynamic community detection. The Map Equation is used by the Infomap algorithm and achieves better community structures on static graphs compared to modularity. We design our approach to be easy to parallelize, increasing its applicability to real-world graphs. We show that a parallel implementation of our approach can be faster than modularity-based implementations and as fast as parallel naive ones, with a minimal impact on accuracy, providing a positive impact in the efficiency and efficacy of dynamic graph workflows.

Palavras-chave: Accuracy, Heuristic algorithms, High performance computing, Memory management, Load management, Parallel algorithms, Detection algorithms, community detection, dynamic graphs, graph algorithms, parallel algorithms