Cache Efficient Louvain with Local RCM
Sanaz Gheibi, Tania Banerjee, Sanjay Ranka, Sartaj K. Sahni · 2020
We develop a cache efficient Louvain community detection algorithm. Its effectiveness is demonstrated by bench-marking it against four existing Louvain algorithms on the Intel Knights Landing (KNL) and Haswell computational platforms using real and synthetic datasets. For a single iteration of Louvain, our algorithm obtains a speedup of up to 76.18% on real datasets on KNL, 51.91% on real networks on Haswell, 71.31% on synthetic networks on KNL, and 59.13% on synthetic networks on Haswell. These percentages using 2 iterations are 62.91%, 43.27%, 67.61%, and 54.43%, respectively.