NetworkX图距离实战：最短路径、距离矩阵、离心率与图直径

图距离：两个节点之间的最短路径长度

图距离（Graph Distance）指的是两个节点之间最短路径的长度。如果对路径的概念还不熟悉，可以先回顾一下前文相关内容。

• 在无权图中，图距离表示两个节点之间最短路径经过的边数；有权图中每条边才会携带欧式距离等权重信息
• 它常被用来衡量图中节点之间的距离远近或相似程度

1、寻找并绘制最短路径

可以用 networkx.shortest_path() 找到图中两个节点之间的最短路径。下面以空手道俱乐部数据集为例，先用 spring_layout 布局把整张图画出来，再特别标出节点 12 与 18 之间的最短路径。

# 用俱乐部数据集，查看图
G = nx.karate_club_graph()  # 空手道俱乐部图
pos = nx.spring_layout(G, seed=3)

plt.figure(figsize=(14, 9))
nx.draw_networkx(G, pos)
nx.draw_networkx_nodes(G, pos, nodelist=[12, 18], node_color='r')  # 可选择任意几个点标红，这里选择12和18
plt.savefig('空手道俱乐部图.svg')

path_nodes = nx.shortest_path(G, 12, 18)  # 找到节点12、18之间最短路径，返回数组[12, 0, 2, 32, 18]
path_edges = list(nx.utils.pairwise(path_nodes))  # 相邻元素配对转化为边序列
# cyclic=False 为默认，设 True 时生成首尾闭合的路径边序列

plt.figure(figsize=(14, 9))
nx.draw_networkx(G, pos)
nx.draw_networkx_nodes(G, pos,
                       nodelist=path_nodes,
                       node_color='r')
nx.draw_networkx_edges(G, pos,
                       edgelist=path_edges,
                       edge_color='r')  # 绘制最短路径节点与边，标为红色
plt.savefig('空手道俱乐部图12、18最短路径.svg')

可以看到，nx.shortest_path() 返回的是一个节点序列，配合 nx.utils.pairwise() 就能把节点序列转换成边序列，进而用红色高亮出来。

2、图距离矩阵

图距离矩阵：由图中每一对节点之间的图距离构造而成，它汇总了所有节点对之间可能路径的距离信息。

# 成对最短距离值 (图距离)
distances_all = dict(nx.shortest_path_length(G))  # 这里未选择某两个节点，意思是找到每个节点两两之间的最短路径距离，并转化为字典格式

# 创建图距离矩阵
list_nodes = list(G.nodes())
Shortest_D_matrix = np.full((len(G.nodes()), len(G.nodes())), np.nan)

# 将嵌套字典转换为图距离矩阵。第一个 for 循环遍历 list_nodes 列表中的所有节点，相当于始点；第二层 for 循环相当于遍历所有终点
for i, i_node in enumerate(list_nodes):
    for j, j_node in enumerate(list_nodes):
        # 用 try ... except ... 处理可能不存在路径的情况
        try:
            d_ij = distances_all[i_node][j_node]
            Shortest_D_matrix[i][j] = d_ij
        except KeyError:
            print(i_node + ' to ' + j_node + ': no path')

Shortest_D_matrix.max()  # 图距离最大值

# 用热图可视化图距离矩阵
plt.figure(figsize=(14, 9))
sns.heatmap(Shortest_D_matrix, cmap='Reds',
             annot=False,
             xticklabels=list(G.nodes),
             yticklabels=list(G.nodes),
             linecolor='k', square=True,
             cbar=True,
             linewidths=0.2)
plt.savefig('图距离矩阵，无权图.svg')

由于数据集为无权无向图，图距离矩阵对称，且图距离就是最短路径的边数（范围在 1~5）。接下来统计一下每个距离值（边数）的频数，并绘制柱状图。

# 取出图距离矩阵中所有成对图距离 (不含对角线下三角元素)——因为对于无向图而言，矩阵对称，比如12-18与18-12之间的图距离相等
# 使用 numpy.tril 获取下三角矩阵，并排除对角线元素
lower_tri_wo_diag = np.tril(Shortest_D_matrix, k=-1)

# 获取下三角矩阵（不含对角线）的索引
rows, cols = np.tril_indices(Shortest_D_matrix.shape[0], k=-1)

# 使用索引从原矩阵中取出对应的元素。这是因为无向图图距离为对称矩阵，节点成对距离 (非对角线元素) 重复
list_shortest_distances = Shortest_D_matrix[rows, cols]

# 使用 numpy.unique 函数获取独特值及其出现次数
unique_values, counts = np.unique(list_shortest_distances,
                                  return_counts=True)
print(unique_values)

# 绘制柱状图
plt.figure(figsize=(14, 9))
plt.bar(unique_values, counts, color='green')
plt.xlabel('Graph distance')
plt.ylabel('Count')
plt.savefig('图距离柱状图.svg')

3、平均图距离

平均图距离：任意节点到其他所有节点都有对应的图距离，把这些距离取平均之后的值，就是该节点的平均图距离。换个角度看，也就是图距离矩阵中每一行（或每一列）去掉对角线元素后的均值。

# 节点平均距离。返回一个数组，元素依次是每个节点的平均图距离（平均最短路径边数）
average_path_lengths = [
    np.mean(list(spl.values())) for spl in distances_all.values()
]
average_all = np.mean(average_path_lengths)  # 所有节点平均图距离取均值，用于画一条红线进行比较

# 绘制每个节点的平均图距离柱状图
plt.figure(figsize=(14, 9))
plt.bar(G.nodes(), average_path_lengths, color='green')
plt.axhline(y=average_all, c='r')
plt.xlabel('Node label')
plt.ylabel('Average node graph distance')
plt.savefig('节点平均图距离.svg')

# 绘制每个平均图距离数值的频数图（直方图）
plt.figure(figsize=(14, 9))
plt.hist(average_path_lengths, ec='k', color='g')
plt.axvline(x=average_all, c='r')
plt.xlabel('Average node graph distance')
plt.ylabel('Count')
plt.savefig('节点图距离直方图.svg')

也可根据节点平均图距离大小渲染节点：

dict_ave_graph_d = {index: value for index, value in enumerate(average_path_lengths)}  # 根据节点平均图距离大小渲染节点
unique_ave_graph_d = set(average_path_lengths)  # 取出节点平均图距离独特值
# colors = plt.cm.RdYlBu(np.linspace(0, 1, len(unique_ave_graph_d)))  # 独特值的颜色映射

plt.figure(figsize=(14, 9))
nx.draw_networkx(G, pos,
                 cmap='RdYlBu_r',
                 with_labels=True,
                 node_color=average_path_lengths)
plt.savefig('根据平均图距离大小渲染节点.svg')

上图暖色系节点代表此节点的平均图距离较大，也就是说这些节点在这个社区关系中更“边缘”；相反，冷色系代表节点平均距离更小，即这群节点更“中心”（该节点起关键作用）。

平均图距离帮助理解一个节点在整个网络中的位置，以及它与其他节点的相对接近程度，为网络的连通性和结构特性提供了直观洞察。

4、离心率

离心率的定义与圆锥曲线（椭圆、双曲线、抛物线）中的离心率完全不同，这里指的是图论中的节点离心率：

• 定义为该节点到图中所有其他节点的最短路径中最长的那一条路径长度，也就是离该节点图距离的最大值，用 nx.eccentricity 计算
• 离心率越小的节点，通常意味着它在图中的位置越“中心”，即它到其他节点的距离都相对较短
• 应用场景包括：识别网络中的关键节点（如信息传播中心或意见领袖）、优化运输路径以提升物流效率、分析疾病传播的速度和范围，从而制定有效防控策略等

eccentricity = nx.eccentricity(G)  # 计算每个节点离心率，返回一个字典——节点标签：离心率
eccentricity_list = list(eccentricity.values())  # 只取字典 values 并转化为列表

# 自定义函数，过滤 dict。
# 过滤出所有值等于 unique 的键值对，并将这些键值对存储在新的字典 newDict 中返回。这是为了后续节点颜色映射的方便，离心率相同的被映射为相同颜色
def filter_value(dict_, unique):
    newDict = {}
    for (key, value) in dict_.items():
        if value == unique:
            newDict[key] = value
    return newDict

# 根据离心率大小渲染节点
unique_ecc = set(eccentricity_list)  # 取出节点离心率独特值
colors = plt.cm.RdYlBu(np.linspace(0, 1, len(unique_ecc)))  # 独特值的颜色映射

plt.figure(figsize=(14, 9))
nx.draw_networkx_edges(G, pos)  # 绘制图的边

# 分别绘制不同离心率
for deg_i, color_i in zip(unique_ecc, colors):
    dict_i = filter_value(eccentricity, deg_i)
    nx.draw_networkx_nodes(G, pos,
                            nodelist=list(dict_i.keys()),
                            node_color=color_i)  # 绘制不同离心率节点，用不同颜色渲染节点

labels = {node: node for node in G.nodes()}  # 使用节点ID作为标签的示例
nx.draw_networkx_labels(G, pos, labels=labels, font_size=14)  # 调整 font_size 以适应你的图形
plt.savefig('根据离心率大小渲染节点.svg')

也可以绘制节点-离心率的柱状图、离心率-频数图（离心率直方图），从更多侧面进行统计可视化。

5、图直径、边缘点、图半径与中心点

图直径

• 图距离矩阵中的最大值，也是所有节点离心率的最大值
• 非连通图（至少一对节点间无路径相连）的图直径无穷大
• 它是衡量图大小和稀疏程度的指标，提供了对图整体大小和节点之间最远距离的感知，常被当作图的全局性质来衡量
• 一幅图的直径较大，说明图中存在一些较为疏远的节点

边缘点

• 离心率最大的节点，即该节点的离心率等于图直径
• 可能不止一个

list_periphery = list(nx.periphery(G))  # 获取图的边缘点
plt.figure(figsize=(14, 9))
nx.draw_networkx(G, pos, node_color='green')
nx.draw_networkx_nodes(G, pos,
                       nodelist=list_periphery,
                       node_color='r')
plt.savefig('空手道俱乐部图，边缘点.svg')

图半径

• 注意：图半径并不是图直径的一半，而是所有节点离心率的最小值
• 它用来描述图的“紧凑性”。半径越小，表示网络中任意两点之间的最远距离越短，网络越紧凑

中心点

• 离心率最小的节点，即该节点的离心率等于图半径
• 可能不止一个

list_centers = list(nx.center(G))  # 获取图的中心点
plt.figure(figsize=(14, 9))
nx.draw_networkx(G, pos, node_color='green')
nx.draw_networkx_nodes(G, pos,
                       nodelist=list_centers,
                       node_color='r')
plt.savefig('空手道俱乐部图，中心点.svg')

以上就是利用 NetworkX 计算并可视化图距离相关指标的全过程。把这些指标组合起来，可以更完整地理解网络的拓扑结构与节点重要性。如果你对图论算法的更多实战内容感兴趣，欢迎到 云栈社区 浏览交流。