问有效的图聚类算法

EN

我个人建议马尔可夫聚类。我在过去几次使用它，取得了很好的效果。

亲和力传播是另一个可行的选择，但它似乎不如马尔可夫聚类一致。

还有各种其他选项，但这两个选项都是现成的，并且非常适合于具体的聚类图问题(您可以将其看作稀疏矩阵)。您正在使用的距离度量也是一个考虑因素。如果你使用适当的度量标准，你的生活会更容易。

我在寻找性能基准时发现了本论文，这是一个很好的主题调查。

层次聚类

这是一个朋友推荐给我的。根据维基百科的说法：

在该方法中，定义了一个量化节点对之间某些(通常是拓扑)相似性类型的相似性度量。常用的度量包括邻接矩阵的余弦相似度、Jaccard指数和行间Hamming距离。然后，根据这一度量，将相似节点分组为社区。有几种常见的分组方案，其中最简单的两种是单连锁聚类，其中两组被认为是独立的群落当且仅当不同组中所有对节点的相似性低于给定的阈值，以及完全连锁聚类，其中每个组内的所有节点的相似性都大于阈值。

马尔可夫聚类

这就是我在你的情况下所用的。这是一个非常有用的算法。我找到了一个关于算法的链接到一个不错的PDF。这是一个伟大的算法，而且，由于缺乏一个更好的术语，非常“强大”。试试看。

对于这里的问题，我认为您应该想一种方法，将顶点-边映射到每个顶点的一组坐标。我不知道是否有更好的办法来做到这一点。但是，我认为您可以首先将每个顶点表示为一个维度，然后，某个顶点的边值将成为您需要为该维度处理的值。在此之后，您可以做一个简单的欧几里得距离，并使用它。