algorithm - 有没有一种根据 Jaccard 相似度对图进行聚类的有效方法？

Question

是否有一种有效的方法可以使用 Jaccard 相似度对图中的节点进行聚类，使得每个聚类至少有 K 个节点？

节点i和j之间的Jaccard相似度:
令S为i的邻居集code> 和 T 是 j 的邻居集。然后 i 和 j 之间的相似度由 |(S ⋂ T)| 给出/|(S ⋃ T)|.

Answer 1

您是否尝试过自己实现一些算法？

计算所有成对的非零相似性(即，当它们至少有一个共同的邻居时；这使得候选集比平方矩阵小得多)。

按相似度对它们进行排序，并按相似度递减的顺序处理对。最初，每个对象都是它们自己的集群。

当 A 和 B 还不在同一个集群中，并且任一集群的成员少于 k 时，加入这两个集群。重复直到处理完所有相似点。

请注意，您最终可能仍然拥有少于 k 个成员的集群。例如，如果你的数据集总共有不到 k 个节点，或者有没有连接的小子图等。

您确实应该接受少于 k 个节点的集群，即非集群节点。为什么一切都会聚集？真实数据中总会存在异常值和噪声。