Python案例如何用Networkx做图的半径

wen python案例 2026-07-16 1

Python案例：如何用NetworkX计算图的半径？——从理论到实战完整指南

📑 目录导读

核心概念速览：什么是图的半径？与直径、离心率的关系？
NetworkX环境搭建：安装与基础图对象创建
计算图的半径：从单点到全局：用radius()函数实战
案例详解1：社交网络中的“影响力半径”（无向图）
案例详解2：有向图中如何计算半径？（有向图处理）
进阶技巧：可视化半径（绘制离心率分布图）
常见问题Q&A：为什么某些图radius为无穷大？如何处理断图？
总结与性能优化建议

核心概念速览：图的半径到底是什么？

图的半径（Radius） 是图论中描述“中心性”的关键指标，定义为：所有节点离心率中的最小值。

Python案例如何用Networkx做图的半径

离心率（Eccentricity）：某个节点到图中最远节点的最短路径距离。
半径 = min(所有节点的离心率)
直径（Diameter）：所有节点离心率中的最大值,即图中最远两点的最短路径。

举个例子：一个星形网络（中心节点连接所有叶子），中心节点的离心率=1（到任何叶子一步），叶子的离心率=2（到对面的叶子要经过中心），因此该图的半径=1。

问答1：半径和直径的关系？
答：对任意连通图，半径 ≤ 直径 ≤ 2×半径，例如完全图Kn，半径=直径=1。

NetworkX环境搭建

# 安装NetworkX（建议Python 3.8+）
!pip install networkx matplotlib numpy
import networkx as nx
import matplotlib.pyplot as plt
import numpy as np

创建基础图对象：

nx.Graph()：无向图
nx.DiGraph()：有向图
nx.complete_graph(5)：快速生成完全图

核心函数：`nx.radius()` 与 `nx.eccentricity()`

1 计算单节点离心率

G = nx.path_graph(5)  # 路径图：0-1-2-3-4
ecc = nx.eccentricity(G)
print(ecc)  # {0:4, 1:3, 2:2, 3:3, 4:4}
# 节点0到最远节点4距离=4

2 一键计算半径

r = nx.radius(G)
print(r)  # 输出2（节点2离心率最小）

关键参数：默认usebounds=True会使用加速算法,若图不连通会抛异常。

案例详解1：社交网络中的“影响力半径”

场景：某社交群有10人，友谊关系如下（A~J为节点，边代表互相关注）。
问题：谁是“最短路径到达所有人”的中心人物？

# 创建社交网络（星形+链式混合）
edges = [('A','B'), ('A','C'), ('A','D'), ('B','E'), ('B','F'),
         ('C','G'), ('D','H'), ('E','I'), ('F','J')]
G = nx.Graph()
G.add_edges_from(edges)
# 计算半径和中心节点
r = nx.radius(G)
print(f"图的半径：{r}")  # 输出2
# 找出离心率=半径的节点（图中心）
centers = [n for n in G.nodes() if nx.eccentricity(G)[n] == r]
print(f"中心节点：{centers}")  # ['A']

可视化：用节点大小表示离心率。

ecc_dict = nx.eccentricity(G)
plt.figure(figsize=(8,6))
pos = nx.spring_layout(G, seed=42)  # 固定布局
node_sizes = [ecc_dict[n]*300 for n in G.nodes()]  # 离心率越大节点越大
nx.draw(G, pos, with_labels=True, node_size=node_sizes, 
        node_color='lightblue', edge_color='gray')f"社交网络离心率分布（半径={r}）")
plt.show()

结果分析：节点A离心率=2（到最远节点如J需2步），而B到J需3步——A是实际上的信息传播中心。

问答2：如果图有多个中心怎么办？
答：比如4个节点形成的环，每个节点离心率=2，半径=2，所有节点都是中心，此时半径衡量的是“最坏情况下的最短距离”。

案例详解2：有向图中的半径计算（需强连通）

关键差异：有向图的半径需图强连通，若某节点无法到达另一个方向，radius()会报错。

# 创建强连通有向图
G_di = nx.DiGraph()
G_di.add_edges_from([(1,2),(2,3),(3,1),(2,4),(4,1)])  # 形成环+分支
# 计算有向离心率（有向最短路径）
ecc_di = nx.eccentricity(G_di)
print(ecc_di)  # {1: 2, 2: 2, 3: 3, 4: 3}
r_di = nx.radius(G_di)
print(f"有向图半径：{r_di}")  # 2
# 若图非强连通会抛 nx.NetworkXError
G_non_strong = nx.DiGraph([(1,2),(2,3)])
# nx.radius(G_non_strong)  # 会报错：Graph is not strongly connected

解决方法：先检测强连通分量：

if nx.is_strongly_connected(G_di):
    print("强连通，可计算半径")
else:
    print("图非强连通，请先提取最大强连通分量")

问答3：有向图半径为0的情况？
答：自环图（每个节点都有自环），离心率=0，半径=0,但实际很少用。

进阶技巧：可视化半径与离心率分布

应用场景：分析网络拓扑的“中心化程度”。

# 生成随机图并可视化离心率
G_rand = nx.erdos_renyi_graph(20, 0.2)  # 20节点，边概率0.2
# 保留最大连通分量
components = list(nx.connected_components(G_rand))
G_main = G_rand.subgraph(max(components, key=len))
ecc = nx.eccentricity(G_main)
r = nx.radius(G_main)
d = nx.diameter(G_main)
# 绘制柱状分布
plt.figure(figsize=(10,5))
plt.subplot(121)
plt.hist(list(ecc.values()), bins=range(d+2), alpha=0.7, edgecolor='black')
plt.axvline(r, color='r', linestyle='--', label=f'Radius={r}')
plt.axvline(d, color='g', linestyle='--', label=f'Diameter={d}')
plt.xlabel('Eccentricity')
plt.ylabel('Node count')
plt.legend()
plt.subplot(122)
pos = nx.spring_layout(G_main, seed=42)
nx.draw(G_main, pos, node_color=[ecc[n] for n in G_main.nodes()], 
        cmap=plt.cm.viridis, with_labels=False, node_size=200)'Node color = eccentricity')
plt.tight_layout()
plt.show()

输出解读：左图显示多数节点离心率接近半径，说明网络中心化强；若离心率分布扁平（接近直径），表示网络较“均匀”。

常见问题Q&A（补充搜索引擎高频提问）

Q1：我的图不连通，如何计算每个连通分量的半径？

for i, comp in enumerate(nx.connected_components(G)):
    sub = G.subgraph(comp)
    print(f"分量{i+1}：半径={nx.radius(sub)}, 节点数={len(sub)}")

Q2：为什么`radius()`比`eccentricity()`慢？能优化吗？

radius()内部会调用eccentricity()，默认启用use bounds剪枝（基于图上下界）。
优化建议：若只需要全局半径，用nx.radius(G)即可，若需所有节点离心率，才用eccentricity()。

Q3：计算超大规模图（10万节点）的半径怎么办？

使用近似算法：nx.approximation.radius(G)（在networkx.algorithms.approximation中）。
或采样部分节点计算离心率近似值。

Q4：半径和网络鲁棒性有什么关系？

半径小的图（如星形）任中心节点故障会严重瘫痪；半径大的图（如环）较抗单点故障。

总结与性能优化建议

场景	推荐函数	注意
小图（<1000节点）	`nx.radius()`	默认即可
中等图（1000~1万）	`nx.radius(G, usebounds=True)`	加速剪枝
大图（>1万）	`nx.approximation.radius()`	或手工采样
有向图	`nx.radius(G_di)`	需先检查强连通
多分量	手动各分量计算	遍历`nx.connected_components()`