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

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

Answer 2

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 3

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