基于曲率的图聚类算法研究

摘要

无监督节点聚类（或社区检测）是经典的图学习任务。本文研究利用图几何特征识别密集连接子结构的算法，这些子结构形成聚类或社区。该方法通过离散Ricci曲率及其关联的几何流实现，在曲率流作用下图的边权重演化以揭示其社区结构。研究分析了多种离散曲率概念的实用性，与现有文献不同，不仅研究每个节点仅属于单一社区的单成员社区检测，还研究社区可能重叠的混合成员社区检测。对于后者，提出在线图（即原图的对偶图）上执行社区检测的优势。通过理论和实验证据验证基于曲率的聚类算法有效性，并给出原图与对偶图曲率关系的若干结论，这些结论支持混合成员社区检测方法的高效实现，对基于曲率的网络分析具有独立价值。