Properties and Performance of the ABCDe Random Graph Model with Community Structure
This work provides a faster and scalable tool for researchers and practitioners in network science to generate benchmark graphs, though it is incremental as it builds on existing ABCD and LFR models.
The paper tackles the need for efficient synthetic graph generation with community structure for evaluating community detection algorithms, proposing ABCDe, a multi-threaded implementation that is over ten times faster and scales better than a parallel LFR implementation while maintaining similar graph properties.
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.