python - 查找给定图的所有完整子图的有效方法(Python)？

有没有一种有效的方法来使用networkx查找给定（无向）图的所有完全连接的组件（即完整的子图）？例如，我有以下邻接矩阵（无自循环）：

    |0 1 1 0 0|
    |1 0 1 0 0|
G = |1 1 0 1 0|
    |0 0 1 0 1|
    |0 0 0 1 0|

对应于下图
该代码应返回以下节点元组：

(0,1), (1,2), (0,2), (3,4), (2,3), (0,1,2)

我知道networkx有用于查找周期，强连接的组件等的例程，但是我找不到关于全连接的组件的任何信息。如果使用networkx无法实现，那么使用Numpy + Scipy也可以。提前谢谢了！

编辑

这是我所做的：

import networkx as nx
import itertools


def findsubsets(S, m):
    return set(itertools.combinations(S, m))



A = np.array([[0, 1, 1, 0, 0],
              [1, 0, 1, 0, 0],
              [1, 1, 0, 1, 0],
              [0, 0, 1, 0, 1],
              [0, 0, 0, 1, 0]])


G = nx.from_numpy_matrix(A)

M = np.sqrt(np.size(A))


for m in range(2, M+1):

    for a in findsubsets(range(0, M), m):

        if(nx.number_of_edges(G.subgraph(a)) == (m**2 - m)/2.):

            print nx.nodes(G.subgraph(a))

它基本上找到给定一个的所有可能的mXm个子图，然后检查它们是否具有最大（即（m ** 2-m）/ 2）个连接。但是我想知道是否存在更有效的方法，因为对于大型图形，函数itertools.combinations的性能不是很好。

最佳答案

好的，我找到了。只是list(nx.find_cliques(G))，只是因为我不知道在图论中，集团是完全连接的子图。

编辑

更准确地说，list(nx.find_cliques(G))找到最大的集团，因此这不是我所需要的。我在this link上找到了类似的帖子。

因此正确的答案是使用list(nx.enumerate_all_cliques(G))。但是，此函数还会返回大小为1的小集团，我不喜欢它，因为我的图形中没有自循环。因此，最终的解决方案是使用以下代码行：

[s for s in nx.enumerate_all_cliques(G) if len(s) > 1]

关于python - 查找给定图的所有完整子图的有效方法(Python)？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/40284774/