找出图中所有不存在的连接

Question

我有一个pandas数据帧边，有两列节点1|节点2

Node1     Node2
0      A         B
1      C         B
2      C         D

这些基本上显示了图中的边

我需要找出的是缺少边，即不存在(A，D(|(B，D(|

所需输出

Node1     Node2
0      A         D
1      A         C
2      B         D

我尝试过的：

我将DataFrame转换为networkx图，然后使用nx.non_edges函数实现相同的目的(查找缺失的边(但由于硬件资源不足，networkx占用了RAM，笔记本电脑崩溃。我试图通过pandas Dataframe找到是否有可能得到图的缺失边，或者你可以说我需要找到图的COMPLEMENT。

Answer 1

一种可能的方法如下：

• 查找节点的所有长度2组合
• 在他们身上反复
• 保留G.edges中未包含的组合

---

from itertools import combinations
G = nx.from_pandas_edgelist(df, source='Node1', target='Node2')
edge_non_present = []
edges = set(G.edges())
for possible_edge in combinations(G.nodes(), r=2):
if possible_edge not in edges:
edge_non_present.append(possible_edge)
print(edge_non_present)
# [('A', 'C'), ('A', 'D'), ('B', 'D')]

---

更新

如果这导致了大量的组合，由于节点数量很大，那么从返回的生成器中抽取一部分，只迭代其中的一个子集：

from itertools import islice
G = nx.from_pandas_edgelist(df, source='Node1', target='Node2')
n_comb = 100
edge_non_present = []
edges = set(G.edges())
for possible_edge in islice(combinations(G.nodes(), r=2), 0, n_comb):
if possible_edge not in edges:
edge_non_present.append(possible_edge)