中心性：度、接近与介数

“哪个节点最重要？”没有唯一答案。中心性（centrality）是一族把节点按某种“重要性”排序的指标，每一种都对应一个关于网络上“流动什么、怎样流动”的隐含模型。本页介绍基于局部连接与最短路径的三种，谱类中心性介绍基于途径与随机游走的几种，k 核介绍基于“嵌入深度”的指标，中心性的选择与解释讨论如何选择。

度中心性

$$C_D(i)=\frac{k_i}{N-1}.$$

最简单、最稳健、计算最快（$O(M)$），只反映直接邻居。它假设影响只通过一步接触产生，例如直接的物理相互作用或直接接触传播的初期。

接近中心性与调和中心性

接近中心性在不连通网络中失效（只要有一个 $d_{ij}=\infty$，$C_C(i)=0$）。NetworkX 对不连通网络采用 Wasserman–Faust 修正：只对可达节点求平均，再乘以可达比例。调和中心性天然处理不可达节点，Boldi 与 Vigna（2014）从公理化角度论证它比接近中心性更合理。网络平均的调和中心性就是全局效率。

接近类指标的数值范围通常很窄：小世界网络中所有节点的平均距离都在 $\ln N$ 附近，节点之间差别不大，排序容易被微小的结构变动打乱。

介数中心性

介数大的节点是瓶颈（bottleneck）或“桥”：大量最短路径依赖它。它与度相关但不等价，一个度很低的节点只要连接两个大社团，介数就可能很高。把求和对象从节点换成边，就得到用于 Girvan–Newman 社团发现的边介数（见Girvan–Newman 算法与边介数）。

计算：逐对枚举最短路径的代价过高。Brandes（2001）算法对每个源点做一次 BFS，同时记录最短路径条数，再按距离由远及近回溯累加“依赖度”，总代价在无权网络中为 $O(NM)$，加权网络中为 $O(NM+N^2\log N)$（推导见数学推导与算法）。对几十万节点的网络，可随机抽取部分源点近似（NetworkX 的参数 k）。