Networkx处理超14万节点二分图投影时内存不足求解决方案

我尝试使用NetworkX的projected_graph方法对一个包含14万+节点的二分图（B）进行投影，但受内存限制，程序持续崩溃。我曾尝试通过稀疏矩阵乘法计算邻接矩阵，但由于矩阵稀疏度不足，该方法也未能奏效。恳请各位提供解决方案。

原始代码：

import networkx as nx
from networkx.algorithms import bipartite

B.add_nodes_from(inmates_list, bipartite=0)
B.add_nodes_from(cells_list, bipartite=1)

inmates = set(n for n,d in B.nodes(data=True) if d['bipartite']==0)
cells = set(B) - inmates
G = bipartite.projected_graph(B, inmates)

方案1：迭代式构建投影图（最低内存开销） #

不用一次性生成完整投影图，而是遍历每个cell，把共享该cell的inmates两两连边。这种方式不需要存储大矩阵，边遍历边构建，内存占用大幅降低。

代码示例：

import networkx as nx

# 初始化投影图，先加入所有inmates节点
G = nx.Graph()
G.add_nodes_from(inmates_list)

# 遍历每个cell，处理关联的inmates
for cell in cells_list:
    connected_inmates = list(B.neighbors(cell))
    # 生成两两组合并添加边
    for i in range(len(connected_inmates)):
        for j in range(i+1, len(connected_inmates)):
            u, v = connected_inmates[i], connected_inmates[j]
            # 若需要统计共同cell数，可累加权重
            if G.has_edge(u, v):
                G[u][v]['shared_cells'] = G[u][v].get('shared_cells', 0) + 1
            else:
                G.add_edge(u, v, shared_cells=1)

方案2：优化NetworkX原生投影 #

NetworkX的projected_graph默认会加载整个图到内存，可先清理节点冗余属性，减少内存占用后再执行投影：

# 清理节点无关属性，只保留二分标记
for node in B.nodes:
    for key in list(B.nodes[node].keys()):
        if key != 'bipartite':
            del B.nodes[node][key]

# 直接投影，避免重复计算节点集合
inmates = set(inmates_list)
G = bipartite.projected_graph(B, inmates)

方案3：换用更高效的图处理库 #

如果NetworkX的内存效率仍不满足需求，试试专门针对大规模图优化的库：

• igraph：内存占用远低于NetworkX，投影速度更快
  示例代码：

  import igraph as ig
  
  # 构建二分图映射：先将节点转成索引
  inmate_idx = {n: i for i, n in enumerate(inmates_list)}
  cell_idx = {n: i + len(inmates_list) for i, n in enumerate(cells_list)}
  
  # 创建igraph对象，标记二分类型
  g = ig.Graph()
  g.add_vertices(len(inmate_idx) + len(cell_idx))
  g.vs['type'] = [0]*len(inmate_idx) + [1]*len(cell_idx)
  
  # 添加所有边
  edges = [(inmate_idx[u], cell_idx[v]) for u, v in B.edges()]
  g.add_edges(edges)
  
  # 投影到inmates节点（type=0）
  projected_graph, _ = g.bipartite_projection(types=g.vs['type'])
  

• graph-tool：内存效率更高，但安装门槛略高，适合超大规模图处理

方案4：分块处理投影 #

如果整个图还是太大，可将cells分批次处理，分别投影后合并结果：

from itertools import islice

# 定义分块工具函数
def split_in_chunks(iterable, chunk_size):
    iterator = iter(iterable)
    while chunk := list(islice(iterator, chunk_size)):
        yield chunk

# 初始化总投影图
G = nx.Graph()
G.add_nodes_from(inmates_list)

# 按每1000个cell为一块处理
for cell_chunk in split_in_chunks(cells_list, 1000):
    # 构建当前块的子二分图
    sub_bipartite = nx.Graph()
    sub_bipartite.add_nodes_from(cell_chunk, bipartite=1)
    # 添加该块cell对应的所有边
    for cell in cell_chunk:
        sub_bipartite.add_edges_from((cell, n) for n in B.neighbors(cell))
    # 生成子投影图
    sub_proj = bipartite.projected_graph(sub_bipartite, inmates & set(sub_bipartite.nodes()))
    # 合并到总图，累加共享cell数
    for u, v in sub_proj.edges():
        if G.has_edge(u, v):
            G[u][v]['shared_cells'] += 1
        else:
            G.add_edge(u, v, shared_cells=1)

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