Как выбрать два узла (пары узлов) случайным образом из графа, которые НЕ подключены, Python, networkx

Question

Я хочу извлечь два узла из графика, причем catch состоит в том, что они не должны быть подключены, т. Е. Между ними нет прямого края , Я знаю, что могу получить случайные ребра, используя «random.choice (g.edges())», но это даст мне случайные узлы, которые связаны. Я хочу, чтобы пары узлов, которые НЕ подключены (пара несвязанных ребер). помочь мне ребята ... спасибо

Answer 1

Я не знаю, что библиотеки, но я предполагаю, что вы могли бы сделать следующее:

n1 = random.choice(g.nodes()) 
    n2 = random.choice(g.nodes()) 
    while (n1 == n2 or any of the edges of n1 lead to n2): 
    n2 = random.choice(g.nodes()) 
    enjoy(yourNodes) 

Приветствия

Answer 2

просто! :)

Возьмите случайный узел - затем выберите случайный узел из списка узлов, исключая соседей и себя. Код для иллюстрации приведен ниже. :)

import networkx as nx 
from random import choice 

# Consider this graph 
# 
#  3 
#  | 
# 2 - 1 - 5 - 6 
#  | 
#  4 

g = nx.Graph() 
g.add_edge(1,2) 
g.add_edge(1,3) 
g.add_edge(1,4) 
g.add_edge(1,5) 
g.add_edge(5,6) 

first_node = choice(g.nodes())     # pick a random node 
possible_nodes = set(g.nodes()) 
neighbours = g.neighbors(first_node) + [first_node] 
possible_nodes.difference_update(neighbours) # remove the first node and all its neighbours from the candidates 
second_node = choice(list(possible_nodes))  # pick second node  

print first_node, second_node 

Answer 3

Ни одно из предложенных здесь решений не будет равномерно выбирать не-ребра (v1, v2). Рассмотрим пример граф с 4 узлами и 2 ребер:

1 —— 2 
| 
3 4 

Есть 4 не-ребер, чтобы выбрать из: (1,4), (2,3), (2,4), (3,4). Используя метод Марии или Филиппа случайного выбора первой вершины из всех четырех вершин, а затем выбирая вторую вершину из ограниченного множества вершин, чтобы не создавать никаких ребер (или самопересечений), будут давать следующие вероятности для каждого не- края должны быть выбраны:

р (1,4) = 1/4 * 1 + 1/4 * 1/3 = 8/24

р (2,3) = 1/4 * 1/2 + 1/4 * 1/2 = 6/24

p (3,4) = p (2,4) = 1/4 * 1/2 + 1/4 * 1/3 = 5/24

Таким образом, процедура не является однородной.

Это означает, что если вы хотите равномерно дискретизировать не-ребра, вам нужно будет выбрать обе вершины неограниченно и отклонить образец (обе вершины), когда они образуют существующий ребро (или равны). В NetworkX:

v1 = np.random.choice(G.nodes()) 
v2 = np.random.choice(G.nodes()) 

while G.has(edge(v1,v2)) or v1==v2: 
    v1 = np.random.choice(G.nodes()) 
    v2 = np.random.choice(G.nodes()) 

Answer 4

Если граф мал, вы можете собрать nx.non_edges() в качестве np.array и random.choice от него:

non_edges = np.array(nx.non_edges(graph)) 

sample_num = 10000 
sample = non_edges[np.random.choice(len(non_edges), sample_num, replace=False)] 

Помните, что non_edges() сама возвращает вас генератор, а не фактический список. Но если вы превращаете его в np.array, вы аккуратно собираете все предметы в генераторе. Если ваш график большой и разреженный, это может вызвать ошибку памяти, но для небольших графиков это будет самый простой способ сделать это.