图论（三）：图距离——寻找并绘制最短路径图距离矩阵平均图距离离心率图直径/边缘点/半径/中心点
图距离（两节点之间最短路径长/边数）
图距离是指两个节点之间的最短路径的长度（有关路径的概念请见上期）。
- 在无权图中，图距离表示两个节点之间的最短路径的边数（有权图每条边才有欧式距离等权重）
- 用于衡量图中节点之间的距离或相似性
1、寻找&绘制最短路径
- 用 networkx.shortest_path() 找到图中两节点之间最短路径图
#用俱乐部数据集，查看图
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))
# 在路径节点序列中获取相邻元素的配对转化为边序列 [(12, 0), (0, 2), (2, 32), (32, 18)]
#(不封闭)参数 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('空手道俱乐部图，15、16最短路径.svg')
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函数获取独特值及其出现次数。例如np.unique([1, 1, 2, 2, 3, 3])返回[1,2,3]
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')
也可以绘制节点-离心率bar柱状图、离心率-频数图（离心率直方图）进行更多侧面信息的统计可视化！
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')