Example11 / 15

ER 随机网络中巨连通分支的涌现

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

N=1000，让平均度从 0.2 增加到 4，记录最大连通分支占全部节点的比例 S，并与理论曲线 S = 1 - exp(- S)（用不动点迭代求解）对比。输出：S 在 =1 附近陡然上升，远离临界点时模拟点与理论曲线吻合；<1 时理论值为 0，模拟值只是很小的有限规模碎片；临界点 =1 处有限规模效应最强，模拟值明显高于理论极限值。

Output输出图

Output文字输出

<k>=0.20: 模拟 S=0.006, 理论 S=0.000
<k>=1.00: 模拟 S=0.170, 理论 S=0.010
<k>=1.80: 模拟 S=0.754, 理论 S=0.732
<k>=2.60: 模拟 S=0.905, 理论 S=0.905
<k>=3.40: 模拟 S=0.965, 理论 S=0.962

Code代码

# N=1000，让平均度 <k> 从 0.2 增加到 4，记录最大连通分支占全部节点的比例 S，
# 并与理论曲线 S = 1 - exp(-<k> S)（用不动点迭代求解）对比。
# 输出：S 在 <k>=1 附近陡然上升，远离临界点时模拟点与理论曲线吻合；<k><1 时理论值为 0，
#       模拟值只是很小的有限规模碎片；临界点 <k>=1 处有限规模效应最强，模拟值明显高于理论极限值。
import networkx as nx
import numpy as np
import matplotlib.pyplot as plt

N = 1000
k_values = np.linspace(0.2, 4, 20)
S_sim = []
for kv in k_values:
    G = nx.fast_gnp_random_graph(N, kv / (N - 1), seed=7)
    S_sim.append(len(max(nx.connected_components(G), key=len)) / N)


def S_theory(kv, iters=200):
    S = 0.5
    for _ in range(iters):            # 不动点迭代求解 S = 1 - exp(-k S)
        S = 1 - np.exp(-kv * S)
    return S


for kv, s in zip(k_values[::4], S_sim[::4]):
    print("<k>=%.2f: 模拟 S=%.3f, 理论 S=%.3f" % (kv, s, S_theory(kv)))

plt.plot(k_values, S_sim, "o", label="simulation (N=1000)")
plt.plot(k_values, [S_theory(kv) for kv in k_values], "-", label="theory")
plt.axvline(1, ls="--", c="gray")
plt.xlabel("average degree <k>")
plt.ylabel("fraction in giant component")
plt.legend()
plt.show()

Run在浏览器中运行

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

ER 随机网络中巨连通分支的涌现

# N=1000，让平均度 <k> 从 0.2 增加到 4，记录最大连通分支占全部节点的比例 S，
# 并与理论曲线 S = 1 - exp(-<k> S)（用不动点迭代求解）对比。
# 输出：S 在 <k>=1 附近陡然上升，远离临界点时模拟点与理论曲线吻合；<k><1 时理论值为 0，
#       模拟值只是很小的有限规模碎片；临界点 <k>=1 处有限规模效应最强，模拟值明显高于理论极限值。
import networkx as nx
import numpy as np
import matplotlib.pyplot as plt

N = 1000
k_values = np.linspace(0.2, 4, 20)
S_sim = []
for kv in k_values:
    G = nx.fast_gnp_random_graph(N, kv / (N - 1), seed=7)
    S_sim.append(len(max(nx.connected_components(G), key=len)) / N)

def S_theory(kv, iters=200):
    S = 0.5
    for _ in range(iters):            # 不动点迭代求解 S = 1 - exp(-k S)
        S = 1 - np.exp(-kv * S)
    return S

for kv, s in zip(k_values[::4], S_sim[::4]):
    print("<k>=%.2f: 模拟 S=%.3f, 理论 S=%.3f" % (kv, s, S_theory(kv)))

plt.plot(k_values, S_sim, "o", label="simulation (N=1000)")
plt.plot(k_values, [S_theory(kv) for kv in k_values], "-", label="theory")
plt.axvline(1, ls="--", c="gray")
plt.xlabel("average degree <k>")
plt.ylabel("fraction in giant component")
plt.legend()
plt.show()