真实网络与同规模 ER 网络的比较

# 生成与空手道网络节点数 N、边数 M 相同的 ER 网络（G(N,M) 模型），取其最大连通分支，
# 比较平均聚集系数 C 与平均路径长度 L，并给出 ER 聚集系数的理论值 C ≈ <k>/(N-1)。
# 输出：两者 L 相近，而空手道网络的 C 明显高于 ER 网络——这正是“小世界性”的含义。
# 单个随机网络有涨落，严格比较应对多个随机种子取平均（见小世界与无标度网络模型的代码示例）。
import networkx as nx

K = nx.karate_club_graph()
n, m = K.number_of_nodes(), K.number_of_edges()
R = nx.gnm_random_graph(n, m, seed=3)
R = R.subgraph(max(nx.connected_components(R), key=len))
print("空手道网络: C=%.3f, L=%.3f" % (nx.average_clustering(K), nx.average_shortest_path_length(K)))
print("ER 网络:    C=%.3f, L=%.3f（理论 C≈%.3f；最大连通分支含 %d/%d 个节点）"
      % (nx.average_clustering(R), nx.average_shortest_path_length(R), 2 * m / n / (n - 1),
         R.number_of_nodes(), n))

# 作图：空手道网络与同规模 ER 网络的 C、L 对比
import matplotlib.pyplot as plt
import numpy as np

vals = {"karate": (nx.average_clustering(K), nx.average_shortest_path_length(K)),
        "ER G(N,M)": (nx.average_clustering(R), nx.average_shortest_path_length(R))}
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(10, 4))
for ax, j, lab in [(ax1, 0, "average clustering C"), (ax2, 1, "average path length L")]:
    v = [vals[k][j] for k in vals]
    ax.bar(list(vals), v, color=["#d6604d", "#92c5de"], width=0.55)
    for i, x in enumerate(v):
        ax.text(i, x * 1.02, "%.3f" % x, ha="center")
    ax.set_ylabel(lab)
ax1.axhline(2 * m / n / (n - 1), color="0.4", ls="--", label="ER theory <k>/(N-1)"); ax1.legend(fontsize=8)
ax1.set_title("Karate C is %.1fx the random value" % (vals["karate"][0] / vals["ER G(N,M)"][0]), fontsize=10)
ax2.set_title("Path lengths are similar", fontsize=10)
plt.tight_layout(); plt.show()