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

Question

我有一个名为Edges的pandas数据框，它有两列，分别是Node 1和Node 2

      Node1     Node2
 0      A         B
 1      C         B
 2      C         D

这些基本上显示了图中的边缘(A,B) | (C,B) | (C,D)

我需要找出缺失的边缘，即不存在的(A,D) | (B,D) | (A,C)

期望输出

      Node1     Node2
 0      A         D
 1      A         C
 2      B         D

我的尝试：

我将DataFrame转换为networkx图，然后使用nx.non_edges函数来实现相同的目的（查找缺失的边），但由于硬件资源不足，networkx会填满RAM并导致笔记本崩溃。 我正在尝试找出是否可以通过pandas DataFrame获取图的缺失边，或者说我需要找到图的补集。

- Malik Hanzala

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)

- yatu

---

我也尝试过使用itertools，但笔记本仍然崩溃。 有没有办法只保存一些边缘并留下其他缺失的边缘，以便笔记本不会崩溃。 - Malik Hanzala

谢谢！这个有效 :) 我之前不知道 "isslice"，但这帮了我很多。 - Malik Hanzala