论文标题
归一化模块和关联聚类的常数近似
Constant Approximation for Normalized Modularity and Associations Clustering
论文作者
论文摘要
我们研究了在广泛的目标下图形聚类的问题，在这些目标中，群集的质量是根据群集中边缘数与群集中顶点的总重量之间定义的。我们表明，我们的定义与流行的聚类措施密切相关，即标准化关联，这是归一化剪切目标的双重和归一化模块。我们为我们的目标提供了线性的时间恒定算法，这意味着针对归一化模块化和归一化关联的第一个恒定因子近似算法。
We study the problem of graph clustering under a broad class of objectives in which the quality of a cluster is defined based on the ratio between the number of edges in the cluster, and the total weight of vertices in the cluster. We show that our definition is closely related to popular clustering measures, namely normalized associations, which is a dual of the normalized cut objective, and normalized modularity. We give a linear time constant-approximate algorithm for our objective, which implies the first constant-factor approximation algorithms for normalized modularity and normalized associations.
