如何在networkx中高效构建大规模二部有向随机模拟图

核心思路是完全抛弃O(N*M)复杂度的嵌套遍历逻辑，向量化批量采样+批量加边，时间复杂度仅和最终边总量相关，可支撑单类30万级节点的构建需求。

前置说明 #

这类图属于二部有向随机图，仅存在跨类边，同类无连接，构建性能瓶颈完全来自Python层循环开销，优化方向是把所有采样、计算逻辑交给底层C实现的数值库完成，避免Python层循环。

具体实现步骤 #

1. 节点预创建 #

提前给两类节点做编号区分，比如I类节点编号范围为0 ~ n_I-1，T类节点编号范围为n_I ~ n_I + n_T -1，可按需添加type属性方便后续业务区分，节点添加操作是O(N)复杂度，无性能压力。

2. 边批量采样 #

根据边的概率大小选择两种采样方案：

• 低概率场景（p_i/p_o < 0.01）：边总量远小于两类节点乘积，直接随机采样边对后去重，效率最高

  import numpy as np
  import networkx as nx
  
  # 自定义参数
  n_I = 5000  # I类节点数
  n_T = 5000  # T类节点数
  p_i = 0.001 # I→T边概率
  p_o = 0.001 # T→I边概率
  
  # 初始化图+添加节点
  G = nx.DiGraph()
  G.add_nodes_from(range(n_I), type="I")
  G.add_nodes_from(range(n_I, n_I + n_T), type="T")
  
  # 采样I→T边
  expected_i = int(n_I * n_T * p_i)
  # 多采样10%抵消随机重复
  sample_size_i = int(expected_i * 1.1)
  i_idx = np.random.randint(0, n_I, size=sample_size_i)
  t_idx = np.random.randint(n_I, n_I + n_T, size=sample_size_i)
  # 去重后取对应数量的边
  edges_i = np.unique(np.column_stack((i_idx, t_idx)), axis=0)[:expected_i]
  
  # 采样T→I边逻辑同上
  expected_o = int(n_I * n_T * p_o)
  sample_size_o = int(expected_o * 1.1)
  t_idx_o = np.random.randint(n_I, n_I + n_T, size=sample_size_o)
  i_idx_o = np.random.randint(0, n_I, size=sample_size_o)
  edges_o = np.unique(np.column_stack((t_idx_o, i_idx_o)), axis=0)[:expected_o]
  

• 高概率场景（p_i/p_o ≥ 0.01）：边重复率高，改用逐节点二项分布采样，避免无效采样冗余
  对每个I节点采样出边数（服从二项分布B(n_T, p_i)），再采样对应不重复的T节点，30万次节点循环开销远低于嵌套循环。

3. 批量加边 #

直接调用NetworkX的add_edges_from方法批量添加采样得到的边列表，该方法底层做过优化，比循环单条加边性能高3~5个数量级：

G.add_edges_from(edges_i.tolist())
G.add_edges_from(edges_o.tolist())

超大规模场景优化（单类节点≥10万） #

NetworkX本身是纯Python实现，内存和性能开销较高，节点规模到30万级时建议替换为igraph或graph-tool库，两类库的核心逻辑为C实现，批量加边性能比NetworkX高1_{2个数量级，内存占用仅为NetworkX的1/3}1/2。

注意事项 #

构建前先估算边总量：总边数 = n_I * n_T * (p_i + p_o)，普通消费级设备可承载的边上限约为1亿条以内，超过该规模需要改用磁盘存储的图数据库方案。

内容的提问来源于stack exchange，提问作者Duccio Borchi