中心性

在图论和网络分析中，中心性指标可确定图中的最重要节点。 其应用包括识别社交网络中最有影响力的人，互联网或城市网络中的关键基础设施节点以及疾病的超级传播者。 中心性概念最早发展起源于社交网络分析中，许多用于衡量中心性的术语反映了它们的社会学渊源。 研究者请勿将中心性指标与节点影响度混淆，后者的作用是量化网络中每个节点的影响。

中心度指标的定义和描述

中心度指标用于回答“那些因素刻画重要节点”。图中节点的实值函数可以给出答案，其中函数值会根据节点的重要性给出排名。

“重要性”一词具有多种含义，以致于产生了许多不同的“中心性”定义。 目前已提出两种分类方案。 可以根据网络中的流或传输类型来定义“重要性”。 这样就可以根据流类型的重要性对中心性进行分类。 或者，“重要性”可以被认为是参与网络的密集程度。 这样就可以根据衡量中心度内聚的方式对其进行分类。这两种方法将中心性划分为不同的类别。 进一步的结论是，适用于一个类别的中心性在应用于另一类别时通常会“出错”。

当通过集聚程度对中心进行分类时，很明显，大多数中心都属于一种类别。 从给定节点开始计数的步数仅与如何定义路程和计数上有所不同。 对该群体的限制考虑可以进行软性表征，从而将中心点放在从长度为1的步长（度中心）到无限步长（特征值中心点）的频谱上。大量中心度都具有这种家族关系的现象也许可以解释这些指数之间的高度相关性。

基于网络流描述

网络可以看作是某种事物流经路径的描述。 这允许基于流的类型和由中心点编织的路径类型进行表征。 流可以基于转移，其中每个不可分割的物体都从一个节点到达另一个节点，例如从交货地点到客户家的包裹递送。 第二种情况是串行复制，其中复制一个项目，以便源和目标都有它。 一个示例是通过八卦信息的传播，其中信息以私有方式传播，并且在过程结束时通知源节点和目标节点。 最后一种情况是并行复制，将项目同时复制给几个链接，例如无线电广播可以一次向许多听众提供相同的信息。

类似地，可将路径类型限制为测地线（最短路径），路径（不多次访问顶点），路径（可以多次访问顶点，不对边缘进行多次遍历）或步行（顶点和路径） 可以多次访问/遍历边缘）。

基于路径结构描述

可以从中心性的构建方式中得出另一种分类。 这又分为两类： 中心可以是径向的或中间的。 径向中心点计算从给定节点开始/结束的走行。 度中心和特征值中心是径向中心的粒子，它计算长度为1或长度为无穷的步数。 中间中心点计数通过给定顶点的走动。 典型的例子是弗里曼的中间性中心度，即通过给定顶点的最短路径的数量。

类似的，计数可以获取步行的数量或长度。 数量是给定类型的步行总数。 上一段中的三个示例属于此类。 长度刻画从给定节点到图形中其余节点的距离。 弗里曼的接近中心性是最有名的例子，即从给定节点到所有其他节点的总测地距离。 请注意，此分类与计算的步行类型（即步行，步道，路径，测地线）无关。

Borgatti和Everett提出，这种分类学提供了关于如何最好地比较中心度度量的见解。 在2×2分类中，放置同一框中的中心点足够相似作合理地选择； 一个人可以合理地比较哪个对给定的应用更好。 但是，来自不同盒子的度量分类是不同的。 相对适合度的任何评估只能在预先确定哪个类别更适用的情况下进行，从而比较变得毫无意义。

一定范围上的半径-体积中心性

路径结构的特征表明，广泛使用的中心度指标基本都是“由半径推体积”式的测量。 这些径向度量解释了一种观点，即顶点的中心性就是其关联顶点的中心性的函数。 中心性在如何定义关联方面将自身与其他测度方法区别开来。

Bonacich证明，如果按照步行来定义关联，则可以根据所考虑的步行时间来定义一系列中心性。度中心点计算长度为1的步长，而特征值中心点计算长度为无穷大。 关联的替代定义也是合理的。 Alpha中心性允许节点具有外部影响力。 Estrada的子图中心性仅建议计算闭合路径（三角形，正方形等）。

此类度量的核心是，图形邻接矩阵的幂给出了这个幂的长度游程数。 类似地，矩阵指数也与给定长度的步数密切相关。 邻接矩阵的初始转换允许对计数的步行类型进行不同的定义。 任何一种方法，

[math]\displaystyle{ \sum_{k=0}^\infty A_{R}^{k} \beta^k }[/math]

对于矩阵的幂或者

[math]\displaystyle{ \sum_{k=0}^\infty \frac{(A_R \beta)^k}{k!} }[/math]

矩阵指数, 其中

• [math]\displaystyle{ k }[/math] 是步长,
• [math]\displaystyle{ A_{R} }[/math]是变换后的邻接矩阵，并且
• [math]\displaystyle{ \beta }[/math]是保证总和收敛的折扣参数。

Bonacich的度量系列不会转换邻接矩阵。 Alpha中心性用其解析物替换了邻接矩阵。 子图的中心性用其迹替换邻接矩阵。 令人吃惊的结论是，不管邻接矩阵的初始转换如何，所有这些方法都具有共同的限制行为。 当接近零时，指标数收敛到度中心。 随着接近其最大值，指标数收敛到特征值中心。

博弈理论的中心性

大多数上述标准度量的共同特征是，它们仅通过关注节点自身扮演的角色来评估节点的重要性。 但是，在许多应用中，这种方法是不够的，因为如果成组地考虑节点的功能，可能会产生协同作用。

例如，考虑阻止流感的问题。从上面的网络图像来看，我们应该接种哪些节点？基于先前描述的措施，我们希望识别在疾病传播中最重要的节点。仅基于中心性的方法（专注于节点的各个功能）可能不是一个好方法。红方框中的节点无法单独阻止疾病传播，但是将它们作为一个整体来看，我们清楚地看到，如果节点[math]\displaystyle{ v_ {1} }[/math]， [math]\displaystyle{ v_{4} }[/math]和[math]\displaystyle{ v_ {5} }[/math]。博弈论中心试图使用博弈论中的工具来指导所描述的问题和几率。文献中提出的方法使用Shapley值。由于Shapley值计算的时间复杂性很强，因此在该领域中的大多数努力都被驱使用来实施新的算法和方法，这些算法和方法依赖于网络的特殊拓扑或问题的特殊特征。这样的方法可以导致将时间复杂度从指数减小到多项式。

重要局限

中心指数有两个重要的局限性，一个是明显的，另一个是隐含的。 明显的局限性是，一种应用而言的最佳中心性通常对于另一应用不是最佳的。 确实，如果不是这样，我们将不需要那么多不同的中心。 Krackhardt风筝图提供了这种现象的说明，针对该现象，三个不同的中心性概念给出了最中心顶点的三个不同选择。

更为隐含的限制是节点中心性与节点的相对重要性这一普遍存在的谬误。 经过明确设计，中心度指标可以产生等级，从而可以指示最重要的节点。 他们在刚刚提到的限制结果很好。 通常，它们并不是为了衡量节点的影响而设计的。 最近，网络物理学家已经开始发展节点影响度量来解决此问题。

有两重错误。 首先，排名仅按重要性对节点进行排序，它无法量化排名不同级别的节点之间的重要性差异。 可以通过将Freeman集中化应用于所讨论的集中度度量来缓解这种问题，该集中度度量取决于节点的集中化分数的差异，从而为节点的重要性提供一些信息。 此外，通过Freeman集中化，人们可以通过比较最高集中度分数来比较多个网络。 但是，这种方法在实践中很少见。

其次，正确标识给定网络应用中最重要节点的功能不一定会推广到其余节点。 对于其他大多数网络节点，排名可能毫无意义。 例如，这解释了为什么仅前几个Google图片搜索结果顺序合理。 Pagerank是一种高度不稳定的度量，显示在对Jump参数进行较小调整后频繁发生的排名反转。

虽然中心性指标无法推广到网络的其余部分，乍一看似乎是反直觉的，但它直接来自上述定义。 复杂的网络具有异构拓扑。 在某种程度上，最佳度量取决于最重要节点的网络结构，对于此类节点而言，它的最优度量对于网络的其余部分而言并非最佳。

点度中心性

历史上第一个概念上简单的中心性定义是点度中心性，定义为与节点直接相连的连边（例如，一个节点有的边的数目）。度可以理解为节点接触到在任何在网络中传播的事物（比如病毒或者信息）的可能性。在有向图中（连边具有方向性），我们经常定义两种不同的度中心测量：指向和指出。相应的，指向的定义为方向指向节点的连边数，指出的定义为节点指出方向的连边数。 当连边与友谊或者合作相关时，指向的度中心常被解释为赶潮流，指出被解释为交际。对于有[math]\displaystyle{ |V| }[/math]个节点[math]\displaystyle{ |E| }[/math]条边的图[math]\displaystyle{ G:=(V,E) }[/math]，节点[math]\displaystyle{ v }[/math]的度中心定义为，

[math]\displaystyle{ {\displaystyle C_{D(v)}= \deg(v)} }[/math]

计算图中所有节点的度中心，在密邻接矩阵表象中需要 [math]\displaystyle{ \Theta(V^2) }[/math], 在稀疏矩阵表象中，连边需要[math]\displaystyle{ \Theta(E) }[/math] 。

节点层面中心性的定义可以推广到整个图上，即我们说的“图中心”。 另[math]\displaystyle{ v{^*} }[/math] 表示图 [math]\displaystyle{ G }[/math]中度中心最大的点。 另 [math]\displaystyle{ X:=(Y,Z) }[/math] 为[math]\displaystyle{ |Y| }[/math]-与图连接使得接下来的量最大的节点([math]\displaystyle{ y* }[/math] 是图[math]\displaystyle{ X }[/math]中心度最大的点):

[math]\displaystyle{ H= \sum^{|Y|}_{j=1} [C_D(y*)-C_D(y_j)] }[/math]

对应的，图 [math]\displaystyle{ G }[/math]的度中心如下:

[math]\displaystyle{ {\displaystyle C_D(G)= \frac{\sum^{|V|}_{i=1} [C_D(v{^*})-C_D(v_i)]}{H}} }[/math]

当图[math]\displaystyle{ X }[/math]包含一个与其他节点都相连的中心点 (星图)时 [math]\displaystyle{ H }[/math]的值最大, 此时

[math]\displaystyle{ H=(n-1)\cdot((n-1)-1)=n^2-3n+2. }[/math]

所以对于任意图 [math]\displaystyle{ {\displaystyle G:=(V,E)} }[/math],

[math]\displaystyle{ C_D(G)= \frac{\sum^{|V|}_{i=1} [C_D(v*)-C_D(v_i)] }{|V|^2-3|V|+2} }[/math]

接近中心度

在一个连接图中，节点的归一化的接近中心性（或者接近）是节点与其他图中节点之间的最短路径的平均长度。因此，一个可能成为中心的节点与其他的节点连接更近。

接近被Alex Bavelas (1950) 定义为距离远的程度的倒数，即: [math]\displaystyle{ {C(x)={\frac {1}{\sum _{y}d(y,x)}}} }[/math]

其中 [math]\displaystyle{ {\displaystyle d(y,x)} }[/math]是x和y之间的距离。但是，但提到接近中心时，人们常指的是归一化形式的，通常是上一个公式乘上1/N，N为图中的节点数。这样处理后可以使得不同大小的图的比较有意义。

在无向图中讨论节点之间指向或者指出的距离是无关紧要的，因为这会导致有向图中不一样的结果（例如，一个网站的指出链接的接近中心性很高，但是指向外部链接的接近中心很低）。

和谐中心度

在一个图中（不一定是连接图），和谐中心度定义为接近中心度倒数和求和运算的拟运算

[math]\displaystyle{ {\displaystyle H(x)=\sum _{y\neq x}{\frac {1}{d(y,x)}}} }[/math] 其中 [math]\displaystyle{ {\displaystyle 1/d(y,x)=0} }[/math]如果没有路径从y到x。和谐中心度可以通过除以N-1归一化，其中N是图中的节点数。

和谐中心度是Marchiori 和 Latora (2000)提出的，随后 Dekker (2005)取名为“价值中心度” （"valued centrality"）， Rochat (2009)也提出过类似的概念.

中介中心性/中间中心性

Betweenness is a centrality measure of a vertex within a graph (there is also edge betweenness, which is not discussed here). Betweenness centrality quantifies the number of times a node acts as a bridge along the shortest path between two other nodes. It was introduced as a measure for quantifying the control of a human on the communication between other humans in a social network by Linton Freeman[21] In his conception, vertices that have a high probability to occur on a randomly chosen shortest path between two randomly chosen vertices have a high betweenness.

The betweenness of a vertex v v in a graph G

=

( V , E ) G:=(V,E) with V V vertices is computed as follows:

For each pair of vertices (s,t), compute the shortest paths between them. For each pair of vertices (s,t), determine the fraction of shortest paths that pass through the vertex in question (here, vertex v). Sum this fraction over all pairs of vertices (s,t). More compactly the betweenness can be represented as:[22]

C B ( v ) = ∑ s ≠ v ≠ t ∈ V σ s t ( v ) σ s t C_B(v)= \sum_{s \neq v \neq t \in V}\frac{\sigma_{st}(v)}{\sigma_{st}} where σ s t \sigma_{st} is total number of shortest paths from node s s to node t t and σ s t ( v ) \sigma_{st}(v) is the number of those paths that pass through v v. The betweenness may be normalised by dividing through the number of pairs of vertices not including v, which for directed graphs is ( n − 1 ) ( n − 2 ) (n-1)(n-2) and for undirected graphs is ( n − 1 ) ( n − 2 ) / 2 (n-1)(n-2)/2. For example, in an undirected star graph, the center vertex (which is contained in every possible shortest path) would have a betweenness of ( n − 1 ) ( n − 2 ) / 2 (n-1)(n-2)/2 (1, if normalised) while the leaves (which are contained in no shortest paths) would have a betweenness of 0.

From a calculation aspect, both betweenness and closeness centralities of all vertices in a graph involve calculating the shortest paths between all pairs of vertices on a graph, which requires O ( V 3 ) {\displaystyle O(V^{3})} time with the Floyd–Warshall algorithm. However, on sparse graphs, Johnson's algorithm may be more efficient, taking O ( V 2 log ⁡ V + V E ) O(V^2 \log V + V E) time. In the case of unweighted graphs the calculations can be done with Brandes' algorithm[22] which takes O ( V E ) O(V E) time. Normally, these algorithms assume that graphs are undirected and connected with the allowance of loops and multiple edges. When specifically dealing with network graphs, often graphs are without loops or multiple edges to maintain simple relationships (where edges represent connections between two people or vertices). In this case, using Brandes' algorithm will divide final centrality scores by 2 to account for each shortest path being counted twice.[22]