在NetworkX中从一个大图中找出完全连通的子图

Question

我一直尽力不在这里重新发布，但我认为我的请求非常简单，我只是对网络图表不熟悉。在使用Python中的networkx模块时，我想从连接的图中恢复所有节点互相连接（节点数大于2）的子图。有没有简单的方法来做到这一点？

以下是我的例子：

一个具有七个节点的简单图。节点1、2、3是共享连接，节点1、2、4也是共享连接，节点5、6、7同样如此。

import networkx as nx
G=nx.Graph() #Make the graph
G.add_nodes_from([1,2,3,4,5,6,7]) #Add nodes, although redundant because of the line below
G.add_edges_from([(1,2),(1,3),(2,3),(1,4),(2,4),(1,5),(5,6),(5,7),(6,7)]) # Adding the edges

我期望的输出是：([1,2,3],[1,2,4],[5,6,7])。

我可以想到一些比较繁琐的方法来实现这个目标，但是想知道是否有一个内置函数可以简化这个过程。

- user2096176

Answer 1

看起来您想在图中发现团伙。为此，您可以使用 nx.clique.find_cliques():

>>> list(nx.clique.find_cliques(G))
[[1, 2, 3], [1, 2, 4], [1, 5], [6, 5, 7]]

nx.clique.find_cliques()返回一个生成器，可以产生图中所有的团。您可以使用列表推导式来过滤掉节点数少于三个的团：

>>> [g for g in nx.clique.find_cliques(G) if len(g) > 2]
[[1, 2, 3], [1, 2, 4], [6, 5, 7]]

- Alex Riley