DF Louvain: Fast Incrementally Expanding Approach for Community Detection on Dynamic Graphs

社区检测是识别网络中自然分割的问题。该问题的一个相关挑战是在快速演化的图中找到社区。在本报告中，我们提出了并行动态边界（DF）Louvain算法，该算法在给定一批边删除和插入更新时，增量地识别和处理图中受影响的近似顶点集，同时使用一种新的方法增量更新顶点的加权度和社区的总边权。我们还展示了Naive-dynamic（ND）和Delta-screening（DS）Louvain的并行实现。在一个64核的AMD EPYC-7742处理器的服务器上，我们的实验表明，在真实世界的动态图上，DF Louvain相对于静态、ND和DS Louvain分别获得了179倍、7.2倍和5.3倍的加速，并且在具有随机批量更新的大图上，相对于静态、ND和DS Louvain分别快了183倍、13.8倍和8.7倍。此外，DF Louvain每翻倍线程数量就提高1.6倍的性能。

本论文旨在解决在动态图中识别社区的问题，特别是在快速变化的图中找到社区的挑战。论文提出了一种基于Parallel Dynamic Frontier (DF) Louvain算法的解决方案，该算法可以在最小的开销下增量识别和处理图中受影响的顶点集合，并使用增量更新顶点的加权度和社区的总边权重的新方法。

DF Louvain算法的关键思路在于增量更新顶点的加权度和社区的总边权重，从而实现对动态图的高效处理，相比当前领域的研究，具有更高的速度和性能。

论文通过实验验证了DF Louvain算法的性能，结果表明在真实世界的动态图中，相比Static、ND和DS Louvain，DF Louvain可以分别获得179x、7.2x和5.3x的加速，并且在具有随机批量更新的大型图上，DF Louvain分别比它们快183x、13.8x和8.7x。此外，DF Louvain每加倍线程可以提高1.6倍的性能。

在相关研究方面，最近的一些研究包括《A survey of community detection in dynamic networks》、《Dynamic community detection algorithms: A survey》等。