自适应切割：基于多层次树状图分割的层次聚类与社区检测新方法

《PNAS Nexus》：Adaptive cut reveals multiscale complexity in networks

　　

摘要

层次聚类和社区检测是机器学习和复杂网络分析中的重要问题。识别簇的一种常见方法是简单地根据某个阈值对树状图进行切割。然而，单层次切割在捕获数据潜在结构方面往往不是最优的，尤其是当树状图不平衡时。本文提出了自适应切割（adaptive cut），一种利用树状图的层次结构通过多层次切割来克服单层次方法局限性的方法。自适应切割使用马尔可夫链蒙特卡洛结合模拟退火来优化目标函数，从而获得更好的划分结果。我们通过链接聚类和模块化优化来展示自适应切割的应用，但指出该方法适用于任何依赖于树状图和目标函数的聚类任务。除了自适应切割之外，我们还引入了平衡度分数（balancedness score），这是一种信息论指标，用于量化树状图的平衡程度。平衡度可以预测使用多层次切割的潜在收益。在社区检测示例中，我们在超过200个真实世界网络和多个合成数据集上评估了该方法，证明了相比传统单切割方法，在划分密度和模块化方面均有改进。我们还通过在不同层次聚类技术和目标函数上应用自适应切割，展示了其通用性。自适应切割在广泛的层次聚类任务中改善了聚类结果。