论文标题
具有社区结构的ABCDE随机图模型的属性和性能
Properties and Performance of the ABCDe Random Graph Model with Community Structure
论文作者
论文摘要
在本文中，我们研究了具有内置社区结构的合成随机图模型的属性和性能。这样的模型对于评估和调整自然界无监督的社区检测算法很重要。我们提出了ABCDE，这是ABCD的多线程实现（社区检测的人工基准）图生成器。我们讨论了该算法的实现详细信息，并将其与ABCD模型的先前可用顺序版本以及标准和广泛使用的LFR（Lancichinetti-Fortunato-Radicchi）发电机进行了比较。我们证明，ABCDE的速度比NetworkIT中提供的LFR的并行实现要快十倍，并且比例比缩放得更好。此外，该算法不仅更快，而且ABCD生成的随机图具有与原始LFR算法生成的属性相似的属性，而LFR的并行网络实现产生了具有明显不同特征的图形。
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.
