Example05 / 11
常见图的拉普拉斯谱、特征值比与谱界
用数值方法验证几类图的拉普拉斯谱闭式解（完全图、星图、环、路径），并计算 代数连通度 mu_2、最大特征值 mu_N、特征值比 mu_N/mu_2，检查两条常用界： Fiedler 上界 mu_2 <= N/(N-1) * k_min； mu_N >= k_max + 1（至少有一条边时）。 最后演示：在环上加一条“捷径”后 mu_2 增大、特征值比下降（加边不会使任何拉普拉斯特征值变小）。 大型稀疏网络用 networkx.algebraic_connectivity（基于稀疏迭代求解）而不是稠密特征分解。
Output输出图
Output文字输出
complete mu2=10.000 muN=10.000 比值=1.00 | Fiedler 上界 10.000 | k_max+1=10 star mu2=1.000 muN=10.000 比值=10.00 | Fiedler 上界 1.111 | k_max+1=10 ring mu2=0.382 muN=4.000 比值=10.47 | Fiedler 上界 2.222 | k_max+1=3 path mu2=0.098 muN=3.902 比值=39.86 | Fiedler 上界 1.111 | k_max+1=3 环 mu2=0.382 mu_N/mu_2=10.47 特征值相对原环均不减: True +1 条捷径 mu2=0.382 mu_N/mu_2=12.73 特征值相对原环均不减: True +2 条捷径 mu2=0.697 mu_N/mu_2=7.34 特征值相对原环均不减: True N=5000 WS 网络的 mu2（稀疏求解）= 0.1797
Code代码
# 用数值方法验证几类图的拉普拉斯谱闭式解（完全图、星图、环、路径），并计算
# 代数连通度 mu_2、最大特征值 mu_N、特征值比 mu_N/mu_2，检查两条常用界：
# Fiedler 上界 mu_2 <= N/(N-1) * k_min； mu_N >= k_max + 1（至少有一条边时）。
# 最后演示：在环上加一条“捷径”后 mu_2 增大、特征值比下降（加边不会使任何拉普拉斯特征值变小）。
# 大型稀疏网络用 networkx.algebraic_connectivity（基于稀疏迭代求解）而不是稠密特征分解。
import numpy as np
import networkx as nx
N = 10
graphs = {
"complete": nx.complete_graph(N),
"star": nx.star_graph(N - 1),
"ring": nx.cycle_graph(N),
"path": nx.path_graph(N),
}
closed = {
"complete": np.r_[0, [N] * (N - 1)],
"star": np.r_[0, [1] * (N - 2), N],
"ring": np.sort(2 - 2 * np.cos(2 * np.pi * np.arange(N) / N)),
"path": np.sort(2 - 2 * np.cos(np.pi * np.arange(N) / N)),
}
for name, G in graphs.items():
L = nx.laplacian_matrix(G).toarray().astype(float)
mu = np.sort(np.linalg.eigvalsh(L))
k = np.array([d for _, d in G.degree()])
assert np.allclose(mu, closed[name]), name
print("%-9s mu2=%.3f muN=%.3f 比值=%.2f | Fiedler 上界 %.3f | k_max+1=%d"
% (name, mu[1], mu[-1], mu[-1] / mu[1], N / (N - 1) * k.min(), k.max() + 1))
def lap_spec(G):
return np.sort(np.linalg.eigvalsh(nx.laplacian_matrix(G).toarray().astype(float)))
ring = nx.cycle_graph(N); mu_old = lap_spec(ring)
one = ring.copy(); one.add_edge(0, 5) # 一条对径捷径
two = one.copy(); two.add_edge(2, 7) # 再加一条
for name, H in [("环", ring), ("+1 条捷径", one), ("+2 条捷径", two)]:
mu = lap_spec(H)
print("%-8s mu2=%.3f mu_N/mu_2=%.2f 特征值相对原环均不减: %s"
% (name, mu[1], mu[-1] / mu[1], bool(np.all(mu >= mu_old - 1e-12))))
# 环的 mu2 是二重特征值：一条捷径只能抬高其中一个，mu2 不变；两条捷径才使 mu2 上升
big = nx.connected_watts_strogatz_graph(5000, 6, 0.1, seed=0)
print("N=5000 WS 网络的 mu2（稀疏求解）=", round(nx.algebraic_connectivity(big, method="lanczos", seed=0), 4))
import matplotlib.pyplot as plt
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(10, 4))
for (name, G), mk in zip(graphs.items(), ["o", "s", "^", "D"]):
ax1.plot(np.arange(1, N + 1), lap_spec(G), marker=mk, ls="-", lw=0.8, ms=5, label=name)
ax1.set_xlabel("index i"); ax1.set_ylabel("Laplacian eigenvalue mu_i"); ax1.legend(loc="center left", bbox_to_anchor=(0.12, 0.6)); ax1.set_title("Laplacian spectra (N = 10)")
for (name, H), mk in zip([("ring", ring), ("+1 shortcut", one), ("+2 shortcuts", two)], ["o", "s", "^"]):
ax2.plot(np.arange(1, N + 1), lap_spec(H), marker=mk, ls="-", lw=0.8, ms=5, label=name)
ax2.set_xlabel("index i"); ax2.set_ylabel("mu_i"); ax2.legend()
ax2.set_title("Adding edges never lowers any eigenvalue")
plt.tight_layout(); plt.show()Run在浏览器中运行
首次加载 Python 环境约需 20–40 秒；可以修改参数后重新运行。