how to select two nodes (pairs of nodes) randomly

Question

I want to extract two nodes from a graph, the catch being that they shouldnt be connected i.e. no direct edge exists between them. i know i can get random edges using "random.choice(g.edges())" but this would give me random nodes that are connected. I want pairs of nodes that are NOT connected (a pair of unconnected edges). help me out guys...thanx

Answer 1

None of the solutions proposed here so far will sample the non-edges (v1,v2) uniformly. Consider the example graph with 4 nodes and 2 edges:

1 —— 2
|
3    4

There are 4 non-edges to choose from: (1,4),(2,3),(2,4),(3,4). Using either Maria's or Philip's method of randomly choosing the first vertex from all 4 vertices and then choosing the second vertex from the restricted set of vertices so as not to create any edges (or self-loops) will give the following probabilities for each non-edge to be chosen:

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

So the procedure is not uniform.

That means if you want uniformly sampled non-edges, you will have to choose both vertices unrestricted and reject the sample (both vertices) whenever they form an existing edge (or are 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 2

I don't know that library, but I'd guess 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)

Cheers

Answer 3

If the graph is small, you can collect nx.non_edges() into an 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 you the generator, not the actual list. But if you turn it into an np.array you acutally collects all the items in the generator. If your graph is large and sparse, this may raise a memory error, but for small graphs it would the most straightforward way to do it.

Answer 4

Simple! :)

Grab a random node - then pick a random node from the list of nodes excluding neighbours and itself. Code to illustrate is 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