我想使用聚类算法对一个大型有向图进行聚类，并且希望从这个图中去除噪声。因此，我考虑使用DBSCAN方法，因为我了解到我们可以给算法提供一个距离函数来确定两个不同节点之间的距离/相似度。

我的问题是，如何定义一个距离函数，使得在跳数上接近的两个节点之间的相似度增加，而当一个节点孤立时相似度减少。

我没有坐标或节点属性，所以无法使用这些信息。我只有图的拓扑结构。

预期的输出结果大致如下：

我非常关心解决方案的复杂度。如何以线性复杂度近似聚类…

回答：

明显的做法有什么问题？

Distance(a,b) = 最短路径的长度，如果没有路径则为无穷大。

你可能应该考虑方向性，所以从a0到a3是1。