第 03 章精校翻译：网络中心性指标
第 3 章 网络中心性指标（Network Centrality Indices）
网络分析中一个自然的问题是：“网络中哪些节点最重要？”一个节点可以在多个方面是重要的。例如，在社交网络中，一个节点可以与许多社会群体都有良好的连接，或者可以促进网络中的信息流动。在信息网络中，一个节点可以提供指向重要信息源的链接，或者充当参考节点。在基础设施网络中，一个节点可能对维持网络良好的拓扑结构至关重要。
节点的重要性可以用一个定义在网络节点上的实值函数来刻画。该函数的取值指示节点的重要程度，并可用于排序。这样的函数称为网络中心性指标（network centrality indices）或网络中心性度量（network centrality measures）。1 由上一段已经可以清楚看出，不同的重要性标准可能导致截然不同的中心性指标定义。因此，我们首先综述各种现有的中心性指标，然后讨论它们之间的关系以及若干应用。除节点的中心性指标外，也存在针对网络边的中心性指标。尽管我们的主要关注点将是节点的中心性指标，我们也会提及一些边的中心性指标。到目前为止，人们已经提出了许多中心性指标，而且这个列表还在不断增长。我们试图概览其中重要的、彼此有区分度的情形。
3.1 中心性指标总览（Overview of Centrality Indices）
在本节中，我们把各种中心性指标的定义划分为若干组。我们承认，所提出的分类并非唯一可能的分类，有些中心性指标可以被归入不止一个组。我们将尽量提及可能的重新归类。
3.1.1 基于距离的中心性指标（Distance Based Centrality Indices）
这里我们描述基于节点间测地（最短路径）距离的网络中心性指标。
节点度（Node degree）
最简单的基于距离的中心性指标是节点度，即一个节点的直接邻居的数目。在有向网络的情形，我们实际上有入度（indegree） $d_v^-$（对应指向该节点的边数）与出度（outdegree） $d_v^+$（对应由该节点指出的边数）。我们注意到，入度大的节点可以解释为“权威”（authorities），而出度大的节点可以解释为“枢纽”（hubs）。在文献计量学的语境中，一篇文章的入度是引用该文章的其他文章的数目，而出度是该文章所包含的参考文献的数目。自然地，一篇公认的权威文章会有很多引用，而一篇综述文章通常会参考许多文献。
接近中心性（Closeness）
记 $d(v, u)$ 为从节点 $v$ 到节点 $u$ 的一条最短路径的长度。Bavelas, 1950 引入了接近中心性（closeness centrality）的概念。节点 $u$ 的接近中心性指标可以定义为
$$ \frac{n - 1}{\sum_v d(v, u)} . \tag{3.1} $$
接近中心性不过是从给定节点到所有其他节点的平均距离的倒数。最初，接近中心性是针对无向、连通的网络定义的。如果把它形式地推广到有向网络的情形还相当直接，那么（强）连通性的缺失就会带来问题。
调和中心性（Harmonic centrality）
为了克服不连通或弱连通网络中路径长度为无穷的问题，人们提出了调和中心性（harmonic centrality）的概念。调和中心性的思想是交换取倒数与求和这两个运算的次序（同时改变归一化方式），由此得到
$$ \frac{1}{n - 1} \sum_{v : v \neq u} \frac{1}{d(v, u)} . $$
于是，调和中心性是调和平均距离的倒数。得益于约定 $\infty^{-1} = 0$，调和平均自然地适用于不连通或弱连通的网络。调和中心性这一概念似乎最早由 Marchiori and Latora, 2000 提出，尽管有若干工作独立地提出了同一概念或其变体、推广（Dekker, 2005；Cohen and Kaplan, 2007；Rochat, 2009；Pan and Saramäki, 2011）。
比较（Comparison）。 我们在同一个图上计算上述三个中心性指标（见图 3.1）。当然，节点度中心性只对度大的节点取值较大，而在所选图中这些节点位于左下方。相反，接近中心性把重要性赋予位于两个簇交界处的节点。调和中心性则似乎混合了两者，因为度大的节点以及位于交界处的节点都具有较大的调和中心性值。
3.1.2 谱中心性指标（Spectral Centrality Indices）
谱中心性指标（spectral centrality indices）是可以作为某个特征值问题
$$ x M = \lambda x , \tag{3.2} $$
的解而得到的指标，其中 $x$ 是一个行向量。之所以用行向量来运算，其原因将从随后的分析中看清。
邻接谱中心性（Adjacency spectral centrality）
这是最古老的中心性指标之一，它在国际象棋赛事评分中的应用可以追溯到 19 世纪末（Landau, 1895）。作为矩阵 $M$，我们选取图的邻接矩阵（adjacency matrix） $A$，并把与最大正特征值相关联的特征向量的各元素取作中心性指标。我们注意到，在非负矩阵理论中，这样的特征向量也称为 Perron–Frobenius 特征向量。
随机游走中心性 / Seeley 指数（Random walk centrality or Seeley's index）
Seeley, 1949 提出把邻接矩阵的各行按行和归一化。这意味着一个节点的声誉被分配给该节点的各个后继。于是，若记 $P = D^{-1} A$（其中 $D$ 是节点度构成的对角矩阵），随机游走中心性（random walk centrality，又称 Seeley 指数）由如下特征值问题的解给出：
$$ \sigma = \sigma P . \tag{3.3} $$
$\sigma$ 的各元素有两种概率解释。第一种解释是：$\sigma_i$ 是图上的随机游走（random walk）者长期停留在节点 $i$ 的时间比例。此外，由马尔可夫链理论我们知道 $E_i[T_i] = 1 / \sigma_i$，其中 $T_i$ 是返回节点 $i$ 的返回时间。于是按第二种解释，$\sigma_i$ 的倒数给出返回节点 $i$ 的期望返回时间。接着，还有两点注记。第一，如果图是无向的，此时随机游走的可逆性意味着 Seeley 指数变得与节点度成正比。第二，最初的 Seeley 指数只对强连通图有定义。如果图不是强连通的，可以作各种正则化。下一自然段将描述其中一种正则化。
PageRank
Google 的创始人 Brin and Page, 1998 提出了 PageRank 中心性指标用于对网页排序。PageRank 对网页浏览者的行为建模：允许随机游走者以概率 $c$ 沿着一条出边前进，并以互补概率 $1 - c$ 从一个均匀随机选取的网页重新开始。于是，PageRank 是该随机游走者的平稳分布，因而是如下方程组的解：
$$ \pi = c \pi P + (1 - c) \nu , \tag{3.4} $$
其中 $P = D^{-1} A$，$\nu$ 是均匀分布。事实上，代替均匀分布，也可以选取一个集中在某个特定节点集合上的分布。这就得到个性化 PageRank（Personalized PageRank），它可以度量相对于某一组节点的中心性。此时，$\nu$ 称为个性化分布（personalization distribution）。
注意，利用归一化条件 $\pi \underline{1} = 1$，我们可以把 (3.4) 改写为：
$$ \pi = \pi \big( c P + (1 - c) \underline{1} \nu \big) , $$
这就解释了为什么 PageRank 属于谱指标家族。
我们也可以把方程 (3.4) 改写为如下形式：
$$ \pi [I - c P] = (1 - c) \nu , $$
这给出 PageRank 的一个有用的显式矩阵表达：
$$ \pi = (1 - c) \nu [I - c P]^{-1} . \tag{3.5} $$
特别地，上述表达使我们可以把 Seeley 指数推广到非强连通的网络。首先考虑一种中间情形：网络由 $m$ 个强连通分量组成，每个分量由各自的转移矩阵 $P^{(i)}$（$i = 1, \dots, m$）描述。于是，利用公式 (3.5) 我们可以写出
$$ \begin{aligned} \pi &= (1 - c) \left[ \frac{n_1}{n} \frac{1}{n_1} \underline{1}^T \quad \cdots \quad \frac{n_m}{n} \frac{1}{n_m} \underline{1}^T \right] \begin{bmatrix} [I - c P^{(1)}]^{-1} & & \\ & \ddots & \\ & & [I - c P^{(m)}]^{-1} \end{bmatrix} \\ &= \left[ \frac{n_1}{n} \pi^{(1)} \quad \cdots \quad \frac{n_m}{n} \pi^{(m)} \right] , \end{aligned} $$
其中各向量 $\underline{1}$ 取相应维数，且
$$ \pi^{(i)} = (1 - c) \frac{1}{n_i} \underline{1}^T [I - c P^{(i)}]^{-1} $$
是分量 $i$ 的 PageRank。
现在我们回顾马尔可夫链理论（见例如 Avrachenkov et al., 2013a；Puterman, 2014）中的如下渐近展开：
$$ [I - c P]^{-1} = \frac{1}{1 - c} \Pi + D + \mathrm{o}(1 - c) , \tag{3.6} $$
其中 $\Pi$ 是遍历投影（ergodic projection），$D$ 是偏差矩阵（deviation matrix），这两个量由下式给出
$$ \Pi = \lim_{T \to \infty} \frac{1}{T + 1} \sum_{t = 0}^{T} P^t , \qquad D = [I - P + \Pi]^{-1} - \Pi . $$
现在，如果一个分量是强连通的，我们有
$$ \Pi^{(i)} = \underline{1} \sigma^{(i)} , $$
其中 $\sigma^{(i)}$ 是分量 $i$ 上随机游走者的平稳分布，即
$$ \sigma^{(i)} = \sigma^{(i)} P^{(i)} , \quad \sigma^{(i)} \underline{1} = 1 . $$
于是，由 (3.6) 可得
$$ \pi^{(i)}(c) \to \sigma^{(i)} \quad \text{当} \quad c \to 1 , $$
而把 Seeley 指数推广到若干强连通分量[校勘]情形的一种自然方式是
$$ \sigma = \left[ \frac{n_1}{n} \sigma^{(1)} \quad \cdots \quad \frac{n_m}{n} \sigma^{(m)} \right] , \tag{3.7} $$
其中 $\sigma^{(i)}$ 是分量 $i$ 上的平稳分布，亦即 Seeley 指数。我们看到，在这样的推广中，一个分量的相对重要性正比于它的规模，这看起来相当公平。特别地，这一推广意味着：在一个大的分量中拥有较大的“局部”中心性是更有利的。
弱连通分量的情形在 Avrachenkov et al., 2008b 中处理。
节点相关续走概率的 PageRank（原文 PageRank with node-dependent restart probability）
PageRank 的一种自然推广基于带重启的随机游走，其中沿链接继续游走的概率依赖于节点。具体地，设随机游走从节点 $i \in V$ 出发时，以概率 $c(i)$ 沿出边继续游走，以概率 $1-c(i)$ 按分布 $\nu$ 重启。[校勘]为方便起见，定义 $C$ 为把各 $c(i)$ 放在对角线相应位置上的对角矩阵。于是，带节点相关重启的随机游走可以用如下转移概率矩阵描述：
$$ \tilde{P} = C D^{-1} A + (I - C) \underline{1} \nu . \tag{3.8} $$
Avrachenkov et al., 2014a 提出了带节点相关重启的个性化 PageRank 的两种推广：
(i) 占用时间型个性化 PageRank（Occupation-Time Personalized PageRank，OT-PPR）定义为
$$ \pi_j(\nu) = \lim_{t \to \infty} P_\nu [X_t = j] . \tag{3.9} $$
由于 $\pi(\nu)$ 是该马尔可夫链的平稳分布，我们可以把 $\pi_j(\nu)$ 解释为对节点 $j$ 的访问的长期频率，即
$$ \pi_j(\nu) = \lim_{t \to \infty} \frac{1}{t} \sum_{s = 1}^{t} 1\{X_s = j\} . $$
(ii) 重启位置型个性化 PageRank（Location-of-Restart Personalized PageRank，LR-PPR）定义为
$$ \begin{aligned} \rho_j(\nu) &= \lim_{t \to \infty} P_\nu [X_t = j \text{ 且恰好位于重启之前}] \\ &= \lim_{t \to \infty} P_\nu [X_t = j \mid \text{时刻 } t + 1 \text{ 发生重启}] . \end{aligned} \tag{3.10} $$
我们可以把 $\rho_j(\nu)$ 解释为对节点 $j$ 的、且紧随其后立即发生一次重启的访问的长期频率，即
$$ \rho_j(\nu) = \lim_{t \to \infty} \frac{1}{N_t} \sum_{s = 1}^{t} 1\{X_t = j,\; X_{t+1} \text{ 重启}\} , $$
其中 $N_t$ 表示到时刻 $t$ 为止的重启次数。
在 Avrachenkov et al., 2014a 中，针对占用时间型个性化 PageRank 给出了如下显式矩阵公式
$$ \pi(\nu) = \frac{1}{\nu [I - C P]^{-1} \underline{1}} \, \nu [I - C P]^{-1} , \tag{3.11} $$
其中 $P = D^{-1} A$；针对重启位置型个性化 PageRank 给出
$$ \rho(\nu) = \nu [I - C P]^{-1} [I - C] . \tag{3.12} $$
我们看到，公式 (3.11) 确实是 (3.5) 的推广。
为简洁起见，记 $\pi_j(i) = \pi_j(e_i^T)$，其中 $e_i$ 是标准基的第 $i$ 个向量，于是 $\pi_j(i)$ 表示从 $i$ 的视角看节点 $j$ 的重要性。类似地，$\pi_i(j)$ 表示从 $j$ 的视角看节点 $i$ 的重要性。在无向图的情形，这些“direct”（正向）与“reverse”（反向）的 OT-PPR 之间存在一个非常有用的关系。
当 $A^T = A$ 且 $C > 0$ 时，如下关系成立
$$ \frac{d_i}{c_i K_i(C)} \pi_j(i) = \frac{d_j}{c_j K_j(C)} \pi_i(j) , \tag{3.13} $$其中
$$ K_i(C) = \frac{1}{e_i^T [I - C P]^{-1} \underline{1}} . \tag{3.14} $$注意，$K_i(A)$[校勘]可以解释为：当重启分布集中在节点 $i$ 上时，两次相继重启之间期望时间的倒数，即
$$ K_i(A)^{-1} = E_i[\# \text{ 重启前的步数}] . \tag{3.15} $$
于是，鉴于 $[I - C P]^{-1}$ 是吸收马尔可夫链的基本矩阵，表达式 (3.11) 还允许 OT-PPR 的另一种概率解释，其形式为更新方程（renewal equation）
$$ \pi_j(\nu) = \frac{E_\nu[\# \text{ 重启前对 } j \text{ 的访问次数}]}{E_\nu[\# \text{ 重启前的步数}]} . $$
特别地，如果 $c_i = c, \forall i$（标准 PageRank 的情形），我们得到“direct”与“reverse”PPR 之间的如下简单关系：
当 $A^T = A$ 且 $c_i = c, \forall i$ 时，关系 (3.13) 化简为
$$ d_i \pi_j(i) = d_j \pi_i(j) . \tag{3.16} $$ 查看学习笔记对“由 (3.13) 直接化简”这一步的补全Katz 指数（Katz's index）
Katz, 1953 提出了一个中心性指标，它显然是 PageRank 的先驱。它由公式
$$ \kappa = \underline{1}^T \sum_{t = 1}^{\infty} \beta^t A^t = \underline{1}^T \big( [I - \beta A]^{-1} - I \big) \tag{3.17} $$
给出。注意，减去单位矩阵其实并非必需，人们也常把下面的量称为 Katz 指数：
$$ \kappa = \underline{1}^T \sum_{t = 0}^{\infty} \beta^t A^t = \underline{1}^T [I - \beta A]^{-1} . \tag{3.18} $$
为使两个版本都有定义，折扣参数 $\beta$ 不应超过 Perron–Frobenius 特征值的倒数 $\lambda^{-1}(A)$。
与 PageRank 的主要区别在于，Katz 中心性不按出度摊薄权重，而对出边所指向的每个邻居节点都计入完整权重（原文称 full endorsement）。人们注意到，在某些社交网络中这可能是合适的——在那里，一个成员对另一个成员的引荐承载着重大的分量。
Vigna, 2016 注意到，利用 Brauer, 1952 关于特征值位移的定理，Katz 指数可以表示为一个特征值问题的解：
$$ \kappa = \kappa \big( \beta \lambda(A) A + (1 - \beta \lambda(A)) r \underline{1}^T \big) , $$
其中 $r$ 是 $A$ 的右主特征向量，满足 $\underline{1}^T r = \lambda(A)$。这验证了把 Katz 指数归类为谱中心性指标是合理的。
HITS 中心性指数（HITS centrality index）
由 Kleinberg, 1999 引入的 HITS 实际上提供了两个中心性指标。第一个中心性指标把节点排为权威（authorities），第二个中心性指标把节点排为枢纽（hubs）。Kleinberg, 1999 提出，一个好的“权威”节点被许多好的“枢纽”指向，而反过来，一个好的“枢纽”指向好的“权威”节点。这一文字表述可以用如下迭代过程表示：
$$ h^{(k + 1)} = a^{(k)} A^T , $$
$$ a^{(k + 1)} = h^{(k + 1)} A , $$
其中 $A$ 是邻接矩阵。在极限中，权威指数是
$$ a = a A^T A $$
的解。因此，按本书的行向量约定，指数 $a$ 是 $A^T A$ 的左主特征向量；把 $a$ 转置为列向量后，它是与 $A$ 的最大奇异值相关联的右奇异向量。类似地，把指数 $h$ 转置后，它是相应的左奇异向量。这些得分可对一般有向图通过 $A^TA$ 与 $AA^T$ 的主特征空间定义；若要得到唯一的得分方向和稳定的幂迭代极限，还需检查最大奇异值是否简单以及初值在主空间上的投影。
比较（Comparison）。 图 3.2 在同一个图上展示了四个谱中心性指标。我们观察到，邻接谱中心性把很大的权重加在图左下方的节点上，那里似乎是若干大度节点所在的区域。随机游走中心性把更多重要性赋予其他节点，同时仍侧重于度较大的节点和左下方的节点；而 PageRank 指标进一步削弱了左下方节点的重要性。事实上，正如对无向图所预期的那样，由于时间可逆性，随机游走中心性给出与节点度相同的排序（比较图 3.2b 与图 3.1a）。最后，Katz 中心性指标只把重要性赋予位于左分量中部的少数几个节点。
3.1.3 基于首中时间的中心性指标（Hitting Time Based Centrality Indices）
在社交网络的分析中，常常不仅最短路径、而且更长的路径也起作用。这种情形的一个典型例子是社交网络中的谣言或信息传播。事实上，这一现象已经反映在 PageRank 与 Katz 中心性指标的定义中——那里所有路径都被计入，但更长的路径打了折扣。网络中另一种“接近程度”的度量由随机游走者的平均首中时间（mean hitting time）给出；概率论与马尔可夫链教材中也常称平均首达时间（mean first passage time）。从节点 $i$ 到节点 $j$ 的平均首中时间由下式给出（见例如 Aldous and Fill, 2002；Meyer, 2000）：
$$ E_i[T_j] = e_i^T [I - P_{-j}]^{-1} \underline{1} , \tag{3.19} $$
其中 $e_i$ 是标准基的第 $i$ 个向量，$P_{-j}$ 是由 $P$ 删去其第 $j$ 行与第 $j$ 列所得的禁忌转移子矩阵（taboo transition submatrix）。
现在，类比于接近中心性（见 (3.1)），我们可以定义首中时间中心性：
$$ h_j = \frac{n}{\sum_i e_i^T [I - P_{-j}]^{-1} \underline{1}} = \frac{n}{\underline{1}^T [I - P_{-j}]^{-1} \underline{1}} . \tag{3.20} $$
据我们所知，表达式 (3.20) 由 White and Smyth, 2003 提出。注意，一般而言 $E_i[T_j] \neq E_j[T_i]$。因此，首中时间中心性也可以采用如下另一定义：
$$ \tilde{h}_j = \frac{n}{e_j^T \sum_i [I - P_{-i}]^{-1} \underline{1}} . \tag{3.21} $$
众所周知（见 Chandra et al., 1996；Aldous and Fill, 2002；Ellens et al., 2011），图中的有效电阻（effective resistance）与首中时间之间存在联系：
$$ r_{ij} = \frac{1}{2m} \big( E_i[T_j] + E_j[T_i] \big) , $$
其中 $m$ 是边的数目（总权重）。于是，首中时间中心性的一种自然的对称化版本由下式给出：
$$ \bar{h}_j = \frac{1}{\sum_i r_{ij}} = \frac{2m}{\sum_i \big( E_i[T_j] + E_j[T_i] \big)} . \tag{3.22} $$
使用有效电阻还有一个额外的好处：它们实际上在图上定义了一个度量（metric）。
比较（Comparison）。 图 3.3 在同一个图上展示了不同的首中时间中心性。我们观察到，由 (3.20) 定义的中心性在左下方的节点上产生较大的权重，并在右分量的节点上产生中等权重。相反，由 (3.21) 定义的中心性给左分量的节点以较小权重，而给右分量的节点以较大权重。最后，由 (3.22) 定义的中心性在连接良好的节点上产生较大权重，而在较为孤立的节点上产生较小权重。
向不连通图的推广（Extension to disconnected graph）
三个版本的首中时间中心性 (3.20)、(3.21) 与 (3.22) 只对连通图有定义。至少有两种途径可以把这种中心性概念推广到不连通或非强连通的图。第一，可以像在标准接近中心性的情形那样直接使用调和平均。第二，如 Hopcroft and Sheldon, 2008 与 Avrachenkov et al., 2018d 所建议的，可以使用带重启的随机游走。与 PageRank 类似，考虑以概率 $c$ 沿边续走、以概率 $1-c$ 重启的随机游走。于是，从节点 $i$ 到节点 $j$ 的带重启期望首中时间由下式给出：
$$ E_i[T_j^c] = \frac{e_i^T [I - c P_{-j}]^{-1} \underline{1}}{1 - (1 - c) \frac{1}{n} \underline{1}^T [I - c P_{-j}]^{-1} \underline{1}} . $$
上述表达式的分子提供了比分母更为显著的贡献，尤其当参数 $c$ 接近 1 时。因此，我们建议用下面的量作为带重启的首中时间中心性：
$$ h_j^c = \frac{n}{\underline{1}^T [I - c P_{-j}]^{-1} \underline{1}} . \tag{3.23} $$
注意，即使网络是强连通的，矩阵 $[I - P_{-j}]$ 也常常病态（ill-conditioned），而因子 $c$ 的引入有助于改善问题的条件数。
3.1.4 介数中心性指标（Betweenness Centrality Indices）
如果一个节点对信息流有显著的贡献，或者充当通信的促进者，那么社交网络中的这个节点就可以被视为重要的。
最短路径介数中心性（Shortest path betweenness centrality）
Freeman, 1977 引入了基于最短路径的介数中心性（betweenness centrality）指标。设 $\sigma_{st}$ 为从节点 $s$ 到节点 $t$ 的最短路径的数目，$\sigma_{st}(v)$ 为其中经过节点 $v$ 的最短路径的数目。于是，节点 $v$ 的最短路径介数中心性定义如下：
$$ \frac{1}{(n - 1)(n - 2)} \sum_{s, t : s, t \neq v} \frac{\sigma_{st}(v)}{\sigma_{st}} . $$
如前所述，社交网络中的信息不一定沿最短路径流动。因此，若干研究者把介数中心性加以推广，以计入更长的路径。
网络流介数中心性（Network flow betweenness centrality）
在 Freeman et al., 1991 中，作者们建议使用最大流（max-flow）的概念。这一概念还允许处理加权网络。设 $w_{ij}$ 为节点 $i$ 与 $j$ 之间连接的权重（若没有连接，则权重为零）。于是，从节点 $s$ 到节点 $t$ 的一个流（flow）是定义在连接集合上的一个映射，满足如下两个约束：
- 容量约束：$\forall (i, j) \in E$，$f_{ij} \leq w_{ij}$；
- 流量守恒：$\forall v$ 使得 $v \neq s, t$：
$$ \sum_{v : (u, v) \in E} f_{uv} = \sum_{v : (v, w) \in E} f_{vw} . $$
于是，流 $f$ 的值由下式给出：
$$ |f| = \sum_{v : (s, v) \in E} f_{s, v} , $$
而最大流是可以从 $s$ 输送到 $t$ 的最大的流。它的值可以用线性规划求得，著名的最大流-最小割定理表明：最大流等于所有 $s$–$t$ 割上的最小容量。
现在，Freeman et al., 1991 定义节点 $v$ 的网络流介数中心性如下：
$$ \frac{\sum_{s, t : s, t \neq v} m_{st}(v)}{\sum_{s, t : s, t \neq v} m_{st}} , \tag{3.24} $$
其中 $m_{st}$ 是从 $s$ 到 $t$ 的最大流的值，$m_{st}(v)$ 是该流中经过节点 $v$ 的部分。
电流介数中心性（Current flow betweenness centralities）
介数中心性的又一个变体不仅基于最短路径，还使用电网络理论，由 Brandes and Fleischer, 2005 与 Newman, 2005a 提出。把一个加权图看作一个电网络，各连接的权重给出电导。假设一单位电流在节点 $s$（源）注入，并在节点 $t$（汇）流出网络。于是，利用基尔霍夫电流定律与欧姆定律，我们得到电位向量满足的如下线性方程组：
$$ L \phi = b , \quad b_v = \left\{ \begin{array}{ll} 1, & v = s, \\ -1, & v = t, \\ 0, & \text{其他}, \end{array} \right. \tag{3.25} $$
其中 $L = D - A$ 是图拉普拉斯矩阵（graph Laplacian）。由于 $L \underline{1} = 0$，电位向量只差一个可加常数。因此，不失一般性，我们可以假设汇节点的电位为零（该节点接地）。于是，其余电位值由 (3.25) 唯一确定。节点 $v$ 的吞吐量（throughput）定义为
$$ \tau_{st}(v) = \frac{1}{2} \left( - |b_v| + \sum_{w : (v, w) \in E} w_{vw} |\phi_v - \phi_w| \right) , $$
而电流介数中心性由下式给出：
$$ \frac{1}{(n - 1)(n - 2)} \sum_{s, t} \tau_{st}(v) . \tag{3.26} $$
注意，网络流介数[校勘] (3.24) 与电流介数 (3.26) 都只对强连通网络有定义。事实上，电流介数只对无向网络有定义。此外，方程组 (3.25) 常常是病态的。为改善方程组的条件数，并使其能应用于非强连通网络，我们至少可以考虑如下两种正则化。第一，与 PageRank 的情形类似，可以把方程组 (3.25) 正则化为（Avrachenkov et al., 2013b）：
$$ [D - \alpha A] \phi = b . $$
这一修改在电网络与图上随机游走两方面都有解释。特别地，这一修改意味着我们把所有电导乘以因子 $\alpha$，并以电导 $(1 - \alpha) d_v$ 把每个节点接地。电流中心性的其余方程保持不变。第二种正则化是在拉普拉斯矩阵上加一项（Avrachenkov et al., 2015）：
$$ [D - A + \beta I] \phi = b . $$
这可以解释为：我们以电导 $\beta$ 把所有节点接地，与节点度无关。于是，上述方程组有如下解：
$$ \phi = [I - D_2 P]^{-1} D_1 b , $$
其中
$$ D_1 = \mathrm{diag}\left( \frac{1}{d_v + \beta} \right) , \quad D_2 = \mathrm{diag}\left( \frac{d_v}{d_v + \beta} \right) . $$
因此，第二种正则化可以用带非均匀重启的随机游走来解释（见关于带非均匀重启概率的 PageRank 那一段）。也就是说，随机游走者从高度节点重启的频率更低。如 Avrachenkov et al., 2013b 与 Avrachenkov et al., 2015 所观察到的，两种正则化给出的排序都与原来的电流中心性相近，但计算与近似都容易得多。第一种正则化的一个优点可能是抑制了高度节点所诱导的偏差，而第二种正则化的一个优点在于：所有节点以相同方式接地，因此我们只需要对源节点做平均。
我们想指出，在介数中心性的语境下，为边定义中心性指标也是非常自然的。具体地，对于最短路径边介数中心性，我们计数经过一条边的最短路径的数目；对于基于流的边介数中心性，我们计算经过所考察边的流量。正如我们稍后将讨论的，边介数中心性对图聚类非常有用。
比较（Comparison）。 图 3.4 展示了在同一个图上算得的不同介数中心性。我们观察到，最短路径介数中心性只把重要性赋予位于左右两簇交界处的节点。确实，那些节点在最短路径中至关重要，因为它们是连接左簇节点与右簇节点的必经之地。网络流介数给连接良好的节点以更多重要性，而给较为孤立的节点以较少重要性。最后，电流介数进一步强化了这一点：电流小的节点正是位于边缘（右上或右下）、与图的其余部分连接较少的节点。
3.1.5 基于博弈论的中心性指标（Game Theory Based Centrality Indices）
定义网络中心性的又一种方式基于合作博弈论。这实际上是定义网络中心性的一种相当自然的方式，因为合作博弈论提供了基于节点对网络连通性或网络凝聚性的贡献来估计节点重要性的手段。
回顾合作博弈论的基本量是特征函数（characteristic function）$v(\cdot)$，它定义在节点的子集上，并满足性质 $v(\varnothing) = 0$。Myerson, 1977 把 Shapley, 1953 的 Shapley 值概念推广到图的情形。Myerson–Shapley 值[校勘]是满足如下两条公理的唯一分配 $Y_i(v, G)$：
- 若 $S$ 是图 $G$ 的一个连通分量，则联盟 $S$ 的成员应当在他们自己之间分配他们可获得的全部价值 $v(S)$，即
$$ \sum_{i \in S} Y_i(v, G) = v(S) ; $$
- $\forall G$，$\forall i, j \in G$，在添加或删除连接 $(i, j)$ 之后，节点 $i$ 与 $j$ 获得相等的收益变化，即
$$ Y_i(v, G) - Y_i(v, G - (i, j)) = Y_j(v, G) - Y_j(v, G - (i, j)) . $$
Myerson 分配可以用 Shapley 公式计算：
$$ Y_i(v, G) = \sum_{S \subset V \setminus \{i\}} \big( v_G(S \cup \{i\}) - v_G(S) \big) \frac{s! (n - s - 1)!}{n!} , $$
其中 $s = |S|$，$v_G(\cdot)$ 是关于连通分量以可加方式定义的特征函数。然而，一般而言，用上述公式计算是非常繁琐的。事实证明，特征函数存在一种自然的选择，可以简化 Myerson 值的计算。受 Jackson and Wolinsky, 1996；Jackson, 2010 的路径折扣特征函数启发，Mazalov and Trukhina, 2014；Mazalov et al., 2016 针对树、Avrachenkov et al., 2018a 针对一般的图提出了如下特征函数。设 $\delta \in [0, 1]$ 为折扣因子。每条连接（或直接相连）给予联盟 $S$ 价值 $\delta$。此外，参与者还从间接连接中获得价值。具体地，属于联盟 $S$ 的每条长度为 2 的简单路径给予该联盟价值 $\delta^2$，长度为 3 的简单路径给予联盟价值 $\delta^3$，依此类推。于是，联盟价值可以用如下公式表示：
$$ v(S) = a_1(G, S) \delta + a_2(G, S) \delta^2 + \cdots $$
其中 $a_k(G, S)$ 是联盟 $S$ 中长度为 $k$ 的简单路径的数目。回顾一下，简单路径是没有重复节点的路径。使用简单路径是至关重要的。在 Avrachenkov et al., 2018a 中证明了，这一特征函数导出 Myerson 值的一个便于处理的表达式：
$$ Y_i(v, G) = \frac{a_1^{(i)}(G)}{2} \delta + \frac{a_2^{(i)}(G)}{3} \delta^2 + \cdots $$
其中 $a_k^{(i)}(G)$ 是包含节点 $i$ 的长度为 $k$ 的简单路径的数目。作为中心性指标，量 $Y_i(v, G)$ 把介数中心性的某些特征与 PageRank、Katz 中心性中那样的路径折扣结合了起来。
3.2 中心性指标的公理化比较（Axiomatic Comparison of Centrality Indices）
如我们所见，中心性指标有许多变体。即使在各个类别内部——比如基于距离的指标或介数指标——也有相当多的变化。一个（在很大程度上仍未解决的）大问题是：如何比较这些中心性指标？
当然，可以在一些基准例子上数值地比较这些指标，这是一种实践中有效的途径，我们在本章第一部分已经见过这种比较的例子。一条有前景的分析途径是：提出一组自然的性质或公理，并用这些公理来检验现有的中心性指标。这一途径最初由 Boldi and Vigna, 2014 提出。让我们在此加以描述。
Boldi and Vigna, 2014 的前两条公理针对规模变化与密度变化来检验中心性指标。两个具有极端密度的强连通图的例子是：由同方向连接构成的环，以及由双向连接构成的团（clique）。
考虑由一个 $k$-团和一个有向 $p$-环组成的图 $G_{k,p}$。称一个中心性指标满足规模公理，如果对每个 $k$ 都存在 $\bar{p}_k$，使得对所有 $p \geq \bar{p}_k$，$p$-环中节点的中心性严格大于 $k$-团中节点的中心性；并且反过来，对每个 $p$ 都存在 $\bar{k}_p$，使得对所有 $k \geq \bar{k}_p$，$k$-团中节点的中心性严格[校勘]大于 $p$-环中节点的中心性。
直观地说，上述公理表明：属于一个非常大但稀疏的社区的节点，应当比属于一个稠密但很小的社区的节点更重要。
然而，下一条公理表明：如果社区规模相等，那么属于更稠密社区的节点应当更重要。
考虑由一个 $k$-团和一个有向 $p$-环组成的图 $D_{k,p}$，二者由一座双向的桥 $x \leftrightarrow y$ 相连，其中节点 $x$ 属于团，节点 $y$ 属于环。称一个中心性指标满足密度公理，如果当 $k = p$ 时，$x$ 的中心性严格大于 $y$ 的中心性。
接着，第三条公理表明：一条新增的直接连接总是提升它所指向节点的指标值，这是很自然的。
称一个中心性度量满足得分单调性公理，如果对每个图 $G$ 和每一对节点 $x$、$y$（满足从 $x$ 到 $y$ 没有连接），当我们添加一条连接 $x \to y$ 时，节点 $y$ 的中心性上升。
在下表 3.1（取自 Boldi and Vigna, 2014）中，我们总结了上述公理对最常见中心性指标的验证情况。
| 中心性指标 | 规模公理（Size） | 密度公理（Density） | 得分单调性公理（Score-monotonicity） |
|---|---|---|---|
| Degree（度） | 仅 $k$ | 是 | 是 |
| Closeness（接近中心性） | 否 | 否 | 否 |
| Harmonic（调和中心性） | 是 | 是 | 是 |
| Betweenness（介数中心性） | 仅 $p$ | 否 | 否 |
| Seeley（随机游走中心性） | 否 | 是 | 否 |
| Katz（Katz 指数） | 仅 $k$ | 是 | 是 |
| PageRank | 否 | 是 | 是 |
| HITS | 仅 $k$ | 是 | 否 |
查看学习笔记对表 3.1 代表性格子（为何接近中心性不满足规模公理等）的逐格验证补全
有趣的是，对于所选的这批中心性指标，只有调和中心性同时满足全部三条公理。考虑到这些公理的要求是多么基本、多么简单，这似乎相当令人惊讶。然而，正如应用实例将要展示的那样，我们不应立即丢弃那些不满足某些公理的中心性指标。对于那些公理未刻画的任务，它们可能仍然有用。
3.3 中心性指标的应用（Applications of Centrality Indices）
3.3.1 社交、文献计量与信息网络（Social, Bibliographic and Information Networks）
中心性指标的大多数定义源于社会学与信息网络领域。这很自然，因为中心性指标应当指明社交网络中哪些成员更重要或更有权势。让我们提及社会学中关于中心性指标的若干关键贡献（这份清单当然并不完备）：Bavelas, 1950；Bonacich, 1987；Bonacich and Lloyd, 2001；Borgatti, 2005；Brandes, 2008；Everett and Borgatti, 1999；Freeman, 1977；Freeman et al., 1991；Friedkin, 1991；Hubbell, 1965；Katz, 1953；Newman, 2005a。
在文献计量学中，引用计数不过是引文网络的入度中心性指标。（引文网络是在 Solla Price, 1965, 1976 的经典工作中引入的。）显然，引用计数有其局限。例如，考虑这样的情形：一篇优秀的原创研究文章之后跟着一篇全面的综述文章。多年之后，综述文章积累的引用数可能超过原创研究文章，而后者甚至可能被遗忘。
Chen et al., 2007 提出用 PageRank 来发现“科学瑰宝”（scientific gems）。他们按引用计数与 PageRank 两种方式对 1893 至 2003 年间 Physical Review 系列期刊上的出版物进行了排名。尽管这两个指标之间呈现出很强的正相关，仍有一些文章引用数非常有限、却具有非常高的 PageRank 得分。这些文章往往就是“科学瑰宝”。例如，一项非常重要的科学技术或概念可能在一篇文章中被提出，随后这一概念以发明者的名字命名，被许多其他文章使用，但人们不再给出具体的引用。
在 Mariani et al., 2016 的近作中，作者们论证：PageRank 能很好地识别已被公认的“科学瑰宝”，但可能错过新的里程碑式工作。他们提出了一种重标度的 PageRank，把发表时间纳入考量。
引文网络只是信息网络的一个例子。信息网络的其他著名例子包括万维网（见例如 Brin and Page, 1998；Kleinberg, 1999；Hopcroft and Sheldon, 2008）、作者引用网络（作者是节点，作者之间的引用是连接）、合著网络（文章是节点，连接表示两篇文章是否由同一位作者撰写2）、期刊引用网络，等等。例如，(Pinski and Narin, 1976；Bollen et al., 2006；Bergstrom, 2007；Bergstrom et al., 2008；González-Pereira et al., 2010) 的作者们使用中心性指标（多为谱类）对期刊排名，而 (Fiala et al., 2008；Ding et al., 2009；Yan and Ding, 2009；Fiala, 2012；West et al., 2013) 的作者们使用中心性指标对作者排名。
3.3.2 半监督学习（Semi-supervised Learning）
给数据打标注是一个费力且昂贵的过程。因此，在许多数据集中，已标注数据的数量很小，标准的监督机器学习方法要么产生大量错误，要么根本不适用。幸运的是，基于图的半监督学习（semi-supervised learning）方法在这种情形下可以提供帮助（Chapelle et al., 2006）。
基于图的半监督学习背后的主要思想是：首先在数据点上构造一个图，其中两个数据点之间的连接表示这两个点之间的强关联；然后，可以使用图上的某种相似性度量，把未标注的数据点指派到由已标注数据点所定义的各个类中。
相似性度量的一个例子由个性化 PageRank 给出，见 (Avrachenkov et al., 2012)。假设类 $k$ 由一组已标注点 $\mathcal{L}_k$ 定义。令 $\nu_k$ 为某个支撑在集合 $\mathcal{L}_k$ 上的分布（例如均匀分布）。于是，我们可以把数据点 $u$ 与类 $k$ 的相似度定义为
$$ \pi_u(k) = (1 - c) \nu_k [I - c P]^{-1} e_u , $$
其中 $P = D^{-1} A$。这样，若
$$ k = \arg \max_{k'} \pi_u(k') , $$
我们就把点 $u$ 归于类 $k$。
有兴趣的读者可以在 (Avrachenkov et al., 2019) 中找到更多节点相似性度量的例子。许多节点相似性度量与中心性指标相关。我们将在第 5 章更详细地讨论半监督学习。
3.3.3 社区检测（Community Detection）
社区检测（community detection）问题是在网络中寻找紧密结合的节点群体的问题。我们把整个第 4 章都用于这一重要主题，但现在让我们先指出中心性指标在社区检测问题中的若干应用。
介数中心性指标在求解社区检测问题时非常高效。具体地，在 (Newman and Girvan, 2004) 与 (Newman, 2005a) 中，删除边介数中心性值最大的边，然后重新计算介数中心性，再删除介数中心性值最大的边，依此类推。这一过程最终会导致彼此不连通的若干分量。
(Avrachenkov et al., 2008a) 的作者们提出：先借助 PageRank 找到能很好地代表各社区的中心节点，然后像在半监督学习中那样，用个性化 PageRank 把节点指派到各社区。
个性化 PageRank 与其他中心性指标也被应用于局部图聚类（local graph clustering）：Orponen and Schaeffer, 2005；Andersen et al., 2006；Zhu et al., 2013；Orecchia and Zhu, 2014；Gleich and Mahoney, 2014。这显然与基于图的半监督学习相关。
3.3.4 更多应用（Further Applications）
从历史上看，中心性指标的首次应用是在体育领域，特别是在国际象棋中（Landau, 1895），随后在该领域又有许多其他应用，仅举几例（Wei, 1952；Kendall, 1955；Keener, 1993；Callaghan et al., 2007；Langville and Meyer, 2012）。
中心性指标在网络鲁棒性分析中扮演重要角色（Albert et al., 2000；Holme et al., 2002；Ellens et al., 2011；Rueda et al., 2017；Ofori-Boateng et al., 2021）。特别地，Clemente and Cornaro, 2020 提出了新的中心性指标，从节点与边对网络脆弱性的影响来刻画它们。
许多推荐系统使用中心性指标，特别是基于随机游走的中心性指标：Fouss et al., 2007；Gori et al., 2007；Boldi et al., 2008；Mei et al., 2008；Fouss et al., 2012；Davoodi et al., 2013。
中心性指标还用于各种 NLP 任务，如语义相似度（Sinha and Mihalcea, 2007）、词义消歧（Agirre and Soroa, 2009）与人名消歧（Smirnova et al., 2010）。
进一步阅读（Further Notes）
除 Boldi and Vigna, 2014 的工作外，还有一些其他工作以公理化途径刻画中心性指标。早在 Sabidussi, 1966 就提出了若干检验中心性指标的自然公理。在 Altman and Tennenholtz, 2005 与 Was and Skibski, 2018 中，作者们提出了 Seeley 与 PageRank 中心性的公理化刻画。随后，在 Skibski and Sosnowska, 2018 中，基于距离的中心性也被公理化。
在许多应用中，人们需要度量一组节点而非单个节点的中心性。例如，可能需要评估某个特定社会群体对社会的影响，或者评估一个部门在组织内部的重要性。从 Everett and Borgatti, 1999 开始，若干工作提出了群体中心性（group centrality）的各种变体：Kolaczyk et al., 2009；Veremyev et al., 2017；Akgün and Tural, 2020。让我们强调：在大多数情况下，简单地把各个节点的中心性值相加是不合适的。毫不奇怪，合作博弈论的方法非常适合用来定义群体中心性指标，见例如 Michalak et al., 2013；Szczepański et al., 2016。
常常重要的是只找出网络中 Top-$k$ 的中心节点。这一问题已在 Avrachenkov et al., 2011, 2014c；Ostuni et al., 2013；Avrachenkov et al., 2014b；Yoshida, 2014；Borassi and Natale, 2019；Fan et al., 2019 中得到研究；亦见其中所引文献。
我们注意到，如果把 Katz 中心性中的几何折扣换成 Poisson（阶乘）折扣，就得到 Estrada 的子图中心性（又称 communicability 中心性）（Estrada and Rodriguez-Velazquez, 2005；Estrada and Hatano, 2008）。进一步，如果再把邻接矩阵换成随机游走的转移矩阵，就得到热核 PageRank（heat kernel PageRank）（Chung, 2007）。
在综述 (Gleich, 2015) 中，可以找到对 PageRank 的各种修改与应用的出色的全面概览。