python - 图聚类算法

Question

我可以解释我正在寻找的内容的最好方法是使用这张图片:

显然，视觉辅助使我们更容易对这些图进行分组，但我也认为找到密集的子图应该是使用算法可以解决的问题。由于 MCL 算法很受欢迎，我尝试了它，但它无法正常工作，因为它至少看起来不允许有方向的边缘。我尝试以不同的方式对边缘进行加权，但这也无助于聚类过程。我想在图中找到密集点，并且我确实有一种方法来验证给定的集群是否可行，如果有帮助的话，在某些情况下某些元素无法组合在一起。

其输出将是:

集群 0:A、B、C

集群 1:D、E、F、G

在这种情况下，如果 D 是可疑元素，则使用不同的方法我可以找出属于哪个簇。

Answer 1

这个问题本身就是一个研究领域(也是我博士论文的一部分......) 最佳解决方案通常取决于您对“集群”或“社区”的数学定义。 例如，您可以最小化簇间边的数量，称为 graph partition problem 。

Fortunato 就这个主题写了一篇很好的评论论文: https://arxiv.org/pdf/0906.0612

除了我们自己的方法之外，我个人最喜欢的是模拟退火。