描述
我想从一个无向图数据集中以节点组的形式识别和获得n大小的集群(最好是在Python中)。目前,我被困在一个远离我的舒适区和知识区的领域里,所以我想可能值得尝试一下,在这里接触感兴趣的人。
在这里,集群的特征是一组节点都通过(非定向)边缘互连。为了简化起见,所有的边权重都可以考虑为权重= 1。此外,节点或边中也没有存储进一步的信息。
下图说明了数据结构和依赖关系
图模式
为此,我正在努力寻找一种解决方案,它可以自动检测完全互连的节点集,如下所示:
预期的集群结果
其中群集大小应动态识别,并始终考虑互连节点的最大数量(例如,n1和n2不被视为自己的群集,因为n3与这两个节点都有连接)。
接近
我尝试通过强连接组件的概念来解决这个问题,但它似乎没有提供所需的输出,因为所有节点之间的连接不是有方向性的。我也尝试过用矩阵的形式来解决这个问题,如下所示:
图为矩阵
但我在一个优雅的解决方案中失败了,该解决方案没有结合使用循环迭代索引的不可伸缩方法。
有没有人有关于如何实现这一点的想法,或者甚至是用一个我可以定向的共享解决方案来进行优化呢?非常感谢!
发布于 2019-03-20 20:47:52
您的群集的正确名称是complete subgraph。您的问题称为clique problem。Python最好的图形处理库之一- networkx -有几种算法可以解决这个问题:networkx cliques
你的问题可以通过这个函数来解决:networkx.algorithms.clique.enumerate_all_cliques
您应该将图形转换为networkx格式,并使用这些算法来查找它。
https://stackoverflow.com/questions/55258926
复制相似问题