判断一个真实网络是否“小世界”

# 以《悲惨世界》人物共现网络为例，计算 C 和 L，再与两种零模型比较，求小世界系数 σ = (C/C_rand)/(L/L_rand)：
#   (a) 同节点数、同边数的 ER 网络；(b) 用双边交换（约 10×E 次）保持度序列的随机化网络。
# 每种零模型取 5 个随机种子平均，并只在最大连通分支上计算 L。
# 输出：两种参照下 σ 都明显大于 1；保度随机化网络的 C_rand 比 ER 更高，因此 σ 更小、判断更严格。
import networkx as nx
import numpy as np

G = nx.Graph(nx.les_miserables_graph())      # 按无权图处理
n, e = G.number_of_nodes(), G.number_of_edges()
C = nx.average_clustering(G)
L = nx.average_shortest_path_length(G)
print("原网络: N=%d, E=%d, C=%.3f, L=%.3f" % (n, e, C, L))


def er_reference(seed):
    R = nx.gnm_random_graph(n, e, seed=seed)
    R = R.subgraph(max(nx.connected_components(R), key=len)).copy()
    return nx.average_clustering(R), nx.average_shortest_path_length(R)


def degree_preserving_reference(seed):
    R = G.copy()
    nx.double_edge_swap(R, nswap=10 * e, max_tries=100 * e, seed=seed)
    R = R.subgraph(max(nx.connected_components(R), key=len)).copy()
    return nx.average_clustering(R), nx.average_shortest_path_length(R)


Cr, Lr = np.mean([er_reference(s) for s in range(5)], axis=0)
print("ER 参照:   C_rand=%.3f, L_rand=%.3f, σ=%.2f" % (Cr, Lr, (C / Cr) / (L / Lr)))
Cd, Ld = np.mean([degree_preserving_reference(s) for s in range(5)], axis=0)
print("保度参照:  C_rand=%.3f, L_rand=%.3f, σ=%.2f" % (Cd, Ld, (C / Cd) / (L / Ld)))

# 作图：原网络与两种零模型的 C、L 对比，标题给出 σ
import matplotlib.pyplot as plt

labels = ["Les Miserables", "ER reference", "degree-preserving"]
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(10, 4))
for ax, v, lab in [(ax1, [C, Cr, Cd], "average clustering C"), (ax2, [L, Lr, Ld], "average path length L")]:
    ax.bar(labels, v, color=["#d6604d", "#92c5de", "#4393c3"], width=0.6)
    for i, x in enumerate(v):
        ax.text(i, x * 1.02, "%.3f" % x, ha="center", fontsize=9)
    ax.set_ylabel(lab)
ax1.set_title("sigma = %.2f (ER), %.2f (degree-preserving)" % ((C / Cr) / (L / Lr), (C / Cd) / (L / Ld)), fontsize=10)
ax2.set_title("Path lengths are comparable", fontsize=10)
plt.tight_layout(); plt.show()