How to join two graphs with some probability

Question

Let's say I have the next graphs: red_graph and blue_graph with N nodes which are constructed randomly with probability p1 and p2 to connect pairs of nodes:

red_graph = nx.fast_gnp_random_graph(N, p1)                                                                                                                                                                               
blue_graph = nx.fast_gnp_random_graph(N, p2)

Now I want to join these 2 graphs into 1 with some probability (let's say it q). So q - probability red nodes connect to blue nodes. I didn't find any functionality in NetworkX documentation about that. Any ideas?

Answer 1

Here's code that allows the subgraphs to have different numbers of nodes as well. It takes advantage of nx.bipartite_random_graph which has a particularly efficient implementation: O(V+E) where V is number of vertices and E is number of edges. The standard way to implement a bipartite random graph would be O(N*M) where these are the number of nodes in each partition. It uses the same trick that fast_gnp_random_graph uses to be O(V+E) as opposed to O(V^2).

Nr= N
Nb = N
red_graph = nx.fast_gnp_random_graph(Nr, p1)
blue_graph = nx.fast_gnp_random_graph(Nb, p2)
main_graph = nx.bipartite_random_graph(Nr, Nb, q)

main_graph.add_edges_from(red_graph.edges_iter())
main_graph.add_edges_from(((Nr+x,Nr+y) for x,y in blue_graph.edges_iter()))

Answer 2

You can break down the whole process into three steps:

1. Create the two random graphs (which you've already done): red_graph and blue_graph.
2. Merge the two random graphs into a combined graph. This is only tricky because the nodes in your two random graphs have the same names, but you can easily fix this by adding N to each of the node names in the blue_graph.
3. Add edges to the combined graph connecting nodes in the red_graph and blue_graph with probability q. You can do this in one line using a list comprehension and taking the product of the nodes in the red_graph and blue_graph.

Here's a complete example, with a resulting random graph below:

###############################################################################
# Step 0: Load required modules and set and parameters
###############################################################################
import networkx as nx, matplotlib.pyplot as plt
from itertools import product
from random import random

# Parameters
N  = 5
p1 = 0.5
p2 = 0.5
q  = 0.25

###############################################################################
# Step 1: Create the random graphs
###############################################################################
red_graph = nx.fast_gnp_random_graph(N, p1)
blue_graph = nx.fast_gnp_random_graph(N, p2)

###############################################################################
# Step 2: Combine the random graphs
###############################################################################
combined = nx.Graph()
red      = red_graph.nodes()
# rename the blue nodes
blue     = [ N + node for node in blue_graph.nodes() ] 
combined.add_nodes_from(red)
combined.add_edges_from(red_graph.edges())
combined.add_nodes_from(blue)
# Rename the blue edges with their new node names
combined.add_edges_from([ (N + u, N + v) for u, v in blue_graph.edges() ]) 

###############################################################################
# Step 3: Connect nodes in the blue/red graphs with probability q
###############################################################################
combined.add_edges_from([ (u, v) for u, v in product(red, blue) if random() < q ])


###############################################################################
# Step 4: Plot the graph, including the color of each node
###############################################################################
pos = nx.spring_layout(combined)
nx.draw_networkx_nodes(combined, pos=pos, nodelist=red, node_color='r')
nx.draw_networkx_nodes(combined, pos=pos, nodelist=blue, node_color='b')
nx.draw_networkx_edges(combined, pos=pos)
plt.show()