A Starting Point for Dynamic Community Detection with Leiden Algorithm

这篇技术报告探讨了许多真实世界的图随着时间的推移而演变的情况。在这些图上识别社区或集群是一个重要的问题。我们将三种动态方法，即Naive-dynamic (ND)、Delta-screening (DS)和Dynamic Frontier (DF)，扩展到我们的Leiden算法多核实现中，这个算法因其高质量的社区检测而闻名。我们在一台64核AMD EPYC-7742处理器的服务器上进行了实验，结果显示，相对于静态、ND和DS Leiden算法，ND、DS和DF Leiden算法在随机批量更新的大型图上分别实现了1.25倍、1.24倍和1.37倍的加速。然而，在真实世界的动态图上，ND Leiden算法表现最佳，平均比Static Leiden算法快1.14倍。我们希望我们的初步结果可以作为动态方法在演变图上应用Leiden算法的起点。

本论文试图解决动态图上社区检测的问题，探索了三种动态方法：Naive-dynamic (ND), Delta-screening (DS), and Dynamic Frontier (DF)，并将它们应用于Leiden算法的多核实现中。

论文中的关键思路是将动态方法应用于Leiden算法，提高动态图上社区检测的效率。相比于当前领域的研究，这篇论文提出了一种新的思路。

论文在64核AMD EPYC-7742处理器上进行了实验，证明了ND、DS和DF Leiden相对于Static、ND和DS Leiden在随机批量更新的大型图上分别实现了1.25x、1.24x和1.37x的加速。然而，在真实的动态图上，ND Leiden的表现最佳，平均比Static Leiden快1.14x。值得关注的是，论文提供了开源代码，并且探讨了未来研究的方向。

近期在这个领域中，还有一些相关的研究，如《Dynamic Community Detection in Evolving Social Networks》、《Community Detection in Dynamic Social Networks: A Survey》等。