边中心度

最近在改善 DN11 的网络拓扑前端展示效果，在图结构上做了不小的调整，记录一下。 边中心度 上面展示的是我的 OSPF 网络拓扑，可以在 https://status.dn11.top/#/ospf/4220084444 看到实时的图像。 除了你见过的所有的 OSPF 拓扑图都会展示的 cost 和 routerId 一类的基本结构，你会很容易地注意到：这里的每一个边都有宽度。这就是边中心度在图中的展示方式。 边中心度这个概念简单来说就是通过某条边的最短路径的数量再做一点归一化，归一化前的边 $e$ 的中心度可以用这个公式表示: $$ c(e) = \sum_{s, t \in V} \frac{\sigma(s, t | e)}{\sigma(s, t)} $$ 摘自 networkX 需要注意的是不同于 networkX 的表述，本文的“边”均为有向边 $V$ 所有节点的集合，$\sigma(s, t)$ 是 $(s 到 t)$ 间最短路径的数量，$\sigma(s, t | e)$ 是其中经过有向边 $e$ 的最短路径的数量。 具体的公式相比前面的描述而言将 ECMP 路由纳入了考虑，将权重分给了 ECMP 路由。 归一化 为了在节点数量变化的情况下持续评估边中心度，我给边中心度做了一次归一化，简单来说就是除以当前节点数量 $n$ 下可以达到的边中心度的最大值。 $$ c_{max}(n) = \begin{cases} 0& n<2 \ (n-1)(n-2)+1 &n>=2 \end{cases} $$ ...