Properties and Performance of the ABCDe Random Graph Model with Community Structure

In this paper, we investigate properties and performance of synthetic random graph models with a built-in community structure. Such models are important for evaluating and tuning community detection algorithms that are unsupervised by nature. We propose ABCDe-a multi-threaded implementation of the ABCD (Artificial Benchmark for Community Detection) graph generator. We discuss the implementation details of the algorithm and compare it with both the previously available sequential version of the ABCD model and with the parallel implementation of the standard and extensively used LFR (Lancichinetti- Fortunato-Radicchi) generator. We show that ABCDe is more than ten times faster and scales better than the parallel implementation of LFR provided in NetworKit. Moreover, the algorithm is not only faster but random graphs generated by ABCD have similar properties to the ones generated by the original LFR algorithm, while the parallelized NetworKit implementation of LFR produces graphs that have noticeably different characteristics. Crown Copyright (C) 2022 Published by Elsevier Inc.

Automated summary

This paper investigates the properties and performance of synthetic random graph models with a built-in community structure, and proposes a multi-threaded graph generator ABCDe. The ABCDe generator is more efficient and scalable than the previously available sequential version and the parallel implementation of LFR. The generated random graphs by ABCD have similar properties to the ones generated by the original LFR algorithm.