CODEWITHSUNDEEP
pythonnodesnetworkx
irfanbukhari
irfanbukhari

Reputation: 205

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

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

Upvotes: 7

Views: 10011

Answers (4)

DarkZero
DarkZero

Reputation: 2344

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.

Upvotes: 0

JanisK
JanisK

Reputation: 41

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

Upvotes: 4

Maria Zverina
Maria Zverina

Reputation: 11173

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

Upvotes: 11

Philip Schaffner
Philip Schaffner

Reputation: 43

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

Upvotes: 1

Related Questions