useR! 2024

Community detection in graphs has numerous applications from social networks to biology. However, the immense size of modern graphs makes it challenging to accurately detect communities. We set out to benchmark a variety of popular methods available in R to measure their accuracy and time complexity on synthetic and real datasets. Unsurprisingly, we found that less scalable algorithms tend to outperform more computationally efficient ones. To address this issue, we introduce two new variants of the Fast Label Propagation algorithm for clustering extremely large networks, both available in the SynExtend package for R. Our implementations offer accuracy comparable to less scalable approaches while providing linear-time computational scalability. Furthermore, we made it possible to apply our community detection algorithms outside of main memory, which permits community detection on graphs with billions of nodes using less than a gigabyte of RAM. These advances will help democratize scalable analyses by removing the need for expensive supercomputer resources. Together, this work both improves graph community detection and makes these analyses more accessible to researchers.