Найти все несуществующие связи в графе - PullRequest
Новая
       63

Найти все несуществующие связи в графе

4 голосов
/ 13 апреля 2020

У меня есть pandas фрейм данных Края с двумя столбцами Узел 1 | Узел 2 

      Node1     Node2
 0      A         B
 1      C         B
 2      C         D

Они в основном показывают края (A, B) | (C, Б) | (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 заполняет оперативную память и вылетает ноутбук. Я пытаюсь выяснить, возможно ли с помощью pandas Dataframe, что я могу получить недостающие края графа или вы можете сказать, что мне нужно найти COMPLEMENT графа.

1 Ответ

4 голосов
/ 13 апреля 2020

Один из возможных подходов может быть следующим:

  • Найти все длины 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)
...