Как соединить два графика с некоторой вероятностью

Question

Скажем, у меня есть следующие графики: red_graph и blue_graph с N узлов, которые построены случайным образом с вероятностью p1 и p2 для подключения пары узлов:

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

Теперь я хочу присоединить эти 2 графа к 1 с некоторой вероятностью (скажем, q). Итак, q - вероятность, что красные узлы соединяются с синими узлами. Об этом я не нашел в документации NetworkX. Есть идеи?

Answer 1

Вы можете разбить весь процесс на три этапа:

1. Создание двух случайных графов (которые вы уже сделали): red_graph и blue_graph.
2. Объединить два случайных графа в граф combined. Это сложно, потому что узлы в ваших двух случайных графах имеют одинаковые имена, но вы можете легко исправить это, добавив N к каждому из имен узлов в blue_graph.
3. Добавить края в соединительные узлы combined в red_graph и blue_graph с вероятностью q. Вы можете сделать это в одной строке, используя понимание списка и взяв product узлов в red_graph и blue_graph.

Вот полный пример, с результатом случайного графа ниже:

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

Answer 2

Вот код, который позволяет подграфы иметь различное число узлов, а также. Он использует nx.bipartite_random_graph, который имеет особенно эффективную реализацию: O (V + E), где V - число вершин, а E - количество ребер. Стандартный способ реализации двудольного случайного графа будет O (N * M), где это число узлов в каждом разделе. Он использует тот же трюк, что fast_gnp_random_graph использует O (V + E) в отличие от 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()))