cómo seleccionar dos nodos (pares de nodos) aleatoriamente de un gráfico que NO está conectado, Python, networkx

Quiero extraer dos nodos de un gráfico, el problema es que no deberían estar conectados, es decir, no existe un borde directo entre ellos. Sé que puedo obtener bordes aleatorios utilizando “random.choice (g.edges ())” pero esto me daría nodos aleatorios que están conectados. Quiero pares de nodos que NO estén conectados (un par de bordes no conectados). ayudame chicos … gracias

¡Sencillo! 🙂

Tome un nodo aleatorio: luego elija un nodo aleatorio de la lista de nodos, excluyendo a los vecinos y a sí mismo. El código para ilustrar está abajo. 🙂

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 

Ninguna de las soluciones propuestas aquí hasta ahora muestreará los no bordes (v1, v2) de manera uniforme. Considere el gráfico de ejemplo con 4 nodos y 2 aristas:

 1 —— 2 | 3 4 

Hay 4 no bordes para elegir: (1,4), (2,3), (2,4), (3,4). El uso del método de Maria o de Philip para elegir aleatoriamente el primer vértice de los 4 vértices y luego elegir el segundo vértice del conjunto restringido de vértices para no crear bordes (o auto-bucles) dará las siguientes probabilidades para cada no vértice. borde a elegir:

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

p (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

Así que el procedimiento no es uniforme.

Eso significa que si desea muestrear uniformemente los no bordes, tendrá que elegir ambos vértices sin restricciones y rechazar la muestra (ambos vértices) siempre que formen un borde existente (o sean iguales). En 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()) 

No conozco esa biblioteca, pero supongo que podrías hacer lo siguiente:

  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) 

Aclamaciones

Si el gráfico es pequeño, puede recostackr nx.non_edges() en un np.array y np.array de él:

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

Tenga en cuenta que non_edges() devuelve el generador, no la lista real. Pero si lo convierte en un np.array , colecta todos los elementos en el generador. Si su gráfico es grande y escaso, esto puede generar un error de memoria, pero para gráficos pequeños sería la forma más sencilla de hacerlo.