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

extract clusters / sets of nodes from an undirected graph

描述

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

此处的集群的特征是一组节点全部通过（非定向）边互连。出于简化的原因，所有边的权重都可以认为是权重 = 1。此外，节点或边中都没有存储更多信息。

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

图表方案

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

预期集群结果

集群大小应动态识别并始终考虑互连节点的最大数量（例如，n1 和 n2 不被视为自己的集群，因为 n3 与它们都有连接）。

方法

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

图形为矩阵

但我未能找到一个优雅的解决方案，该解决方案未包含使用嵌套循环遍历索引的不可扩展方法。

有没有人知道如何解决这个问题，或者甚至使用我可以定位的可共享解决方案来优化这个问题？非常感谢！！

您的集群的正确命名是 complete subgraph. Your problem is known as clique problem。 Python 最好的图形处理库之一 - networkx - 有几种算法可以解决这个问题： networkx cliques

您应该将图形转换为 networkx 格式并使用这些算法来查找它。