一组基于“介于性”的中心性度量

一句话看懂

一个人重要，不一定是因为他认识的人多，而可能是因为别人之间的消息必须经过他。Freeman 把这种“处在中间”的位置量化为介数（betweenness）：统计所有节点对之间的最短路径中，有多大比例经过该节点。

研究背景与问题

20 世纪 40–50 年代，社会心理学的小组沟通实验已经发现：在星形、链形、环形等不同沟通结构中，处在“中心”位置的成员更容易成为领导者，小组的效率也不同。但“中心”应该怎样测量，研究者给出了多种互不一致的定义。有的指标只适用于连通图，有的与网络规模纠缠在一起，不同大小的网络之间无法比较。

Freeman 的目标是：从“控制沟通”这一直觉出发，给出一组定义清楚、可以跨网络比较、对不连通网络也能使用的中心性指标。

核心思想与方法

假设信息总是沿最短路径（geodesic）传递。若节点 $i$ 与 $j$ 之间有 $g_{ij}$ 条最短路径，其中 $g_{ij}(k)$ 条经过节点 $k$ ，那么 $k$ 能“截住” $i$ 与 $j$ 之间消息的概率可以估计为二者之比。

成对依赖： $b_{ij}(k)=g_{ij}(k)/g_{ij}$ 。

节点介数： $C_B(k)=\sum_{i<j,\;i,j\neq k} b_{ij}(k)$ ，即把节点 $k$ 在所有节点对上的成对依赖相加。

标准化介数：在 $n$ 个节点的无向图中，星形图的中心落在全部 $\binom{n-1}{2}=\tfrac{n^2-3n+2}{2}$ 对其他节点的唯一最短路径上，这是 $C_B$ 的最大值。于是定义 $C_B'(k)=\dfrac{2C_B(k)}{n^2-3n+2}$ ，取值在 0 与 1 之间。

在节点指标之外，Freeman 还定义了整个网络的中心化程度（centralization）：先找出介数最大的节点 $k^*$ ，再把所有节点与它的差距 $\sum_i[C_B'(k^*)-C_B'(i)]$ 相加，并除以该求和在星形图中能达到的最大值，使结果落在 0 与 1 之间。星形图的中心化程度为 1；完全图或环中每个节点地位相同，中心化程度为 0。

这一组定义有两个实用优点。第一，若 $i$ 与 $j$ 之间没有路径，这一对节点对任何人的介数都没有贡献，因此不连通的网络也能计算。第二，标准化后的指标与网络规模无关，可以比较不同大小的网络。

主要发现

这是一篇方法论文，主要贡献是定义而不是经验结果：

给出了节点介数、标准化节点介数、网络中心化程度三个层次的度量，三者都以最短路径为基础。
证明了星形图的中心使介数达到最大，并以此作为标准化的基准。
指出介数刻画的是“对沟通的潜在控制力”，与只看直接连接数的度中心性含义不同：一个度很小的节点，如果是两个群体之间唯一的桥，介数可以很高。
介数适用于任意大小、连通或不连通的对称关系网络。

怎样读这篇论文

全文篇幅很短，数学只用到计数。建议先读引言部分对早期沟通实验的回顾，理解作者为什么认为“处在中间”是一种独立的重要性；然后在纸上对星形、链、环三种 5 个节点的小网络手算 $C_B$ 和中心化程度，这比读证明更有帮助。标准化常数的推导可以快速读过。

读完后建议接着读 Freeman 1979 年在 Social Networks 上的综述，那里把度、接近、介数三种中心性放在同一框架下比较。

局限与后续工作

“只走最短路径”的假设：介数假设信息只沿最短路径流动。Newman（2005）提出基于随机游走的介数，Borgatti（2005）则系统讨论了不同“流动方式”应当配合不同中心性。在偏相关网络、共表达网络中，边并不代表物质或信息的传递，介数的含义就很可疑（症状中心性及其解释讨论了这一点）。
计算代价：按定义直接计算需要对每对节点枚举最短路径。Brandes（2001）给出的算法在无权图上复杂度为 $O(nm)$ ，至今仍是 NetworkX 等软件的默认实现；大网络上常用抽样近似。
加权网络：需要先把权重转换成“距离”。相关性越强代表越近，直接把相关系数当距离会得到相反的结论。
从节点到边：把同样的思想用于边，就得到边介数。Girvan 与 Newman（2002）据此提出了按边介数删边的社团发现算法。
介数与“重要性”：高介数节点在网络受攻击时往往很关键，但在生物网络中，高介数是否意味着功能上的重要性需要独立证据，不能直接从拓扑推出。

关联知识

路径、距离与最短路径算法中的最短路径与广度优先搜索是计算介数的基础；BFS 在无权图上一次就能得到从一个源点出发的全部最短路径计数。
Girvan–Newman 算法与边介数中的边介数和 Girvan–Newman 算法，是本文思想在边上的直接推广。
症状中心性及其解释讨论了接近中心性与介数在症状网络中的解释局限，可以与本文的“沟通控制”假设对照阅读。

延伸思考

在一个由两个稠密团块和一条“桥”边组成的网络里，桥两端节点的度可能不大，但介数很高。请构造一个具体的小例子并计算，体会度与介数的差别。
在脑结构网络中，白质纤维确实承担信号传递；在基因共表达网络中，边只代表表达相关。介数在这两类网络中的含义有什么不同？
Freeman 的中心化程度以星形图为最大值。对一个度分布重尾的 PPI 网络和一个近似规则的格点网络，你预期它们的介数中心化程度谁更高？为什么？