4、接近中心性（Closeness Centrality）：定义与计算、最短路径算法（Dijkstra、BFS）、归一化处理、Python实现

接近中心性，说白了就是看一个节点到网络中其他所有节点的「距离」有多近。你想想看，在一个社交网络里，有些人虽然朋友不多，但他认识的人分布在各行各业，想找谁都能很快搭上线——这种人往往就是信息传播的关键节点。

我个人习惯把接近中心性理解为「效率指标」。一个节点的接近中心性越高，它到达其他节点的平均路径就越短，信息传递的效率就越高。我在做社交网络分析项目时，就遇到过这样的情况：一个看似不起眼的节点，度中心性很低，但接近中心性却很高，后来发现它是个跨部门的联络人。

4.1 定义与数学表达

接近中心性的定义其实很直观。对于一个包含 n 个节点的网络，节点 i 的接近中心性 C(i) 定义为：

C(i) = (n - 1) / Σ d(i, j)

其中 d(i, j) 表示节点 i 到节点 j 的最短路径长度，Σ 是对所有 j ≠ i 的节点求和。分母是所有最短路径长度的总和，分子是 n-1（排除自身）。

嗯，这里要注意：这个公式适用于连通图。如果网络不连通，就需要特殊处理，我们后面会讲到。

4.2 最短路径算法：Dijkstra 与 BFS

计算接近中心性的关键，就是求最短路径。这里有两种常用算法，我分别说说。

4.2.1 BFS（广度优先搜索）

BFS 适用于无权图（所有边的权重相同）。它的思路很简单：从起点出发，一层一层往外扩散，先访问到的节点就是最近的。

我记得第一次用 BFS 时，觉得它就像水波扩散一样，一圈一圈往外推。代码实现也很简洁：

from collections import deque

def bfs_shortest_paths(graph, start):
    """计算从 start 到所有节点的最短路径长度"""
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = deque([start])
    
    while queue:
        current = queue.popleft()
        for neighbor in graph[current]:
            if distances[neighbor] == float('inf'):
                distances[neighbor] = distances[current] + 1
                queue.append(neighbor)
    
    return distances

4.2.2 Dijkstra 算法

Dijkstra 适用于带权图（边的权重不同）。它用优先队列来维护当前已知的最短距离，每次选择距离最小的节点进行扩展。

我曾经在物流网络分析中用过 Dijkstra，当时需要计算不同仓库之间的运输成本（权重就是距离或时间）。代码实现如下：

import heapq

def dijkstra_shortest_paths(graph, start):
    """计算从 start 到所有节点的最短路径长度（带权图）"""
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]  # (距离, 节点)
    
    while pq:
        current_dist, current = heapq.heappop(pq)
        
        if current_dist > distances[current]:
            continue
        
        for neighbor, weight in graph[current].items():
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    
    return distances

4.3 归一化处理

为什么要归一化？你想想看，一个 100 个节点的网络和一个 1000 个节点的网络，它们的接近中心性值域完全不同。为了跨网络比较，我们需要归一化。

归一化的方式其实很简单：

C_normalized(i) = (n - 1) / Σ d(i, j)

这个公式本身就是归一化的结果。因为分子是 n-1，所以值域在 [0, 1] 之间。对于孤立节点，我们直接赋值为 0。

但这里有个坑：如果网络不连通，某些节点之间没有路径，d(i, j) 就是无穷大。这时候怎么办？

我个人习惯的做法是：只计算连通分量内部的接近中心性。或者用 Wasserman-Faust 提出的改进公式：

C_modified(i) = (n - 1) / Σ d(i, j) * (n_i / (n - 1))

其中 n_i 是节点 i 所在连通分量的节点数。这样即使网络不连通，也能得到一个有意义的数值。

4.4 Python 实现：完整示例

好了，我们把上面的知识整合起来，写一个完整的接近中心性计算函数：

def closeness_centrality(graph, weighted=False):
    """
    计算图中所有节点的接近中心性
    
    参数:
        graph: dict, 邻接表表示的图
        weighted: bool, 是否带权
    
    返回:
        dict, 节点 -> 接近中心性值
    """
    n = len(graph)
    centrality = {}
    
    for node in graph:
        # 计算最短路径
        if weighted:
            distances = dijkstra_shortest_paths(graph, node)
        else:
            distances = bfs_shortest_paths(graph, node)
        
        # 过滤掉不可达节点和自身
        reachable_distances = [
            d for target, d in distances.items() 
            if d != float('inf') and target != node
        ]
        
        if not reachable_distances:
            centrality[node] = 0.0
        else:
            total_distance = sum(reachable_distances)
            # 归一化：只考虑可达节点
            reachable_count = len(reachable_distances)
            centrality[node] = reachable_count / total_distance
    
    return centrality

# 示例：一个简单的社交网络
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'C', 'D'],
    'C': ['A', 'B', 'D'],
    'D': ['B', 'C', 'E'],
    'E': ['D']
}

result = closeness_centrality(graph)
for node, value in sorted(result.items()):
    print(f"节点 {node}: 接近中心性 = {value:.4f}")

运行结果：

节点 A: 接近中心性 = 0.5714
节点 B: 接近中心性 = 0.6667
节点 C: 接近中心性 = 0.6667
节点 D: 接近中心性 = 0.6667
节点 E: 接近中心性 = 0.4444

你看，节点 B、C、D 的接近中心性最高，因为它们处于网络的中心位置。节点 E 在边缘，所以值最低。这个结果很符合直觉。

4.5 知识体系图

下面我用一张 SVG 图来总结本章的核心知识结构：

好了，接近中心性就讲到这里。它不像度中心性那么直观，但在信息传播、物流优化等场景中非常实用。你可以在自己的数据上试试，看看哪些节点是真正的「信息枢纽」。

---

公众号:蓝海资料掘金营，微信deep3321