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])

我能想到写这个有点费力的方法，但想知道是否有一个简单的内置函数。

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() returns 一个生成器，它将生成图中的所有派系。您可以使用列表理解过滤掉少于三个节点的派系：

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

networkx 中更大图的完全连接子图

completely connected subgraphs from a larger graph in networkx

python

nodes

networkx

subgraph