交通地理与网络科学/中心性

摘要

交通地理中存在各种网络，例如航空网络、道路网络和运河网络。一个重要的问题是如何衡量这些网络。如果我们关注节点的属性，问题可以是：某些节点有多重要？以及如何量化它们的重要性？

中心性 衡量指标通常用于衡量节点的重要性。主要有三个类别：度中心性、接近中心性和中介中心性。

度中心性

度中心性通过节点所拥有的边数（度）来衡量节点的重要性。其理念是，边数越多的节点越重要。从数学上讲，对于节点 j，其度中心性计算为其度的数量除以 n-1，其中 n 是图中边的总数。

接近中心性

接近中心性 通过节点到其他节点的测地距离来衡量节点的重要性。其理念是，节点离其他节点越近，该节点就越重要。从数学上讲，它计算为所有其他节点测地距离之和的倒数。

中介中心性

中介中心性 通过节点在其他节点之间的路径比例来衡量节点的重要性。其理念是，连接更多其他节点的节点越重要。从数学上讲，节点 j 的中介中心性计算为从一个节点 s 到另一个节点 t 的最短路径中经过 j 的比例。

一个思想实验

您将使用哪种中心性指标来回答以下问题？。

• 如果我需要为我新成立的组织招募 10 人，我应该考虑谁？
• 如果我要将一条信息传递给这个网络中的三个人，让他们依次转达给他们的朋友等等。我应该选择哪三个人？
• 如果我要根据我的所有朋友在这个网络中的“中心性”对他们进行排名，我该如何去做？
• 如果我要为这个 500 人的团队提名一个领导人，我应该选择谁？

技术讨论

改编自维基百科关于 中心性 的文章

在 w:图论 和 w:网络分析 中，存在各种度量图中顶点的中心性，这些度量决定了顶点在图中的相对重要性（例如，一个人在w:社交网络中的重要性，或者，在w:空间句法理论中，一个房间在一个建筑中的重要性，或者一条道路在一个w:城市网络中的使用程度）。

网络分析中广泛使用四种中心性度量：度中心性、中介性、接近性和特征向量中心性。有关对加权网络的回顾以及泛化，请参见 Opsahl 等人 (2010)。

度中心性

主要文章：度 (图论)

第一个也是最简单的就是度中心性。度中心性定义为与一个节点相连的边的数量（即，一个节点所拥有的联系数量）。度通常根据节点在网络中感染流经网络的东西（如病毒或某种信息）的直接风险进行解释。如果网络是有向的（这意味着联系是有方向的），那么我们通常定义两种独立的度中心性度量，即w:入度 和 w:出度。入度是节点接收到的联系数量的统计，而出度是节点发出的联系数量的统计。对于友谊或建议等积极的关系，我们通常将入度解释为一种受欢迎程度，而将出度解释为爱交际程度。

对于一个图 $G:=(V,E)$，其中有 n 个顶点，顶点 $v$ 的度中心度 $C_{D}(v)$ 为

$C_{D}(v)={\frac {{\text{deg}}(v)}{n-1}}$

在一个图的 密集 邻接矩阵 表示中，计算所有节点 $V$ 的度中心度需要 $\Theta (V^{2})$；而在一个图的 稀疏 邻接矩阵 表示中，计算所有边 $E$ 的度中心度需要 $\Theta (E)$。

中心度的定义可以扩展到图。令 $v*$ 为图 $G$ 中度中心度最高的节点。令 $X:=(Y,Z)$ 为使以下量最大化的 $n$ 个节点连接的图（$y*$ 为图 $X$ 中度中心度最高的节点）

$H=\displaystyle {\sum _{j=1}^{|Y|}{C_{D}(y*)-C_{D}(y_{j})}}$

则图 $G$ 的度中心度定义如下：

$C_{D}(G)={\frac {\displaystyle {\sum _{i=1}^{|V|}{[C_{D}(v*)-C_{D}(v_{i})]}}}{H}}$

$H$ 在图 $X$ 包含一个连接到所有其他节点的节点，而所有其他节点仅连接到该中心节点（一个 w:star graph）时最大化。在这种情况下

$H=(n-1)(1-{\frac {1}{n-1}})=n-2$

因此 $G$ 的度中心性简化为

$C_{D}(G)={\frac {\displaystyle {\sum _{i=1}^{|V|}{[C_{D}(v*)-C_{D}(v_{i})]}}}{n-2}}$

中介中心性

色调（从红色=0 到蓝色=最大）显示节点介数中心性。

介数中心性是图中 顶点 的一个中心性度量（也存在 边 介数中心性，这里没有讨论）。出现在其他顶点之间许多 最短路径 上的顶点比那些不在最短路径上的顶点具有更高的介数中心性。

对于具有 n 个顶点的图 $G:=(V,E)$，顶点 $v$ 的介数中心性 $C_{B}(v)$ 如下计算

1. 对于每对顶点 (s,t)，计算它们之间的所有 最短路径。

2. 对于每对顶点 (s,t)，确定通过目标顶点（此处为顶点 v）的最短路径所占的比例。

3. 对所有顶点对 (s,t) 的比例进行求和。

或者，更简洁地说：

$C_{B}(v)=\sum _{s\neq v\neq t\in V}{\frac {\sigma _{st}(v)}{\sigma _{st}}}$

其中 $\sigma _{st}$ 是从s到t的最短路径数量，而 $\sigma _{st}(v)$ 是从s到t且经过顶点v的最短路径数量。可以通过除以检查的路径数量来进行归一化，即$(n-1)(n-2).$ 对于无向图，只需要检查每对顶点之间方向之一，因此总共只有$(n-1)(n-2)/2$ 条路径，这也等于不包括v的顶点对的数量。例如，在无向星形图中，中心顶点（包含在所有可能的 shortest path 中）的介数为$(n-1)(n-2)/2$（归一化后为 1），而叶子（不包含在任何最短路径中）的介数为 0。

计算图中所有顶点的介数和接近中心度需要计算图中所有顶点对之间的最短路径。这需要 $\Theta (V^{3})$ 时间，使用 w:弗洛伊德-沃舍尔算法，修改为不仅找到一条路径，而且计算两个节点之间所有最短路径。在稀疏图上，w:约翰逊算法 可能更有效，需要$O(V^{2}\log V+VE)$ 时间。在无权图上，使用 Brandes 算法计算介数中心度需要 $O(VE)$ 时间。

在计算图中所有顶点的介数和接近中心度时，假设图是无向的、连通的，并且允许存在自环和重边。当专门处理网络图时，通常图中没有自环或重边，以保持简单的关系（边表示两个人或顶点之间的连接）。在这种情况下，使用 Brandes 算法会将最终的中心度分数除以 2，以说明每条最短路径都被计算了两次。

接近中心性

在w:拓扑学和数学中相关的领域，接近度是拓扑空间中的基本概念之一。直观地说，我们说两个集合是接近的，如果它们彼此任意接近。这个概念可以在w:度量空间中自然地定义，其中定义了空间元素之间的距离概念，但它可以推广到拓扑空间，在拓扑空间中，我们没有具体的方法来度量距离。

在w:图论中，接近度是图中顶点的中心度度量。对其他顶点“浅”的顶点（即那些倾向于对图中其他顶点有较短的测地距离的顶点）具有较高的接近度。在w:网络分析中，接近度被用来表示最短路径长度，因为它对更中心化的顶点赋予更高的值，因此通常与其他度量（如度数）呈正相关。

在网络理论中，接近度是中心度的复杂度量。它被定义为顶点v与其可达到的所有其他顶点之间的平均测地距离（即最短路径）

${\frac {\displaystyle \sum _{t\in V\setminus v}d_{G}(v,t)}{n-1}}$

其中 $n\geq 2$ 是网络从节点 v 可达的 '连通分量' V 的大小。紧密性可以被认为是衡量信息从给定节点传播到网络中其他可达节点所需时间的一种度量。

有些人将紧密性定义为该数量的倒数，但无论哪种方式，传递的信息都是一样的（这次估计的是速度而不是时间跨度）。节点 $v$ 的紧密性 $C_{C}(v)$ 是 V 中所有其他节点到该节点的 测地距离 之和的倒数。

$C_{C}(v)={\frac {1}{\sum _{t\in V\setminus v}d_{G}(v,t)}}.$

不同的方法和算法可以被用来衡量紧密性，例如 Noh 和 Rieger（2003）提出的 随机游走中心性，它衡量随机游走消息从网络中的其他地方到达一个节点的速度——一种随机游走版本的中心性。

Stephenson 和 Zelen（1989）的 信息中心性 是另一个紧密性度量，它与 Noh 和 Rieger 的度量有一些相似之处。本质上，它衡量的是以节点 i 为终点的路径的调和平均长度，如果 i 有很多连接到其他节点的短路径，则该值会更小。

Dangalchev（2006）为了衡量网络脆弱性，修改了紧密性的定义，使其适用于非连通图，并且总的紧密性更容易计算。

$C_{C}(v)=\sum _{t\in V\setminus v}2^{-d_{G}(v,t)}.$

Opsahl（2010）提出了一个扩展，用于具有非连通分量的网络。

特征向量中心性

特征向量中心性是衡量网络中 节点 重要性的一个度量。它根据连接到高得分节点比连接到低得分节点对节点分数的贡献更大这一原则，为网络中的所有节点分配相对得分。w:Google 的 w:PageRank 是特征向量中心性度量的变体。

使用邻接矩阵查找特征向量中心性

令 $x_{i}$ 表示第 $i^{th}$ 个节点的分数。令 $A_{i,j}$ 是网络的 w:邻接矩阵。因此，如果第 $i^{th}$ 个节点与第 $j^{th}$ 个节点相邻，则 $A_{i,j}=1$，否则 $A_{i,j}=0$。更一般地说，A 中的条目可以是表示连接强度的实数，如 w:随机矩阵 中的条目。

对于第 $i^{th}$ 个节点，令其中心度得分与其所有连接节点的得分之和成正比。因此

$x_{i}={\frac {1}{\lambda }}\sum _{j\in M(i)}x_{j}={\frac {1}{\lambda }}\sum _{j=1}^{N}A_{i,j}x_{j}$

其中 $M(i)$ 是连接到第 $i^{th}$ 个节点的所有节点的集合，N 是节点总数，$\lambda$ 是一个常数。用向量表示法可以改写为

$\mathbf {x} ={\frac {1}{\lambda }}\mathbf {Ax}$，或作为 w:特征向量 方程 $\mathbf {Ax} ={\lambda }\mathbf {x}$

通常，会有许多不同的 w:特征值 $\lambda$ 存在特征向量解。然而，特征向量所有元素都为正的附加要求意味着（根据 w:佩龙-弗罗贝尼乌斯定理）只有最大的特征值才会产生所需的中心度度量。 然后，相关特征向量的第 $i^{th}$ 个分量就给出网络中第 $i^{th}$ 个节点的中心度得分。 w:幂迭代 是许多用于寻找此主导特征向量的 w:特征值算法 之一。

另见

• 图中的距离

进一步阅读

• Freeman, L. C. (1979). 社会网络中的中心性：概念澄清。社会网络，1(3), 215-239.
• Sabidussi, G. (1966). 图的中心性指标。心理测量学，31 (4), 581-603.
• Freeman, L. C. (1977) 一套基于介数的中心性指标。社会计量学 40, 35-41.
• Koschützki, D.; Lehmann, K. A.; Peeters, L.; Richter, S.; Tenfelde-Podehl, D. 和 Zlotowski, O. (2005) 中心性指标。在 Brandes, U. 和 Erlebach, T. (Eds.) 网络分析：方法论基础, pp. 16–61, LNCS 3418, Springer-Verlag.
• Bonacich, P.(1987) 权力和中心性：一组指标，美国社会学杂志，92 (5), pp 1170–1182

外部链接

• https://networkx.lanl.gov/trac/attachment/ticket/119/page_rank.py
• http://www.faculty.ucr.edu/~hanneman/nettext/C10_Centrality.html