生物医学网络科学Biomedical Network Science
Example12 / 15

ER 网络演化的四个区间

所属专题
网络结构指标与随机图
下载
Notebook · .py

固定 ，改变 N，看最大连通分支规模 N_G 如何随 N 增长： 亚临界 =0.5：N_G ~ ln N；临界 =1：N_G ~ N^{2/3}；超临界 =2：N_G ~ N（比例约 0.797）； 再在 N=2000 时扫描 ，估计“整个网络连通”的概率，验证连通阈值 ≈ ln N ≈ 7.6。 输出：=2 时 N_G/N 稳定在理论值 0.797；=0.5 时 N_G/ln N 只缓慢增长（理论上有 ln ln N 修正）； =1 时涨落极大，N_G/N^{2/3} 在 O(1) 范围内波动；连通概率在 ln N 附近从 0 升到 1， 与“孤立节点数近似泊松分布”给出的 exp(-N e^{-}) 相符。

Output输出图

ER 网络演化的四个区间：输出图 1

Output文字输出

N=  1000 | <k>=0.5: N_G/lnN=1.62 | <k>=1: N_G/N^(2/3)=1.02 | <k>=2: N_G/N=0.797
N=  4000 | <k>=0.5: N_G/lnN=2.03 | <k>=1: N_G/N^(2/3)=0.75 | <k>=2: N_G/N=0.792
N= 16000 | <k>=0.5: N_G/lnN=1.94 | <k>=1: N_G/N^(2/3)=1.38 | <k>=2: N_G/N=0.796
N= 64000 | <k>=0.5: N_G/lnN=2.64 | <k>=1: N_G/N^(2/3)=0.54 | <k>=2: N_G/N=0.797
ln N = 7.60
<k>= 4.0: 连通概率 0.00（理论 exp(-N e^{-<k>}) = 0.00）
<k>= 6.0: 连通概率 0.00（理论 exp(-N e^{-<k>}) = 0.01）
<k>= 7.0: 连通概率 0.07（理论 exp(-N e^{-<k>}) = 0.16）
<k>= 7.6: 连通概率 0.38（理论 exp(-N e^{-<k>}) = 0.37）
<k>= 8.0: 连通概率 0.57（理论 exp(-N e^{-<k>}) = 0.51）
<k>= 9.0: 连通概率 0.85（理论 exp(-N e^{-<k>}) = 0.78）
<k>=11.0: 连通概率 0.97（理论 exp(-N e^{-<k>}) = 0.97）

Code代码

# 固定 <k>，改变 N，看最大连通分支规模 N_G 如何随 N 增长：
#   亚临界 <k>=0.5：N_G ~ ln N；临界 <k>=1：N_G ~ N^{2/3}；超临界 <k>=2：N_G ~ N（比例约 0.797）；
# 再在 N=2000 时扫描 <k>，估计“整个网络连通”的概率，验证连通阈值 <k> ≈ ln N ≈ 7.6。
# 输出：<k>=2 时 N_G/N 稳定在理论值 0.797；<k>=0.5 时 N_G/ln N 只缓慢增长（理论上有 ln ln N 修正）；
#       <k>=1 时涨落极大，N_G/N^{2/3} 在 O(1) 范围内波动；连通概率在 ln N 附近从 0 升到 1，
#       与“孤立节点数近似泊松分布”给出的 exp(-N e^{-<k>}) 相符。
import networkx as nx
import numpy as np

rng = np.random.default_rng(0)


def largest_cc(N, c, reps=5):
    sizes = []
    for _ in range(reps):
        G = nx.fast_gnp_random_graph(N, c / (N - 1), seed=int(rng.integers(1e9)))
        sizes.append(len(max(nx.connected_components(G), key=len)))
    return np.mean(sizes)


rows, conn_rows = [], []                          # 存下结果用于作图
for N in [1000, 4000, 16000, 64000]:
    a, b, c = largest_cc(N, 0.5), largest_cc(N, 1.0), largest_cc(N, 2.0)
    rows.append((N, a / np.log(N), b / N ** (2 / 3), c / N))
    print("N=%6d | <k>=0.5: N_G/lnN=%.2f | <k>=1: N_G/N^(2/3)=%.2f | <k>=2: N_G/N=%.3f"
          % (N, a / np.log(N), b / N ** (2 / 3), c / N))

N = 2000
print("ln N = %.2f" % np.log(N))
for c in [4, 6, 7, 7.6, 8, 9, 11]:
    conn = np.mean([nx.is_connected(nx.fast_gnp_random_graph(N, c / (N - 1), seed=s)) for s in range(40)])
    conn_rows.append((c, conn))
    print("<k>=%4.1f: 连通概率 %.2f（理论 exp(-N e^{-<k>}) = %.2f）" % (c, conn, np.exp(-N * np.exp(-c))))

# 作图：左为三个区间的标度比值随 N 的变化，右为连通概率随 <k> 的变化
import matplotlib.pyplot as plt

R = np.array(rows)
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(10, 4))
for col, mk, lab in [(1, "o-", "<k>=0.5: N_G / ln N"), (2, "s--", "<k>=1: N_G / N^(2/3)"), (3, "^:", "<k>=2: N_G / N")]:
    ax1.plot(R[:, 0], R[:, col], mk, label=lab)
ax1.set_xscale("log"); ax1.set_xlabel("N"); ax1.set_ylabel("scaled giant component size"); ax1.legend(fontsize=8)
ax1.set_title("Each regime has its own scaling", fontsize=10)
cs, ps = zip(*conn_rows)
kk = np.linspace(3.5, 11.5, 100)
ax2.plot(cs, ps, "o", label="simulation (40 runs)")
ax2.plot(kk, np.exp(-N * np.exp(-kk)), "-", color="0.4", label="exp(-N e^{-<k>})")
ax2.axvline(np.log(N), color="#d6604d", ls="--", label="ln N = %.1f" % np.log(N))
ax2.set_xlabel("average degree <k>"); ax2.set_ylabel("P(connected)"); ax2.legend(fontsize=8)
ax2.set_title("Connectivity threshold at <k> ~ ln N (N = %d)" % N, fontsize=10)
plt.tight_layout(); plt.show()

Run在浏览器中运行

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

ER 网络演化的四个区间