问从无向图中提取节点的集群/集合

EN

描述

我想从一个无向图数据集中以节点组的形式识别和获得n大小的集群(最好是在Python中)。目前，我被困在一个远离我的舒适区和知识区的领域里，所以我想可能值得尝试一下，在这里接触感兴趣的人。

在这里，集群的特征是一组节点都通过(非定向)边缘互连。为了简化起见，所有的边权重都可以考虑为权重= 1。此外，节点或边中也没有存储进一步的信息。

下图说明了数据结构和依赖关系

图模式

​

​

为此，我正在努力寻找一种解决方案，它可以自动检测完全互连的节点集，如下所示：

预期的集群结果

​

​

其中群集大小应动态识别，并始终考虑互连节点的最大数量(例如，n1和n2不被视为自己的群集，因为n3与这两个节点都有连接)。

接近

我尝试通过强连接组件的概念来解决这个问题，但它似乎没有提供所需的输出，因为所有节点之间的连接不是有方向性的。我也尝试过用矩阵的形式来解决这个问题，如下所示：

图为矩阵

​

​

但我在一个优雅的解决方案中失败了，该解决方案没有结合使用循环迭代索引的不可伸缩方法。

有没有人有关于如何实现这一点的想法，或者甚至是用一个我可以定向的共享解决方案来进行优化呢？非常感谢！