生物医学网络科学Biomedical Network Science
Example09 / 10

随机几何图——空间嵌入带来的高聚类与“大世界”

所属专题
小世界与无标度网络模型
下载
Notebook · .py

在单位正方形中随机撒 N 个点，距离小于 r 的点对相连；r 取使期望平均度约为 10 的值（忽略边界效应 ≈Nπr²）。 与同节点数、同边数的 ER 网络比较聚集系数与平均路径；二维随机几何图的聚集系数理论值为 1-3√3/(4π)≈0.587（Dall 与 Christensen 2002）。 再加入少量随机“长程连接”（每节点平均 0.05 条），观察路径长度骤降而聚集几乎不变——空间版的小世界机制。 输出：RGG 的 C≈0.60–0.62，略高于理论值（边界附近节点的邻域被截断）；N 增大 4 倍时 L 约增大 2 倍（按 √N 增长）， ER 的 C 很小、L 按 ln N 缓慢增长；加入约 100 条长程边后 L 降到原来的一半以下，C 几乎不变。

Output输出图

随机几何图——空间嵌入带来的高聚类与“大世界”：输出图 1

Output文字输出

N= 500: RGG <k>=9.0, C=0.618, L=9.5 | ER C=0.0164, L=3.06
N=2000: RGG <k>=9.7, C=0.598, L=17.6 | ER C=0.0048, L=3.60
理论值 1-3√3/(4π) = 0.587
加入 99 条长程边后: C=0.585, L=7.82

Code代码

# 在单位正方形中随机撒 N 个点，距离小于 r 的点对相连；r 取使期望平均度约为 10 的值（忽略边界效应 <k>≈Nπr²）。
# 与同节点数、同边数的 ER 网络比较聚集系数与平均路径；二维随机几何图的聚集系数理论值为 1-3√3/(4π)≈0.587（Dall 与 Christensen 2002）。
# 再加入少量随机“长程连接”（每节点平均 0.05 条），观察路径长度骤降而聚集几乎不变——空间版的小世界机制。
# 输出：RGG 的 C≈0.60–0.62，略高于理论值（边界附近节点的邻域被截断）；N 增大 4 倍时 L 约增大 2 倍（按 √N 增长），
#       ER 的 C 很小、L 按 ln N 缓慢增长；加入约 100 条长程边后 L 降到原来的一半以下，C 几乎不变。
import networkx as nx
import numpy as np

for N in [500, 2000]:
    r = np.sqrt(10 / (np.pi * N))
    G = nx.random_geometric_graph(N, r, seed=2)
    G = G.subgraph(max(nx.connected_components(G), key=len)).copy()
    E = nx.gnm_random_graph(G.number_of_nodes(), G.number_of_edges(), seed=2)
    E = E.subgraph(max(nx.connected_components(E), key=len)).copy()
    print("N=%4d: RGG <k>=%.1f, C=%.3f, L=%.1f | ER C=%.4f, L=%.2f"
          % (N, 2 * G.number_of_edges() / G.number_of_nodes(), nx.average_clustering(G),
             nx.average_shortest_path_length(G), nx.average_clustering(E), nx.average_shortest_path_length(E)))

print("理论值 1-3√3/(4π) = %.3f" % (1 - 3 * np.sqrt(3) / (4 * np.pi)))

rng = np.random.default_rng(5)
nodes = list(G.nodes())
H = G.copy()
for _ in range(int(0.05 * len(nodes))):
    a, b = rng.choice(nodes, 2, replace=False)
    H.add_edge(a, b)
print("加入 %d 条长程边后: C=%.3f, L=%.2f" % (int(0.05 * len(nodes)), nx.average_clustering(H),
                                          nx.average_shortest_path_length(H)))

# 作图：左为空间嵌入的网络（红线 = 新加的长程边）；右为加边前后的 C 与 L
import matplotlib.pyplot as plt

fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(10, 4.2), gridspec_kw={"width_ratios": [1.1, 1]})
pos = nx.get_node_attributes(G, "pos")
nx.draw_networkx_edges(G, pos, ax=ax1, edge_color="0.7", alpha=0.4, width=0.4)
nx.draw_networkx_edges(H, pos, ax=ax1, edgelist=[e for e in H.edges() if not G.has_edge(*e)], edge_color="#d6604d", width=1)
nx.draw_networkx_nodes(G, pos, ax=ax1, node_size=4, node_color="#4393c3")
ax1.set_title("RGG (N = %d) + %d shortcuts" % (N, H.number_of_edges() - G.number_of_edges()), fontsize=10)
ax1.set_aspect("equal"); ax1.axis("off")
vals = [(nx.average_clustering(G), nx.average_shortest_path_length(G)), (nx.average_clustering(H), nx.average_shortest_path_length(H))]
for j, (lab, col) in enumerate([("clustering C", "#92c5de"), ("path length L", "#d6604d")]):
    bars = ax2.bar(np.arange(2) + (j - 0.5) * 0.36, [v[j] / vals[0][j] for v in vals], 0.36, color=col, label=lab)
    for bar, v in zip(bars, vals):
        ax2.text(bar.get_x() + 0.18, bar.get_height() + 0.02, "%.3g" % v[j], ha="center", fontsize=9)
ax2.set_xticks([0, 1]); ax2.set_xticklabels(["RGG", "RGG + shortcuts"])
ax2.set_ylabel("value relative to RGG"); ax2.set_ylim(0, 1.2); ax2.legend(fontsize=8)
ax2.set_title("Shortcuts halve L, C barely changes", fontsize=10)
plt.tight_layout(); plt.show()

Run在浏览器中运行

首次加载 Python 环境约需 20–40 秒；可以修改参数后重新运行。

随机几何图——空间嵌入带来的高聚类与“大世界”