How to select two nodes (pairs of nodes) randomly from a graph that are NOT connected, Python, networkx

Question

I want to extract two nodes from the graph, and the catch is that they should not be connected, i.e. there is no straight edge between them. I know that I can get random edges using "random.choice (g.edges ())", but that will give me random nodes that are connected. I want pairs of nodes that are NOT connected (a pair of unconnected edges). help me guys ... thanx

Answer 1

Simple! :)

Take a random node - then select a random node from the list of nodes, excluding neighbors and yourself. The code for illustration is given below. :)

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 2

None of the solutions proposed here will uniformly map non-edges (v1, v2). Consider an example graph with 4 nodes and two edges:

 1 —— 2 | 3 4 

There are 4 non-edges: (1,4), (2,3), (2,4), (3,4). Using the Mary or Philippe method to randomly select the first vertex from all four vertices, and then choosing the second vertex from a limited set of vertices so as not to create any edges (or self-intersections), the following probabilities for each non-selectable edge will be given:

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

Thus, the procedure is not homogeneous.

This means that if you want to evenly discretize non-edges, you will have to select both vertices indefinitely and reject the selection (both vertices) when they form an existing edge (or equal). In 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 3

I do not know this library, but I would suggest that you could do the following:

  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) 

Greetings

Answer 4

If the graph is small, you can collect nx.non_edges() in np.array and random.choice from it:

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

Beware that non_edges() itself returns the generator to you, not the actual list. But if you turn it into np.array , you will neatly collect all the elements in the generator. If your graph is large and sparse, this may cause a memory error, but for small graphs this will be the easiest way to do this.