介数中心性

介数中心性（betweenness centrality）通过经过一个顶点的最短路径份额衡量其中介位置。若一对端点之间有多条同长最短路，就把这一对的贡献按路径份额分摊；起点和终点通常不计为中间顶点。

四边形环 $1-2-3-4-1$ 中，顶点二的邻居一、三之间有两条最短路 $1-2-3$ 和 $1-4-3$，顶点二只获得这一对的一半贡献。把“经过它”简单记成一，会把并列路径造成的分流漏掉。

两条最短路长度均为二，顶点二的这一对贡献为 1/2。

无向图中的计数约定

设 $G=(V,E)$ 为有限无向简单图，边长均为一。对不同顶点 $s,t$，记最短路数为 ${\sigma }_{st}$，其中内部经过 $v$ 的条数为 ${\sigma }_{st}(v)$。本文对无序端点对只数一次，定义 $$B(v)=\sum _{\{s,t\}\subseteq V\setminus \{v\},s\ne t}\frac{{\sigma }_{st}(v)}{{\sigma }_{st}}.$$ 不可达端点对的贡献约定为零，不进行 $0/0$ 除法。若 $n=|V|\ge 3$，归一化介数为 $\hat{B}(v)=B(v)/(\genfrac{}{}{0ex}{}{n-1}{2})$；$n<3$ 时约定为零。每对贡献在零和一之间，所以归一化值也在此范围内。

四边形中对顶点二，只有端点对 $\{1,3\}$ 贡献一半，其余候选对相邻，不会绕经二，所以 $B(2)=1/2$，$\hat{B}(2)=1/6$。其余三个顶点由对称性得到同样数值。

树上的分量公式

在树中任意端点间路径唯一。删去顶点 $v$ 后，设各连通分量大小为 $n_1,\dots ,n_k$，则 $$B(v)=\sum _{i<j}{n}_i{n}_j.$$ 证明分成两种端点位置：同分量中的两点，其唯一树路径不经过 $v$；不同分量中的两点，其唯一路径必须经过 $v$，每对贡献一。第 $i,j$ 个分量间共有 $n_i{n}_j$ 对，逐对相加即可。这给出了公式的全部计数依据。

例如五点路径 $1-2-3-4-5$，删去三得到两个大小二的分量，故 $B(3)=4$；删去二得到大小一、三的分量，故 $B(2)=3$。原始介数依次为 $0,3,4,3,0$，归一化后为 $0,1/2,2/3,1/2,0$。端点虽参与许多路径，但作为中间点的贡献仍是零。

中心的介数由两侧顶点数相乘得到，不能只数与它直接相连的两条边。

还有一个全图复核式。对每个可达无序对 $\{s,t\}$，长度为 $d(s,t)$ 的每条最短路恰有 $d(s,t)-1$ 个内部顶点。把各顶点的路径份额先相加，再按端点对相加，得到 $$\sum _{v}B(v)=\sum _{\{s,t\}\text{ 可达}}(d(s,t)-1).$$ 四边形的四对相邻点贡献零，两对对角点各贡献一，总和二，等于四个顶点各一半。

变式。 星图中心连接四个叶子，中心删去后有四个单点分量，所以 $B=(\genfrac{}{}{0ex}{}{4}{2})=6$、归一化值一；所有叶子为零。若给叶子之间补上全部边，变成完全图，每对端点都有直接边，所有介数反而归零，尽管各顶点的度增加了。

有向图必须使用有序端点对，不能再将贡献除二；加权图中边权若表示距离，应明确为正，以避免零长度环和大量同长路带来的计数问题。介数还假设交通依据最短路并按所设份额分流，它不是实际流量的自动测量。接近中心性度量到其他点的距离，特征向量中心性度量邻居得分反馈，二者与本篇的中介份额具有不同含义。