是否有一种有效的方法可以使用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/