介数中心性

在图论中，介数中心性（英語：betweenness centrality，又译作中间中心性）是基于最短路径针对网络图中心性的衡量标准之一。针对全连接网络图，其中任意两个节点均至少存在一个最短路径，在无权重网络图中该最短路径是路径包含边的数量求和，加权网络图中该最短路径则是路径包含边的权重求和。每个节点的介数中心性即为这些最短路径穿过该节点的次数。

介数中心性在网络理论中有广泛的应用：它代表了某节点与其他节点之间的互动程度。 例如，在通信网络中，一个有更高介数中心性的节点在网络中有更强的控制能力，因为更多的信息传递时将通过该节点。 介数中心性被用作为对中心性的一种常见测量方式:[1] 它适用于解决网络理论中的许多问题，包括与社会网络、生物、运输和科学合作等方面相关的问题。

虽然早期的研究人员曾直观地描述了介数的中心性，但Freeman在1977年给了第一个介数中心性的正式定义。

节点 v {\displaystyle v} 的介数中心性可表达为以下公式：

其中 σ s t {\displaystyle \sigma _{st}} 是节点 s {\displaystyle s} 到节点 t {\displaystyle t} 的最短路径之數量，而 σ s t ( v ) {\displaystyle \sigma _{st}(v)} 这些路径经过 v {\displaystyle v} 的次数。

可注意到一个节点的介数中心性与该网络图中的节点个数相关。因此，可通过除以不包含 v {\displaystyle v} 的节点对数以将计算结果标准化，使得 g ∈ [ 0 , 1 ] {\displaystyle g\in [0,1]} 。其中有向图需除以 ( N − 1 ) ( N − 2 ) {\displaystyle (N-1)(N-2)} ，而无向图需除以 ( N − 1 ) ( N − 2 ) / 2 {\displaystyle (N-1)(N-2)/2} ，其中 N {\displaystyle N} 是网络图中节点数量的集合。该比例代表的是最高可能计算值，即某节点与其他所有节点都通过单一的最短路径相连接，不过以上情况通常不会发生。标准化的过程并不会使计算的精准度受到影响。

可求解得：

由公式可知，计算结果将始终是一个从较小范围到更大范围的比例，因此没有精准度的损失。

在一个加权网络中，连接节点的边不再被看作类似于二元的互相作用（有边或无边），而是根据其特征、影响、频率等赋予对应的权重，这在网络图基于的网络拓扑结构之上增加了另一个异质性的维度。 在加权网络中，一个节点的强度为其邻边权重的代数和。

其中 a i j {\displaystyle a_{ij}} 和 w i j {\displaystyle w_{ij}} 分别表示节点 i {\displaystyle i} 和 j {\displaystyle j} 之间的邻接矩阵和权重矩阵。类似于在无标度网络中发现的幂律分布，一个给定节点的强度也服从幂律分布。

一项研究表明，介数为 b {\displaystyle b} 的节点其平均值 s ( b ) {\displaystyle s(b)} 可用以下公式来近似： [2]

渗流中心性是加权介数中心性的一种特殊情况，它在计算其权重时考虑了每条最短路径的源节点与目标节点的“状态”。 在复杂网络中，许多情景都会发生“感染”并进行渗流。 例如，众所周知，在接触网络中细菌或病毒的感染可以在人群的社会网络中传播。也可以将疾病的传播抽象化，认为一个城镇或人群聚集地是由公路、铁路或航空的连接而构成的网络。计算机病毒可能通过计算机网络传播。关于商业报价和交易的传闻或新闻也可以经由人群的社交网络传播。 在所有这些情景下，一个“感染”可在复杂网络中通过连接传播，并伴随着节点“状态”的改变，如受到感染或感染后恢复到原状态。例如，在一个流行病的情景下，个体在感染传播时会将状态由“易感染”变为“已感染”。 在上述例子中，各个节点在传播时可能的状态可以是二元的（已受到/未受到感染）、离散的（易感染/已感染/已恢复）乃至连续的（如城镇中受感染者的比例）。 在所有这些情景中，常见的特征是传染病的传播使网络中节点状态发生变化。 以上这些有关渗流中心性(PC)的概念由Piraveenan et al.提出，这对具体地测量节点在网络渗透中的重要性很有帮助。[3]

渗流中心性的定义是：给定一个节点，在给定的时间内“渗透路径”通过该节点的比例。“渗透路径”指的一对节点之间的最短路径，其中源节点产生渗透效果(例如传播感染)，目标节点可以是处于已渗透、未渗透或部分渗透的状态。

其中 σ s r {\displaystyle \sigma _{sr}} 是从节点 s {\displaystyle s} 到节点 r {\displaystyle r} 最短路径数之和， σ s r ( v ) {\displaystyle \sigma _{sr}(v)} 这些路径中通过 v {\displaystyle v} 的次数。 节点 i {\displaystyle i} 在时间 t {\displaystyle t} 的渗流状态由 x t i {\displaystyle {x^{t}}_{i}} 决定，其中有两个临界值， x t i = 0 {\displaystyle {x^{t}}_{i}=0} 时表示在时间 t {\displaystyle t} 的时候没有渗透状态， x t i = 1 {\displaystyle {x^{t}}_{i}=1} 时表示在时间 t {\displaystyle t} 的时候为完全渗流状态。0到1之间的值则表示部分渗透状态（例如，在一个城镇网络中，这表示城镇受感染人群的百分比）。

渗流路径的权重取决于源节点的渗流水平，如果源节点的渗流水平越高，那么来自该节点的路径影响力更大。 因此在源节点为高渗透作用节点的最短路径上的节点更有可能受到渗流影响。渗流中心性的定义还可以扩展到也包括目标节点的权重。 渗流中心性的计算可采用Brandes快速算法有效实现，其时间复杂度为 O ( N M ) {\displaystyle O(NM)} 。如果计算需要考虑目标节点的权重，最坏情况的时间复杂度为 O ( N 3 ) {\displaystyle O(N^{3})} 。

在一个网络图中，计算所有节点的介数中心性和接近中心性需要涉及到计算图中所有节点对的最短路径。如果使用改进的弗洛伊德算法需要花费 Θ ( | V | 3 ) {\displaystyle \Theta (|V|^{3})} 的时间，其中需将两点间的最短路径修改为图中所有节点对之间的最短路径。 在稀疏网络图中，约翰逊算法或布兰德斯算法效率更高，都需要花费 O ( | V | 2 log ⁡ | V | + | V | | E | ) {\displaystyle O(|V|^{2}\log |V|+|V||E|)} 的时间。 在无权重网络图中，用布兰德斯的算法计算介数中心性需要花费 O ( | V | | E | ) {\displaystyle O(|V||E|)} 的时间。[4]

计算一个网络图所有节点的介数中心性和接近中心性时，图是无向的且可以由环形边（节点自己连自己）或重复边（两个节点多条边）连接组成的。当专门处理网络图时，通常网络图是没有环形边或重复边而只有简单的关系（其中边表示两个节点之间的连接）在这种情况下，使用布兰德斯算法计算时需要将最终结果除以2，因为每个最短路径都被计算了两次。[5]

另一个算法通过引入超参数来控制探索与利用之间的平衡，从而涵盖了可计算测地线的Freeman介数与可计算所有路径的Newman介数。其时间复杂度为网络图中边的数量乘上节点的数量。[6]

中心性的概念也被扩展到评定一个团队的级别。[7] 团队介数中心性表示通过一组节点连接非该组节点的测地线的比例。能计算所有节点介数中心性的布兰德斯算法被修改为计算一组具有相同渐近运行时间的节点的团队介数中心性。[7]

介数中心性与网络的连接度相关，介数高的节点如果在被移除以后有很大可能性使网络图不完全连接。

路由介数中心性使介数中心性适用于任何循环较少的简单路径定义方案而不局限于最短路径标准。