LINKRADAR / REAL NETWORK STUDY

关键节点观察台

用全图介数识别中转位置，再用结构失效实验检验排名。

当前网络

✓ 全节点 NetworkX 对照通过无权 · 无向 · 精确 Brandes原始匿名 ID

谁在连接网络？

默认按全图介数降序。高介数表示最短路径的中转作用，不等于真实人物的重要性。

RANKING

全图介数 Top 10

下载 CSV ↗

标准无向归一化：raw / ((n−1)(n−2)/2)。排名不包含端点贡献。

NODE LENS

节点参数

点击左侧柱条、下方表格或局部图节点，即可检查原始指标。

EXPLANATORY SUBGRAPH

把排名放回连接结构

介数 Top10 选取的邻居拖动平移 · 滚轮缩放 · 点击检查

AUDITABLE RECORDS

节点排名与参数

全部节点 CSV ↗

原始 ID排名标准展示范围

排名	原始 ID	度数	度排名	raw 介数	归一化介数	分量大小	割点

删除这些节点，结构会怎样？

所有策略使用原图固定排名。随机曲线来自20个独立可复现排列，阴影为10%–90%经验分位范围。

FIXED-RANK REMOVAL

最大连通分量的变化

分母固定为原始 n

原图不连通时初始值可以小于1；经验分位带不是置信区间。该模拟不预测现实行为。

度数与中转作用

散点使用当前所选网络的完整原图，标注介数前十节点；坐标使用对称对数尺度。切换上方网络即可查看另一张图。

结果如何计算，性能如何解释？

Python运行完整算法，浏览器展示已有结果。页面切换与筛选不会重新执行全图介数。

相邻区组复测

首轮真实图计时记录

模式	实际进程	重复	total 中位数 / s	steady 中位数 / s	观察 S_total

total 包含启动、计算通信归并、归一化及清理；steady 排除启动和清理。不同亲和性协议的记录不混合。

来源与指标说明

介数: 统计不包含该节点作为端点的最短路径比例；全起点计算，不是抽样近似。
度数: 直接相连的邻居数量，与最短路径中转作用不同。
割点: 在完整原图中单独删除该节点，会增加连通分量数量；不是现实故障概率。
局部网络: 确定性选取介数前十及其部分邻居，最多120个节点。仅用于解释，未重算局部分数；布局距离不表示地理或实际路径距离。
匿名数据: Facebook为采样自我网络合并图；ca-GrQc为作者合作图。原始ID无法在本项目中对应真实身份。

UNDERSTAND THE COMPUTATION

从一条最短路径，读懂整个项目

先看小图，再读公式。这里解释真实结果使用的定义；交互例子只计算五个教学节点，不会重跑两张真实网络。

我们要算什么？介数中心性

衡量节点承担多少最短路径中转份额的指标。

我们怎样把它算出来？Brandes算法

正向统计路径数量，再反向累计贡献的计算方法。

01 / MODEL & CENTRALITY

把“谁和谁相连”写成数学问题

无权 · 无向 · 简单图

图记为 G = (V, E)：V是节点集合，E是连接集合，n = |V|，m = |E|。每条边长度为1，可以双向走；清洗时去掉自环与重复边，保留所有已知节点和连通分量。

度数：直接连接多少邻居

\deg (v) = | N (v) |, \bar{d} = \frac{2 m}{n}

N(v)是v的邻居集合。平均度为2m/n，因为一条无向边分别给两端各贡献1度；n=0时另作零值处理。

介数：最短路的中转份额

C_{raw} (v) = \sum_{\begin{matrix} {s, t} \subseteq V ∖ {v} \\ s \neq t, σ_{s t} > 0 \end{matrix}} \frac{σ_{s t} (v)}{σ_{s t}}

s、t是不同端点；σ_st是两者之间最短路径的条数，σ_st(v)是其中以v为内部中转点的条数。每组无序端点只算一次；不可达时整项按0处理，不做0/0。

归一化：除以可能的端点对数量

C_{norm} (v) = \frac{C_{raw} (v)}{(n - 1) (n - 2) / 2} n > 2

除去v，还剩n−1个节点，能组成(n−1)(n−2)/2组无序端点对。n≤2时分数为0。非连通图仍使用原始全图n；归一化不会改变同一张图内的排名。

度数、介数和割点回答不同问题。Facebook的58号只有12个邻居，但介数排第9；高介数表示拓扑中转作用，不是现实人物价值。

02 / TRY A SHORTEST-PATH SHARE

两条一样短的路，贡献怎么分？

五节点教学图

端点对观察哪个中转节点

橙色边覆盖当前全部最短路径；绿色节点是端点，深色外圈是观察节点。也可以直接点击节点。

THIS PAIR'S CONTRIBUTION

单个端点对的贡献，不等于该节点的全图介数。

看这张五节点图的完整答案

把全部10组无序端点对都检查一遍；每个节点排除以自身为端点的4组。归一化分母为(5−1)(5−2)/2 = 6。下表由这个教学图的路径份额累计得到。

节点	度数	raw介数	归一化介数

S的raw为0.5，A、B各为1，T为3.5，U为0；与Python中的五节点手算测试一致。T的3.5 = S↔U的1 + A↔U的1 + B↔U的1 + A↔B的0.5。

03 / BRANDES, STEP BY STEP

不枚举所有完整路径，怎样算得更快？

每个节点都作为起点

从起点s向外BFS

像水波一样按距离扩展，记录最短距离dist、路径数σ和所有最短路径前驱P。等长路径都保留，不只挑其中一条。

从远到近回传贡献

按照BFS访问顺序逆序处理，利用路径数比例，把远处节点的贡献分配给前驱。δ表示固定起点下的累计依赖。

覆盖所有起点后汇总

重复上述过程n次，排除起点本身的端点贡献。无向图两个方向重复计数，最终统一除以2，再归一化。

为什么不逐条列出所有路径？S到U的最短路可复用“S到T的最短路再接一条T—U”的结构。大图的等长路径可能很多，Brandes只保存计数与前驱，再合并回传贡献。上面的五节点路径枚举仅用于教学展示。

FOLLOW ONE SOURCE: s = S

固定S为起点，跟着数值走一遍

本演示固定起点S，与上方端点对选择无关。d是距离，σ是路径数，P是前驱；δ是该起点的累计依赖，不是最终全图介数。

节点	距离 d	路径数 σ	前驱 P	当前 δ_S	本源最终写入分数

正向从近到远 · 反向从远到近

展开看路径计数与依赖递推公式

先数最短路径

σ_{s} (w) = \sum_{v \in P_{s} (w)} σ_{s} (v)

σ_s(s)=1；其余节点初始为0。P_s(w)只包含满足dist_s(w)=dist_s(v)+1的邻居；不可达节点不进入反向累计。

再回传依赖

δ_{s} (v) += \frac{σ_{s} (v)}{σ_{s} (w)} (1 + δ_{s} (w))

对每个v∈P_s(w)执行；“+=”表示累加而非覆盖。“1”代表目标w自身的份额，δ_s(w)代表经w继续到更远目标的份额。路径数比值负责公平分摊；最后只在v≠s时把δ_s(v)加入分数。

全起点时间写作O(n(n+m))；连通无权图常简写为O(nm)。每个进程需要O(n+m)量级的图与单源工作空间。这是复杂度描述，不是实际秒数保证。本项目σ使用Python整数，贡献与归并使用float64；“精确”指全起点，而非任意精度算术。

源码对应：brandes.py中的single_source_accumulate与finalize_scores。NetworkX是独立正确性参照，实际串并行分数均由本项目同一内核计算。

04 / PARALLEL SOURCES

三种方法，改变的是哪一层？

分起点任务 · 每进程读完整图

固定一个起点的计算不依赖其他起点的中间结果，所以可以分工；同一次单源计算内部，BFS与逆序累计依然有先后依赖。

serial

一个接一个

一个计算进程遍历所有起点，贡献直接累加到同一个向量。

批0批1批2批3

static_batches

提前固定分工

按batch_id % p分配。下例p=2：进程0做批0、2，进程1做批1、3；空闲时不会改领另一进程的批次。

P0：0 → 2P1：1 → 3

dynamic_batches

空闲就领下一批

同样的批次放进公共队列；哪个进程先空闲，哪个取下一批。可减少等待，也会增加队列管理开销。

公共队列 → 空闲进程

上面的批次条是分工原理示意，不是计时或CPU利用率。若有8个起点、B=2，则4批依次为[0,1]、[2,3]、[4,5]、[6,7]。

每进程局部累计，主进程最终归并

L_{j} (v) = \sum_{s \in S_{j} ∖ {v}} δ_{s} (v); C_{raw} (v) = \frac{1}{2} \sum_{j = 0}^{p - 1} L_{j} (v)

S_j是进程j负责的起点集合；集合之间不重叠，合起来覆盖所有节点。每个局部向量长度都是n，各进程结束时回传一次总向量；主进程归并后统一做无向修正和归一化。

p是计算工作进程数，B是每批起点数，重复次数是整次算法重跑几遍，三者不同。p=1的分批版本仍使用一个工作进程，约1.065的观察比值不能解释为多核收益。比较静态与动态，应固定同一图、p、B和日志设置。

想核验实际发生的分工？

Facebook配对复测的一个p=4、B=128案例中，四个历史PID分别处理1024、1024、967、1024个起点，合计4039个起点、32批。每个起点和批次都检查不重不漏。

spawn创建独立进程，每进程获得完整邻接表副本；本项目没有共享内存零复制。PID与计数说明实际分工，不能代替逐时CPU利用率证据。真实图正式主计时没有逐批时间线。

05 / CONNECTIVITY UNDER REMOVAL

LCC：删掉节点后，最大一块还剩多大？

Largest Connected Component

能沿边互相到达的一组节点叫连通分量。节点数最多的分量就是LCC（最大连通分量）；“LCC大小”是这个集合的节点数。

k = ⌊ q n ⌋, r_{k} = \frac{k}{n}, L (k) = \frac{| LCC (G_{k}) |}{n}

G_k是删除排名前k个节点后的剩余图，q是请求移除比例，r_k是实际比例。纵轴分母固定为原图节点数n，不是n−k；若没有剩余节点，LCC大小按0计。

假设原图100节点，删除20节点后分成60和20两个群体，LCC/n = 60/100 = 0.6；若除以剩余80节点，会变成另一个指标0.75。本项目主曲线使用前者。

介数、度数和随机策略都从原图开始，使用原图固定排名，不每删一次重排。随机结果来自20个独立可复现排列，阴影是10%–90%经验分位范围，不是置信区间。相同移除比例下LCC/n越低，说明该策略造成的连通性破坏越强；不能推广成现实人员价值或故障预测。

06 / READ THE EXPERIMENT TABLE

加速、效率、误差，各在比较什么？

同一图 · 同一内核

总加速比与并行效率

S_{total} = \frac{median (T_{serial,total})}{median (T_{p,total})}, E = \frac{S_{total}}{p}

ca-GrQc的dynamic(p=4)：16.252 / 6.479 ≈ 2.509倍，效率约2.509 / 4 = 62.7%。效率是加速比相对进程数的比值，不是CPU利用率。这里用展示表的四舍五入值作读表示例。

全节点容差比较

| a - b | \leq atol + rtol \cdot | b |

atol控制接近0的绝对误差，rtol随对照值大小缩放。实际全节点检查覆盖raw和normalized，并检查有限值；真实图参照使用atol=10⁻⁸、rtol=10⁻⁷。浮点归并顺序不同可能产生末位差异。

字段	本项目具体含义
total	完整算法调用墙钟，包含工作进程启动、计算通信归并、最终缩放、清理及必要调度开销；不包含下载、清洗、NetworkX参照和画图。
steady	execute_reduce + finalize，排除启动与清理。steady加速与total加速必须分别标注。
重复 / median	相同条件整次重跑，汇总中位数，而非挑最快一次。“重复3次”不是3个进程，也不是只算3个起点。
观察比值与协议	Facebook首轮单工作进程也出现异常快值，不能据该轮四进程比值声称可靠多核加速；固定亲和性的后续配对复测单独统计。

启动、通信、任务不均和系统调度都会影响结果，四个工作进程不保证四倍加速。固定四个逻辑CPU也不等于已确认四个物理核心。

07 / GLOSSARY

定义从哪里来？

公式与项目实际实现核对：Brandes单源内核、无向统一缩放、spawn批次归并，以及固定排名失效协议。

正文、公式与教学交互均为本地HTML/CSS/JS，无需CDN或在线公式库；参考链接仅在主动点击时访问外网。