machine-learning - DBSCAN 的距离函数

Question

我想使用聚类算法来找到大有向图的聚类，并且我也想从该图中消除噪声。因此，我正在考虑使用DBSCAN方法，因为我发现我们可以为算法提供一个距离函数来确定两个不同节点之间的距离/相似度。

我的问题是，如何定义一个距离函数，该距离函数可以增加两个节点之间的相似度(以跳数为单位)，并在节点被隔离时减少。

我没有坐标或节点属性，因此无法使用它们。我只有图的拓扑。

预期的输出将是这样的:

我真的很担心解决方案的复杂性。如何以线性复杂度近似聚类...

Answer 1

显而易见的事情有什么问题吗？

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

您可能应该考虑方向，因此 a0 到 a3 就是 1。