论文标题
评估逐步发展图的社区检测算法
Evaluating Community Detection Algorithms for Progressively Evolving Graphs
论文作者
论文摘要
在过去的十年中，已经提出了许多算法，以发现动态社区。但是，这些方法很少在他们之间进行比较。在本文中，我们提出了一个动态图的生成器，具有种植的社区结构，作为比较和评估此类算法的基准。与以前建议的基准不同，它可以通过描述性语言指定任何所需的社区结构，然后生成相应的逐步发展的网络。我们从经验上评估了六种现有的算法，以与种植的地面真理，动态分区的平稳性和可扩展性的瞬时和纵向相似性来进行动态社区检测。我们明显观察到不同类型的弱点，具体取决于它们的方法，以确保光滑度，即故障，过度简化和身份损失。尽管没有作为明显的赢家出现的方法，但我们观察到方法之间存在明显的差异，并且我们确定了最快的，那些在每个步骤中产生最平滑或最准确的解决方案的方法。
Many algorithms have been proposed in the last ten years for the discovery of dynamic communities. However, these methods are seldom compared between themselves. In this article, we propose a generator of dynamic graphs with planted evolving community structure, as a benchmark to compare and evaluate such algorithms. Unlike previously proposed benchmarks, it is able to specify any desired evolving community structure through a descriptive language, and then to generate the corresponding progressively evolving network. We empirically evaluate six existing algorithms for dynamic community detection in terms of instantaneous and longitudinal similarity with the planted ground truth, smoothness of dynamic partitions, and scalability. We notably observe different types of weaknesses depending on their approach to ensure smoothness, namely Glitches, Oversimplification and Identity loss. Although no method arises as a clear winner, we observe clear differences between methods, and we identified the fastest, those yielding the most smoothed or the most accurate solutions at each step.
