时间戳

首页 > 解决方案 > 查找图中所有不存在的连接

python - 查找图中所有不存在的连接

问题描述

我有一个带有两列节点 1 | 的熊猫数据框边缘 节点 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 找到我可能会丢失图的边缘，或者你可以说我需要找到图的补充。

标签： pythonpandasnetworkxgraph-theory

解决方案

一种可能的方法如下：

  • 查找节点的所有长度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)

推荐阅读