近似中介中心性算法的误差–成本前沿：从 ε-绝对误差保证转向 Top-k 排名保真度的独立检验

1 · 研究问题

近似中介中心性（betweenness centrality, BC）算法 KADABRA、RK（Riondato–Kornaropoulos）与 ABRA 所提供的理论保证是"所有顶点的 BC 值绝对误差 ≤ ε（置信度 1−δ）"，但实际应用几乎只用排名。在给定的墙钟时间预算下，这三种算法给出的 Top-k 顶点集合保真度（与精确 Brandes 结果的交集率、Kendall τ、最大排名反转距离）孰优孰劣？其排序是否与文献中按"达到 ε 保证所需时间"给出的排序一致？

2 · 研究背景与空白

技术背景。 顶点 v 的中介中心性定义为经过 v 的最短路径对数占全部顶点对最短路径的比例，是网络科学中识别"桥接节点"的核心指标（用于交通枢纽、蛋白互作网络的关键蛋白、社交网络的信息中介）。Brandes 算法把精确计算降到 O(nm)（无权图），但对百万边规模的图仍需数小时。近似算法通过随机采样最短路径来估计：RK 依据网络直径确定所需样本量；ABRA 用 Rademacher 平均等经验界自适应决定何时停止；KADABRA 改造广度优先搜索的方式并采用不同的采样策略。这类课题在资源上完全可控：图算法是纯 CPU 整数运算，且本课题的"精确基准真值"可以通过限制图规模（顶点数 ≤ 5×10⁴）在笔记本上数小时内算出，不需要任何 GPU 或集群。

已有工作到哪一步。 KADABRA（Borassi–Natale，ACM JEA 2018 / arXiv:1604.08553）报告：在真实复杂网络上显著优于此前全部方法，无向图上平均比 RK 快约 100 倍、有向图上约 70 倍，比 ABRA 快 1000 倍以上，且在误差容限趋于 0 时相对 RK 的优势进一步扩大；ABRA（Riondato–Upfal）报告其在运行时与样本数上均大幅优于同等质量保证的既有算法，并支持全动态图。另有专门比较近似方法速度与精度的实验综述（Computational Social Networks, 2019）、有向图上精确与近似算法的比较（arXiv:1708.08739），以及若干自适应估计与图神经网络排名方法（arXiv:1810.10094、arXiv:1905.10418）。

空白在于：这些比较几乎全部以"达到给定 ε 的绝对误差保证"为终点来衡量成本，而使用者真正需要的"在固定时间预算内谁的 Top-k 排名最准"这一等成本口径，缺少系统的公开测量。两者不等价：ε-保证是对所有顶点的一致界，而 Top-k 只关心分布右尾的少数顶点；一个算法可能为了保证尾部之外的精度而浪费大量样本。这个空白属于"评价维度转换"，可靠性高，且结论正负都成立（若排序不变，说明 ε-保证是排名质量的良好代理；若排序翻转，说明现有比较误导了应用侧的算法选择）。

3 · 可检验假设

• H1：在等墙钟时间预算口径下，跨 ≥ 15 个图的 Top-100 交集率排序与文献按 ε-保证成本给出的排序不完全一致：至少在 1/3 的图上发生排名翻转（即某个在 ε 口径下更慢的算法，在等时间口径下给出更高的 Top-100 交集率）。若翻转比例 < 10%，H1 被否证，ε-保证被确立为排名质量的良好代理。
• H2：Top-k 保真度的差异幅度随 k 减小而增大（k = 10 时的算法间差距 ≥ k = 1000 时的两倍），因为小 k 更依赖对分布极右尾的采样效率。若差距随 k 无系统变化，说明三种采样策略在尾部的行为等价。

4 · 量化验收标准

1. 方法学校验（硬门槛）：（a）用自建管线在文献使用过的至少 3 个公共图上重现 KADABRA 相对 RK 的加速比，与已发表数值同数量级且相对排序一致（跨硬件允许 3 倍以内偏差）；（b）在 ≥ 5 个顶点数 ≤ 5×10⁴ 的图上，用自建/调用的精确 Brandes 实现与 NetworkX 的 betweenness_centrality 交叉比对，全部顶点的 BC 值相对偏差 ≤ 1×10⁻⁶（同一定义与归一化下应完全一致，差异只能来自浮点）。这两条不过关，后续全部结论无效。
2. 真值口径写死：Top-k 保真度的参照必须是精确 Brandes 结果，因此主分析限制在顶点数 ≤ 5×10⁴ 且精确计算可在 ≤ 6 机时完成的图上；对更大的图，只做"高样本量近似作为伪真值"的补充分析，并明确标注伪真值本身的误差棒，不与主分析混报。
3. 等成本口径：主口径为等墙钟时间预算（每图设 3 档预算：精确计算耗时的 1%、5%、20%），辅口径为等样本数；两种都要报。这是本课题"双成本口径"的具体形式，两者结论不一致时必须讨论。
4. 随机性与统计：每个（图 × 算法 × 预算）组合用 ≥ 20 个固定随机种子独立运行；报 Top-k 交集率与 Kendall τ 的中位数与 IQR，给自助法 95% 置信区间；跨算法比较用配对 Wilcoxon 符号秩检验（配对单位为"图 × 种子"）。k 取 {10, 100, 1000} 三档。
5. 样本量：≥ 15 个图，覆盖社交、网页、道路、生物（蛋白互作）与合成幂律图五类；顶点数跨 2 个数量级；并同时报告每图的直径与度分布参数（RK 的样本量依赖直径，这是解释结果的必要协变量）。
6. 基准测试方法学：所有计时在固定频率、绑核、无后台负载的条件下进行，重复 ≥ 5 次取中位数与 IQR，不报均值；线程数固定为 1（KADABRA 等实现支持并行，但并行会引入不可比的调度噪声，须在正文声明这一选择并单独用一组并行实验说明其影响）。
7. 可复现性：全部脚本、图清单与下载脚本、原始结果 CSV、统计与绘图脚本开源；一键重跑脚本；全部种子写死。

5 · 数据与工具

用途	来源 / 工具
近似 BC 算法实现	NetworKit（networkit pip 可装，C++ 内核 + Python 绑定，含 KadabraBetweenness 与 EstimateBetweenness/RK 类实现；ABRA 是否内置需核实，若无须自行实现或使用作者原始代码）。仅用于校验与对比，不计入本项目贡献
精确 BC	NetworKit 的 Betweenness（C++ Brandes，快）；NetworkX 的 betweenness_centrality（纯 Python，慢但作为独立交叉校验）；igraph 的 betweenness（第三方独立实现，用于三方比对）
图数据	SNAP（社交/网页/道路网）；SuiteSparse Matrix Collection；BioGRID 或 STRING 的蛋白互作网络（公开下载，需按物种筛选控制规模）；NetworkX/NetworKit 的合成生成器（幂律、LFR）
统计与作图	Python + SciPy（Wilcoxon、Kendall τ）+ Matplotlib
算力	纯 CPU。精确 Brandes 的复杂度 O(nm)：n = 5×10⁴、m = 5×10⁵ 的图约 2.5×10¹⁰ 次基本操作，NetworKit 的 C++ 实现单线程估计数小时（须在第 1 阶段实测标定，不得凭估计）。内存需求以邻接表为主，16 GB 充裕。超出范围：顶点数 ≥ 10⁶ 的图无法给出精确真值，不进入主分析

6 · 方法路径

1. 装 NetworKit / NetworkX / igraph，用小图（顶点数 ≤ 200）三方比对精确 BC 值，确认定义与归一化一致；完成验收第 1 条的两项校验并归档。
2. 核实工具能力边界：NetworKit 内置了 KADABRA 与哪种 RK 变体、ABRA 是否可得、各实现的 ε/δ 参数语义是否一致（不同实现对 ε 的定义可能相差一个归一化因子，这是本课题最容易出错的地方，必须在此步核实清楚）；确认各实现能否强制单线程。
3. 实测精确 Brandes 的运行成本随 (n, m) 的标度，据此确定主分析的图规模上界并锁定图样本清单（≥ 15 图，五类覆盖）。
4. 计算并归档全部主分析图的精确 BC 真值与协变量（直径、度分布参数、连通性）。
5. 执行主扫描：3 算法 × 3 档时间预算 × 15+ 图 × 20 种子，记录 Top-k 交集率、Kendall τ、最大排名反转距离与实际耗时。
6. 分析：等时间预算与等样本数两种口径的对照表、H1 的翻转比例统计与配对 Wilcoxon 检验、H2 的 k 依赖趋势；以直径与度分布为协变量解释算法间差异。
7. 独立交叉校验：（a）用 igraph 的独立实现复算至少 3 个图的精确 BC，验证真值无误；（b）在 LFR 合成图上做受控实验——固定 n、m 只改变直径（通过调节社区结构与随机重连），检验 RK 相对 KADABRA 的劣势是否确实随直径增大而扩大（这是对 RK 样本量依赖直径这一机制的直接检验）。

7 · 新颖性边界

本课题不声称：不提出新的近似算法，不改进任何采样策略，不给出新的概率界或复杂度界，不声称哪个算法"更好"这一笼统判断。KADABRA、RK、ABRA 与 NetworKit / NetworkX / igraph 的全部实现均为他人工作，标注为对照基准，不计入本项目贡献；全部图数据来自公开数据库，不计入本项目的数据贡献。

已有工作完成了什么：Borassi 与 Natale（KADABRA, ACM JEA 2018）给出了 KADABRA 相对 RK 约 100 倍（无向）/ 70 倍（有向）、相对 ABRA 逾 1000 倍的加速，并指出误差容限趋零时优势扩大；Riondato 与 Upfal（ABRA）给出了自适应采样的质量保证与动态图支持；另有专门的速度–精度实验综述与有向图上的精确/近似比较。这些结论本项目引用而不重复声称。历届丘奖对照：2021 年金奖《Efficient Algorithm for Parallel Bi-core Decomposition》同属"图上的中心性/分解计算"，但其贡献是一个新的并行算法；本课题不提出算法，只做等成本口径下的评价维度转换，两者在贡献类型上不重叠。

本项目的贡献：把评价维度从"达到 ε 绝对误差保证的成本"转换为"等墙钟时间预算下的 Top-k 排名保真度"，并检验既有排序在这一应用侧口径下是否保持。主结论是这份"等成本前沿 + 排名翻转清单"，不是任何新算法。

为什么有价值：应用者（网络科学、生物信息）几乎只使用 BC 排名而非绝对值，却依据 ε-保证的比较来选算法。若排序保持，ε-保证被确立为排名质量的合理代理，这是一条有用的正面结论；若翻转，则说明应用侧的算法选择建议需要重写。

风险提示：三种算法在 Top-k 上"实际上差不多"是可能结果。此时必须用 20 种子 × 15 图的配对设计给出置信区间，证明本实验有能力分辨交集率 5 个百分点量级的差异；若功效不足，须扩大种子数或图数，不得直接下"等价"结论。

8 · 决策门槛（go / no-go）

• 第 4 周：参数语义门槛。若无法确认三种实现的 ε/δ 定义一致，必须在此周解决——这是需要提前核实而非边做边发现的事项。若确实不一致，降级路径 A：整体放弃 ε 参数口径，改为纯样本数/时间预算驱动（直接指定采样条数或运行时长，绕开 ε 的定义分歧）。主结论框架（等成本下的排名保真度）完全不受影响，反而更干净。
• 第 8 周：ABRA 可得性核实完毕。若无内置实现且作者代码无法运行，降级路径 B：算法集缩为 KADABRA + RK + 一个自行实现的朴素均匀最短路采样基线（后者代码量约 150 行，且作为"教科书方法"参照有独立价值）。三算法的下限保持，主结论不变。
• 第 12 周：精确真值的算力标定完成，图样本清单锁定。若精确 Brandes 在目标规模上超时，降级路径 C：把主分析图规模上界下调至 n ≤ 2×10⁴，图数量补到 20 个以维持统计功效。宁可用更多更小的图，不可用更少更大的图——本课题的统计单位是"图"，样本量比单图规模重要。
• 第 28 周：主扫描完成且 H1 有明确判定。若进度不足，降级路径 D：时间预算档从 3 档减为 2 档（1% 与 10%），k 从 3 档减为 2 档（10 与 100，即差异最可能出现的两档），种子数保持 20 不变。
• 预算裁剪顺序：图类别数（下限 3 类）→ 时间预算档数 → k 档数 → （绝不裁剪）种子数与精确真值的正确性校验。
• 选择前提：适合对网络科学有兴趣、能读懂采样算法的概率保证（不必会证）、并能接受"结论可能是三者等价"的学生。本路线全程 Python 可完成，工程门槛低于 K01/K05，是编程基础较弱学生的首选之一。

---