5D Library › 社会网络拓扑、结构洞与复杂传染的数学模型 · English
第四章 无标度网络、优先连接与鲁棒性
度的分布
一个人的联系人数叫做他的度。在埃尔德什与雷尼研究的随机图中，每一对人以相同的概率相连，度的分布集中在平均值附近，远远超过平均值的人极少 (Erdős and Rényi 1960)。但许多真实网络看起来不是这样：少数节点有极多的连接，大多数节点只有很少的连接。
证据
优先连接。 巴拉巴西与阿尔伯特在 1999 年报告，电影演员合作网络、万维网与美国西部电网的度分布的尾部近似服从幂律 ，估计的指数分别约为 2.3、2.1 与 4。他们提出一个由两个机制组成的模型来解释它：网络不断增长，新节点加入时优先连接到已经有很多连接的节点（连接的概率与对方的度成正比）。这个模型产生的度分布服从幂律，理论指数为 3，他们的模拟给出 (Barabási and Albert 1999)。没有特征尺度的幂律分布被称为「无标度」的。
5D Library 第 6 本《注意力的经济学》已经实现了这个模型，并估计出约 2.91 的指数。本章不再重复，而是讨论两个后续问题：怎样判断一组数据是不是幂律，以及无标度的结构对网络的鲁棒性意味着什么。
「无标度网络其实很少见」
判断幂律最常见的做法，是把度分布画在双对数坐标上，看它是不是一条直线，再用最小二乘法拟合斜率。克劳塞特、沙利齐与纽曼指出，这种做法有严重的偏差：许多不是幂律的分布在双对数坐标上也近似直线，最小二乘的斜率估计也有偏。他们建议用最大似然估计指数，用拟合优度选择幂律开始成立的下限 ，并用似然比检验把幂律与对数正态等其他分布比较 (Clauset, Shalizi, and Newman 2009)。
证据
近千个网络的检验。 布罗伊多与克劳塞特用这套方法检验了来自社会、生物、技术、信息与交通等领域的近千个真实网络。按照他们定义的几个等级，只有约 4% 的网络显示出「最强」的无标度证据，52% 只有「最弱」的证据；在多数网络中，对数正态分布对度分布尾部的拟合与幂律一样好或更好。社会网络大多最多只是弱无标度的，部分技术与生物网络的证据较强 (Broido and Clauset 2019)。
证据
一场关于定义的争论。 这篇论文发表后引起了激烈的讨论。霍尔姆在同期的评论中总结说，分歧有相当一部分来自对「无标度」的不同理解：如果它指的是严格的幂律分布，那么它确实少见；如果它指的是度分布有很长的右尾、少数枢纽节点在结构与功能上举足轻重，那么它几乎无处不在，他的标题是「既罕见又无处不在」(Holme 2019)。
推导
用两组合成的「度」数据说明这个统计问题。BA：一个 20,000 个节点的巴拉巴西—阿尔伯特网络（每个新节点连接 2 个老节点），其尾部理论上是指数为 3 的幂律。LN：20,000 个对数正态随机数取整，不是幂律。对每组数据用最大似然估计不同 下的指数（离散近似），并在 处做幂律对对数正态的似然比检验（连续近似，对数正态用网格搜索拟合，报告伏翁检验的标准化比值 与双侧 值）。
# Is it a power law? Maximum-likelihood exponent and a likelihood-ratio test
# against a log-normal (in the spirit of Clauset, Shalizi & Newman 2009 and
# Broido & Clauset 2019). Two synthetic degree samples of 20,000 nodes:
# BA: a Barabasi-Albert network with m = 2 (true tail exponent 3);
# LN: rounded log-normal values exp(Normal(1.0, 0.8)), not a power law.
# Exponent: alpha = 1 + n / sum ln(k / (kmin - 0.5)) (discrete approximation).
# LR test: continuous approximation above kmin - 0.5; the log-normal is fitted
# by grid search (mu -24 to 4, sigma 0.2 to 4; the tail mass uses erfc, which
# stays accurate far out in the tail); Vuong's normalised ratio z and
# two-sided p are reported.
import math, random
from statistics import NormalDist
rng, PHI = random.Random(9), NormalDist().cdf
N, M = 20000, 2
targets, deg = [], [0] * N
for i in range(M + 1):
for j in range(i):
targets += [i, j]; deg[i] += 1; deg[j] += 1
for new in range(M + 1, N):
chosen = set()
while len(chosen) < M:
chosen.add(rng.choice(targets))
for t in chosen:
targets += [t, new]; deg[t] += 1; deg[new] += 1
samples = {"BA": deg,
"LN": [max(1, round(math.exp(rng.gauss(1.0, 0.8)))) for _ in range(N)]}
def alpha_hat(ks, kmin):
tail = [k for k in ks if k >= kmin]
a = 1 + len(tail) / sum(math.log(k / (kmin - 0.5)) for k in tail)
return a, (a - 1) / math.sqrt(len(tail)), len(tail)
def lr_test(ks, kmin):
x = [k for k in ks if k >= kmin]; xm = kmin - 0.5; n = len(x)
a = 1 + n / sum(math.log(v / xm) for v in x)
lp = [math.log((a - 1) / xm) - a * math.log(v / xm) for v in x]
lx = [math.log(v) for v in x]
def ln_ll(mu, s):
tailp = 0.5 * math.erfc((math.log(xm) - mu) / (s * math.sqrt(2)))
if tailp < 1e-300: return None
c = -math.log(s * math.sqrt(2 * math.pi)) - math.log(tailp)
return [c - l - (l - mu) ** 2 / (2 * s * s) for l in lx]
best = None
grid = [(mu / 4, s / 10) for mu in range(-96, 17) for s in range(2, 41)]
for mu, s in grid:
ll = ln_ll(mu, s)
if ll is not None and (best is None or sum(ll) > best[0]):
best = (sum(ll), mu, s, ll)
d = [p - q for p, q in zip(lp, best[3])]
R = sum(d); sd = math.sqrt(sum((v - R / n) ** 2 for v in d) / n)
z = R / (sd * math.sqrt(n))
return R, z, 2 * PHI(-abs(z)), best[1], best[2]
for name, ks in samples.items():
print(f"{name}: max value {max(ks)}")
for kmin in (2, 4, 8, 16):
a, se, n = alpha_hat(ks, kmin)
print(f" kmin {kmin:2d}: alpha = {a:.2f} +/- {se:.2f} (n tail = {n})")
R, z, p, mu, sig = lr_test(ks, 8)
if p >= 0.1:
verdict = "cannot tell them apart"
else:
verdict = "power law favoured" if z > 0 else "log-normal favoured"
print(f" kmin 8, power law vs log-normal: R = {R:+.1f}, z = {z:+.2f},"
f" p = {p:.3f}")
print(f" -> {verdict}; best log-normal mu = {mu:.2f}, sigma = {sig:.1f}")
# BA: max value 418
# kmin 2: alpha = 2.40 +/- 0.01 (n tail = 20000)
# kmin 4: alpha = 2.69 +/- 0.02 (n tail = 6002)
# kmin 8: alpha = 2.80 +/- 0.04 (n tail = 1630)
# kmin 16: alpha = 2.77 +/- 0.09 (n tail = 431)
# kmin 8, power law vs log-normal: R = -0.8, z = -0.63, p = 0.531
# -> cannot tell them apart; best log-normal mu = -12.00, sigma = 2.9
# LN: max value 57
# kmin 2: alpha = 2.09 +/- 0.01 (n tail = 15408)
# kmin 4: alpha = 2.77 +/- 0.02 (n tail = 7504)
# kmin 8: alpha = 3.60 +/- 0.06 (n tail = 2062)
# kmin 16: alpha = 4.56 +/- 0.21 (n tail = 301)
# kmin 8, power law vs log-normal: R = -32.0, z = -5.73, p = 0.000
# -> log-normal favoured; best log-normal mu = 1.00, sigma = 0.8结果有三点值得注意。第一，即使数据确实来自优先连接模型，指数的估计也随 变化： 时为 2.40， 时为 2.80，都低于理论值 3，因为有限规模的网络中尾部还没有完全形成。第二，对数正态数据在 时也给出 2.77 的「指数」，与 BA 数据几乎一样；只有把 逐步提高，才看到它的「指数」不断变大（3.60、4.56），暴露出它不是幂律。第三，似然比检验对对数正态数据给出了明确的结论（，偏向对数正态）；但对真正的 BA 数据，检验无法区分幂律与对数正态（，），最佳拟合的对数正态参数（、）说明它正在用一个极宽的分布模仿幂律。也就是说，在约 1,600 个尾部数据点的规模上，「无法拒绝幂律」并不等于「证明是幂律」；布罗伊多与克劳塞特的大量网络落在「弱证据」等级上，部分原因正在于此。
随机失效与定向攻击
无标度结构的一个重要推论与鲁棒性有关。
证据
失效与攻击。 阿尔伯特、Jeong 与巴拉巴西在 2000 年比较了无标度网络与度分布呈指数衰减的随机网络在节点被移除时的表现。随机移除节点（模拟故障）时，无标度网络（包括万维网与互联网的实际拓扑）表现出很强的耐受性，网络的直径几乎不变；但如果有针对性地优先移除连接最多的节点（模拟攻击），无标度网络会很快碎裂。指数型的随机网络在两种情形下表现相近 (Albert, Jeong, and Barabási 2000)。
推导
一个 2,000 个节点的 BA 网络（）和一个节点数、连带数都相同的随机网络（ER）。逐步移除一定比例的节点：随机移除（10 种随机顺序的平均）或按初始度从高到低移除（攻击），记录最大连通分量占原有节点的比例 。
# Error and attack tolerance (after Albert, Jeong & Barabasi 2000).
# A Barabasi-Albert network (N = 2000, each newcomer links to m = 2 existing
# nodes with probability proportional to degree) and an Erdos-Renyi network
# with the same number of nodes and ties. Nodes are removed either at random
# (failures; mean of 10 orders) or in order of initial degree, highest first
# (attack). S = share of the ORIGINAL nodes in the largest connected component.
import random
N, M = 2000, 2
def ba(rng):
edges, targets = set(), []
for i in range(M + 1): # small complete seed graph
for j in range(i):
edges.add((j, i)); targets += [i, j]
for new in range(M + 1, N):
chosen = set()
while len(chosen) < M:
chosen.add(rng.choice(targets))
for t in chosen:
edges.add((t, new)); targets += [t, new]
return list(edges)
def er(n_edges, rng):
edges = set()
while len(edges) < n_edges:
a, b = rng.randrange(N), rng.randrange(N)
if a != b: edges.add((min(a, b), max(a, b)))
return list(edges)
def giant(edges, removed):
par = list(range(N))
def find(x):
while par[x] != x:
par[x] = par[par[x]]; x = par[x]
return x
for a, b in edges:
if a not in removed and b not in removed:
ra, rb = find(a), find(b)
if ra != rb: par[ra] = rb
size = {}
for x in range(N):
if x not in removed:
r = find(x); size[r] = size.get(r, 0) + 1
return max(size.values(), default=0) / N
def curves(edges, fracs, rng, orders=10):
deg = [0] * N
for a, b in edges: deg[a] += 1; deg[b] += 1
attack = sorted(range(N), key=lambda v: (-deg[v], rng.random()))
rand = [rng.sample(range(N), N) for _ in range(orders)]
out = []
for f in fracs:
k = int(f * N)
r = sum(giant(edges, set(o[:k])) for o in rand) / orders
out.append((f, r, giant(edges, set(attack[:k]))))
return out, deg
if __name__ == "__main__":
rng = random.Random(8)
fracs = (0, 0.05, 0.1, 0.15, 0.2, 0.3, 0.4, 0.6, 0.7, 0.8, 0.9)
g_ba = ba(rng); g_er = er(len(g_ba), rng)
res_ba, d_ba = curves(g_ba, fracs, rng)
res_er, d_er = curves(g_er, fracs, rng)
for name, d in (("BA", d_ba), ("ER", d_er)):
k1 = sum(d) / N; k2 = sum(x * x for x in d) / N
print(f"{name}: {len(g_ba)} ties, mean degree {k1:.2f},"
f" max degree {max(d)}, <k^2>/<k> = {k2 / k1:.1f}")
print("removed BA random BA attack ER random ER attack")
for (f, a, b), (_, c, e) in zip(res_ba, res_er):
print(f" {f:4.0%} {a:5.2f} {b:5.2f} {c:5.2f} {e:5.2f}")
# BA: 3997 ties, mean degree 4.00, max degree 104, <k^2>/<k> = 11.6
# ER: 3997 ties, mean degree 4.00, max degree 13, <k^2>/<k> = 5.0
# removed BA random BA attack ER random ER attack
# 0% 1.00 1.00 0.98 0.98
# 5% 0.95 0.86 0.93 0.92
# 10% 0.89 0.63 0.87 0.85
# 15% 0.84 0.04 0.82 0.78
# 20% 0.78 0.01 0.76 0.69
# 30% 0.65 0.00 0.65 0.37
# 40% 0.52 0.00 0.53 0.06
# 60% 0.24 0.00 0.25 0.00
# 70% 0.11 0.00 0.08 0.00
# 80% 0.03 0.00 0.01 0.00
# 90% 0.01 0.00 0.00 0.00
攻击下的差别非常明显：按度从高到低移除 10% 的节点后，BA 网络的最大连通分量还剩 63%，移除 15% 后只剩 4%；同样的攻击对 ER 网络的影响要小得多，移除 15% 后还剩 78%，移除 40% 后才降到 6%。BA 网络中度最高的节点有 104 条连接，ER 网络中最多只有 13 条：攻击无标度网络，就是先拆掉那些把整个网络连在一起的枢纽。
但随机失效下的结果可能出人意料：在这个规模上，两种网络的表现几乎一样。随机移除 40% 的节点后，BA 网络剩 52%，ER 网络剩 53%；只有在移除 70% 以上时，BA 网络才略微好一些（70% 时 0.11 对 0.08）。原因可以用随机图理论中的一个经典判据理解。
推导
对按给定度分布随机连接的网络，存在巨连通分量的条件是 ；随机移除比例为 的节点后， 按 的比例缩小，由此得到临界比例
ER 网络的 ，；这个 BA 网络的 ，。两者的差别主要在高移除比例的一端。对于指数 的无限大无标度网络， 发散， 趋于 1，这就是「对随机失效极其稳健」的来源；但它是一个渐近结论，在有限规模、度的上限受限的网络中，优势要小得多。
所以，「无标度网络对故障稳健、对攻击脆弱」这句话的后一半在有限网络中非常可靠，前一半则在很大程度上依赖网络的规模与度分布尾部的形状。阿尔伯特等人当年主要用网络直径衡量鲁棒性，他们研究的万维网与互联网样本也比这里的模拟大得多。
注
用在人身上时。 在社会网络中，「移除节点」对应的是一个人离开、被排斥或被封禁。模型说明，少数联系极广的人对整个网络的连通有不成比例的作用；这一结论在公共卫生（例如优先为联系最多的人接种）与基础设施保护中有明确的用途。但它也可以被用来设计瓦解一个社群的策略。本书讨论这一模型，是为了理解网络的脆弱性，而不是为了提供针对任何人或群体的方法。
本章小结
优先连接模型能产生幂律的度分布，但判断真实数据是否服从幂律需要最大似然估计与对其他分布的比较；近千个网络的检验显示，强的无标度证据并不常见，争论的一部分来自对「无标度」的不同定义。程序显示，即使数据真的来自优先连接模型，在中等规模上也很难把幂律与对数正态区分开。无标度网络在定向攻击下非常脆弱；它对随机失效的稳健优势是一个渐近结论，在有限规模上很小。下一章讨论另一类位置指标：不只看一个人有多少连接，也看他连接的是谁。
参考文献
Fan, Y. (2026). Social Network Topology, Structural Holes and Complex Contagion: From the Strength of Weak Ties and Preferential Attachment to Information Cascades, Read Beside Classical Chinese Diplomacy [社会网络拓扑、结构洞与复杂传染的数学模型] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23764990 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).