大规模网络的计算策略

“大规模”是相对于算法复杂度而言的。在一个 2 万节点、6 万条边的稀疏网络上，度、连通分支、PageRank 都很快完成；但所有节点对的最短路径与精确介数的计算量与 $NM$ 成正比，规模再大一两个数量级就会变得不可行。应对策略可以归为五类。

1. 先缩小问题

• 按研究问题过滤：只保留高置信度边、特定组织表达的基因、研究关心的子网络。
• 结构化约简：最大连通分支、$k$-核（nx.k_core）、去除度为 1 的“悬挂”节点（若研究问题允许）。
• 每一步都要报告保留与丢弃的节点和边。过滤本身是一个需要做敏感性分析的分析选择。

2. 用稀疏矩阵和专门的数值库

生物网络几乎都是稀疏的（$M\ll N^2$）。稠密邻接矩阵的内存与 $N^2$ 成正比，稀疏格式（CSR、COO）只与非零元个数成正比。代码示例中 2 万节点的 BA 网络：稠密 float64 矩阵约需 3200 MB，CSR 格式约 2 MB。很多计算可以完全在稀疏矩阵上完成：

3. 近似算法

• 抽样介数：Brandes 算法对每个源点做一次单源最短路径并“回传”依赖值。只取 $k$ 个随机源点，再按 $N/k$ 放大，得到介数的无偏估计（Brandes 与 Pich 2007）；NetworkX 中即 betweenness_centrality(G, k=k, seed=s)。Riondato 与 Kornaropoulos（2016）给出了基于最短路径抽样、具有误差上界保证的近似算法。代码示例中，在 2000 节点的 BA 网络上，$k=200$ 个源点的估计耗时约为精确计算的十分之一，与精确值的 Spearman 秩相关约 0.91，前 20 名中有 19 个重合；$k=50$ 时秩相关约 0.86、前 20 名重合 14 个。也就是说，抽样介数适合找“排名靠前的节点”，对中低介数节点的精确排序不可靠。
• 平均路径长度：从随机抽取的若干源点做 BFS，用样本均值估计全网平均距离。
• 社团检测：Louvain、Leiden、标签传播在稀疏网络上的运行时间大致随边数近线性增长，适合大网络；Girvan–Newman 需要反复计算边介数，只适合小网络。

4. 换工具或换后端

NetworkX 3 起支持“后端分派”：安装 nx-parallel（基于 joblib 的并行实现）或 nx-cugraph（基于 NVIDIA GPU 的 RAPIDS cuGraph）等后端后，可以用函数的 backend= 参数、环境变量 NETWORKX_BACKEND_PRIORITY 或 nx.config.backend_priority 切换实现，代码其余部分不变。也可以直接改用 igraph、graph-tool、NetworKit 等 C/C++ 实现的库。

5. 谨慎使用网络抽样

当完整网络无法获得或无法处理时，人们会抽取子网络。需要牢记：子网络的统计性质一般不等于全网络的性质。均匀抽取节点后取诱导子图，每条边被保留的概率约为抽样比例的平方，度分布整体左移并改变形状；Stumpf、Wiuf 与 May（2005）证明，无标度网络的随机子网一般不再是无标度的——这对“相互作用组不完整”的生物网络尤其重要，因为现有 PPI 数据本身就可以看作真实相互作用组的一个非随机样本。Leskovec 与 Faloutsos（2006）比较了多种大图抽样方法，基于随机游走或“森林火灾”式扩展的方法比均匀节点抽样更能保留原网络的多种性质。代码示例中，从 2 万节点 BA 网络随机抽取 20% 节点，诱导子图的平均度从 6.0 降到约 1.2，最大度从 323 降到 45，并出现约 1500 个孤立点。