是否有一种根据Jaccard相似性对图表进行聚类的有效方法？

Question

有没有一种有效的方法来使用Jaccard相似性来集群图中的节点,使得每个集群至少具有K节点？

节点之间的Jaccard相似i和j:
我们S是集合的邻居i和T是集合邻居j.然后之间的相似性i和j由下式给出 |(S ? T)| / |(S ? T)|.

Answer 1

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

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

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

当 A 和 B 尚未位于同一个集群中，并且任一集群的成员数少于 k 时，加入这两个集群。重复此操作，直到处理完所有相似之处。

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

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