5D Library › 集群动力学、耦合振子同步与分布式共识的数学模型 · English

第五章 德格鲁特共识:影响力、谱隙与群体智慧

反复取平均

前四章的个体调整的是相位或方向;本章的个体调整的是一个数——对某个量的估计或意见。最简单的模型是反复取加权平均。弗伦奇 1956 年在「社会权力的形式理论」中已经提出了这种结构 (French 1956);德格鲁特 1974 年在《美国统计学会会刊》上把它写成一个关于「达成共识」的统计模型:nn 个人各有一个初始估计,每一轮每个人把自己的估计换成所有人估计的加权平均,权重表示他对各人的信任 (DeGroot 1974)。

推导

模型与极限。 设 TT 为行随机矩阵(Tij≥0T_{ij} \ge 0,每行之和为 1),p(t+1)=Tp(t)p(t+1) = T p(t),于是 p(t)=Ttp(0)p(t) = T^t p(0)。若信任关系构成的有向图强连通且非周期,则 Tt→𝟏π⊤T^t \to \mathbf{1}\pi^{\top},其中 π\pi 是 TT 对应特征值 1 的左特征向量(π⊤T=π⊤\pi^{\top}T = \pi^{\top},∑iπi=1\sum_i\pi_i = 1)。所有人收敛到同一个值 p∞=∑iπipi(0),p_\infty = \sum_i \pi_i\, p_i(0), πi\pi_i 就是第 ii 个人的影响力 (Golub and Jackson 2010)。非周期是必要的:两个人每轮互换意见、都不保留自己的意见时,估计会永远来回摆动。

收敛速度。 若 TT 可对角化,特征值按模排列为 1=|λ1|>|λ2|≥…1 = |\lambda_1| > |\lambda_2| \ge \dots,则 ∥p(t)−p∞𝟏∥≤C|λ2|t,\|p(t) – p_\infty\mathbf{1}\| \le C\,|\lambda_2|^{t}, 分歧以 |λ2||\lambda_2| 的速率按几何级数缩小,谱隙 1−|λ2|1 – |\lambda_2| 越大越快。这是渐近速率,常数 CC 取决于初始意见在各个模态上的分量。在无向网络上,令 Tij=1/(di+1)T_{ij} = 1/(d_i + 1)(对自己与每个邻居等权),TT 是可逆的马尔可夫链,影响力有显式解 πi=(di+1)/∑j(dj+1)\pi_i = (d_i + 1)/\sum_j(d_j + 1),即影响力与「被多少人听」成正比。

框架中的「谱隙 1−|λ2|1 – |\lambda_2| 收敛速率」是对的,但要注意两点:它要求 TT 非周期(否则 |λ2|=1|\lambda_2| = 1),而且它描述的是长期速率,前几轮的收敛可能快得多。连续时间的共识协议中,对应的量是拉普拉斯矩阵的第二小特征值(代数连通度)(Olfati-Saber et al. 2007)。

程序比较六种 21 人的网络:完全图、每人连左右各 1 人的环、各 2 人的环、加 6 条随机捷径的环、两个完全子团之间只有一条边、星形。用第二章的雅可比方法求对称化矩阵 D1/2TD−1/2D^{1/2}TD^{-1/2} 的特征值,给出最大影响力 max⁡iπi\max_i\pi_i、有效人数 Neff=1/∑iπi2N_{\mathrm{eff}} = 1/\sum_i\pi_i^2、|λ2||\lambda_2|、谱隙,以及「|λ2|t|\lambda_2|^t 降到 1/100 所需的轮数」,并用 5 组随机初始意见模拟分歧(最大值减最小值)降到初始 1% 所需的轮数。

推导

# DeGroot (1974) averaging p(t+1) = T p(t) on undirected graphs with self-loops,
# T_ij = 1/(d_i + 1) for j = i or j ~ i. Then T is reversible: pi_i = (d_i + 1)/sum(d + 1)
# is the left unit eigenvector (influence), the consensus is sum_i pi_i p_i(0), and
# disagreement shrinks like |lambda_2|^t, lambda_2 = largest-modulus eigenvalue below 1.
import math, random

def jacobi_eigs(S, sweeps=60):
    a = [row[:] for row in S]; n = len(a)
    for _ in range(sweeps):
        if sum(a[i][j] ** 2 for i in range(n) for j in range(n) if i != j) < 1e-22: break
        for p in range(n - 1):
            for q in range(p + 1, n):
                if abs(a[p][q]) < 1e-15: continue
                t = (a[q][q] - a[p][p]) / (2 * a[p][q])
                t = (1 if t >= 0 else -1) / (abs(t) + math.sqrt(t * t + 1))
                c = 1 / math.sqrt(t * t + 1); s = t * c
                for k in range(n):
                    u, v = a[k][p], a[k][q]
                    a[k][p], a[k][q] = c * u - s * v, s * u + c * v
                for k in range(n):
                    u, v = a[p][k], a[q][k]
                    a[p][k], a[q][k] = c * u - s * v, s * u + c * v
    return sorted(a[i][i] for i in range(n))

def ring(n, k=1):
    return [{(i + s) % n for s in range(-k, k + 1) if s} for i in range(n)]

def networks(n=21):
    rng = random.Random(3); sw = ring(n, 2)
    for _ in range(6):
        i, j = rng.sample(range(n), 2); sw[i].add(j); sw[j].add(i)
    two = [{j for j in range(n) if j != i and (j < 10) == (i < 10)} for i in range(n)]
    two[0].add(10); two[10].add(0)              # two cliques (10 and 11) and one bridge
    return [("complete", [set(range(n)) - {i} for i in range(n)]), ("ring k=1", ring(n)),
            ("ring k=2", ring(n, 2)), ("ring k=2 + 6 shortcuts", sw),
            ("two cliques + 1 bridge", two),
            ("star", [set(range(1, n))] + [{0}] * (n - 1))]

def rounds_to_one_percent(adj, rng):
    p = [rng.random() for _ in adj]; s0 = max(p) - min(p)
    for t in range(1, 100000):
        p = [(p[i] + sum(p[j] for j in nb)) / (len(nb) + 1) for i, nb in enumerate(adj)]
        if max(p) - min(p) < 0.01 * s0: return t

if __name__ == "__main__":
    rng = random.Random(1974)
    print("network (N = 21)        max pi  N_eff=1/sum pi^2  |lam_2|    gap   predicted"
          " simulated")
    for name, adj in networks():
        w = [len(nb) + 1 for nb in adj]; pi = [x / sum(w) for x in w]
        S = [[(1 if (j in adj[i] or i == j) else 0) / math.sqrt(w[i] * w[j])
              for j in range(len(adj))] for i in range(len(adj))]
        lam = jacobi_eigs(S); l2 = max(abs(lam[0]), abs(lam[-2]))
        pred = 1 if l2 < 1e-12 else math.ceil(math.log(100) / -math.log(l2))
        sim = sum(rounds_to_one_percent(adj, rng) for _ in range(5)) / 5
        print(f"{name:24s}  {max(pi):.3f}      {1 / sum(x * x for x in pi):5.1f}"
              f"         {l2:.4f}  {1 - l2:.4f}    {pred:4d}    {sim:7.1f}")
    print("predicted = rounds for |lam_2|^t to fall to 1/100; simulated = rounds until")
    print("the spread max - min falls below 1 % of its start (mean of 5 random starts)")
# network (N = 21)        max pi  N_eff=1/sum pi^2  |lam_2|    gap   predicted simulated
# complete                  0.048       21.0         0.0000  1.0000       1        1.0
# ring k=1                  0.048       21.0         0.9704  0.0296     154      104.6
# ring k=2                  0.048       21.0         0.9127  0.0873      51       29.8
# ring k=2 + 6 shortcuts    0.060       20.6         0.8429  0.1571      27       16.8
# two cliques + 1 bridge    0.054       20.9         0.9846  0.0154     297      152.2
# star                      0.344        7.1         0.5000  0.5000       7        7.0
# predicted = rounds for |lam_2|^t to fall to 1/100; simulated = rounds until
# the spread max - min falls below 1 % of its start (mean of 5 random starts)

两点结论。第一,快与准是两回事。除了一轮就收敛的完全图,星形网络收敛最快(|λ2|=0.5|\lambda_2| = 0.5,约 7 轮),但中心一人的影响力为 0.344,有效人数只有 7.1;只连左右各 1 人的环影响力完全平均(有效人数 21.0),但 |λ2|=0.9704|\lambda_2| = 0.9704,按渐近速率要 154 轮,模拟平均 104.6 轮。第二,结构上的「瓶颈」使收敛极慢:两个子团之间只有一条边时,影响力几乎平均(0.054),但 |λ2|=0.9846|\lambda_2| = 0.9846,按渐近速率要 297 轮,模拟平均 152.2 轮——两团内部各自很快达成一致,团与团之间却长期保持分歧。模拟的轮数都少于按 |λ2||\lambda_2| 预测的轮数,因为随机初始意见并不全部落在最慢的模态上。加 6 条捷径就把环的收敛从 51 轮(预测)降到 27 轮,而最大影响力只从 0.048 升到 0.060。

左:四类网络中共识的均方根误差随人数 N 的变化(对数坐标;各人信号独立,标准差为 1)。环形网络的误差为 1/\sqrt{N};约 \sqrt{N} 个枢纽的网络误差也趋于 0,但较慢;3 个「精英」与星形网络的误差不随人数下降。右:五种 21 人网络中分歧随轮数的衰减(对数坐标);两个子团加一条桥的网络在一轮之后迅速下降,然后长期停在团与团之间的分歧上。

群体什么时候是明智的

戈卢布与杰克逊 2010 年问:如果每个人的初始估计是真值加上独立的噪声,反复取平均之后的共识会不会随着人数增加而趋于真值?他们把这样的一列网络称为「明智的」(wise),并证明:一列网络是明智的,当且仅当其中最大影响力 max⁡iπi\max_i\pi_i 随人数趋于 0 (Golub and Jackson 2010)。这里的前提是各人信号独立、均值为真值、方差有正的下界。他们还给出了判别条件:不存在有限人数而影响力始终有下界的「显要家族」(prominent family);以及充分条件「平衡」与「最小外部分散」。他们特别指出,收敛的快慢与是否明智彼此无关:任何快慢与准确度的组合都有网络可以实现。戈卢布与杰克逊 2012 年进一步说明,同质性(人们主要与相似的人交往)会减慢共识的形成,而网络的稠密程度不影响这个速度 (Golub and Jackson 2012)。

共识的误差为 ∑iπiei\sum_i\pi_i e_i,若各人噪声独立、方差为 1,其均方根为 ∑iπi2=1/Neff\sqrt{\sum_i\pi_i^2} = 1/\sqrt{N_{\mathrm{eff}}};若第 ii 个人带有系统偏差 bb,共识就偏移 πib\pi_i b。程序对四类网络(每人连左右各 2 人的环;约 N\sqrt{N} 个彼此相连的枢纽各带一批叶子;3 个与所有人相连的「精英」加一个环;星形)计算人数从 11 到 10,001 时的误差,并用 4,000 次蒙特卡罗模拟检验偏差的传递。

推导

# Wisdom of crowds under DeGroot averaging (Golub & Jackson 2010): signals s_i = mu + e_i,
# e_i iid, variance 1; consensus = sum_i pi_i s_i, so its RMS error is sqrt(sum pi_i^2)
# and a bias b carried by node i shifts it by pi_i * b. Undirected graphs with self-loops:
# pi_i = (d_i + 1) / sum_j (d_j + 1). Wise iff max_i pi_i -> 0 as N grows.
import math, random

def pis(deg):
    w = [d + 1 for d in deg]; t = sum(w); return [x / t for x in w]

def degrees(kind, n):
    if kind == "star":                       # one hub linked to everyone
        return [n - 1] + [1] * (n - 1)
    if kind == "ring k=2":
        return [4] * n
    if kind == "3 elites":                   # 3 nodes linked to all; the rest form a ring
        return [n - 1] * 3 + [2 + 3] * (n - 3)
    if kind == "sqrt-hubs":     # h = round(sqrt n) hubs, all linked, each with own leaves
        h = round(math.sqrt(n)); q, r = divmod(n - h, h)
        return [h - 1 + q + (k < r) for k in range(h)] + [1] * (n - h)
    raise ValueError(kind)

def mc_check(kind, n, rng, draws=4000, bias=1.0):
    pi = pis(degrees(kind, n)); e1 = e2 = 0.0
    for _ in range(draws):
        x = sum(p * rng.gauss(0, 1) for p in pi) + pi[0] * bias
        e1 += x; e2 += x * x
    return e1 / draws, math.sqrt(e2 / draws - (e1 / draws) ** 2)

if __name__ == "__main__":
    kinds = ("ring k=2", "sqrt-hubs", "3 elites", "star")
    print("RMS error of the consensus (signal SD 1); max pi in brackets")
    print("     N " + "".join(f"{k:>17s}" for k in kinds) + "   1/sqrt(N)")
    for n in (11, 31, 101, 301, 1001, 10001):
        cells = []
        for k in kinds:
            pi = pis(degrees(k, n))
            cells.append(f"{math.sqrt(sum(p * p for p in pi)):.3f} [{max(pi):.3f}]")
        print(f"{n:6d} " + "".join(f"{c:>17s}" for c in cells) + f"     {n ** -0.5:.3f}")
    print("node 0 (the hub, or an ordinary node in the ring) adds a bias b = +1:")
    rng = random.Random(2010)
    for k in ("ring k=2", "star"):
        for n in (21, 101):
            m, sd = mc_check(k, n, rng)
            print(f"   {k:9s} N = {n:3d}: theory shift {pis(degrees(k, n))[0]:.3f},"
                  f" simulated mean error {m:+.3f}, SD {sd:.3f}")
# RMS error of the consensus (signal SD 1); max pi in brackets
#      N          ring k=2        sqrt-hubs         3 elites             star   1/sqrt(N)
#     11     0.302 [0.091]    0.344 [0.182]    0.315 [0.136]    0.409 [0.355]     0.302
#     31     0.180 [0.032]    0.242 [0.099]    0.239 [0.119]    0.361 [0.341]     0.180
#    101     0.100 [0.010]    0.170 [0.054]    0.207 [0.113]    0.342 [0.336]     0.100
#    301     0.058 [0.003]    0.125 [0.030]    0.198 [0.112]    0.336 [0.334]     0.058
#   1001     0.032 [0.001]    0.091 [0.016]    0.194 [0.111]    0.334 [0.334]     0.032
#  10001     0.010 [0.000]    0.050 [0.005]    0.193 [0.111]    0.333 [0.333]     0.010
# node 0 (the hub, or an ordinary node in the ring) adds a bias b = +1:
#    ring k=2  N =  21: theory shift 0.048, simulated mean error +0.046, SD 0.216
#    ring k=2  N = 101: theory shift 0.010, simulated mean error +0.008, SD 0.099
#    star      N =  21: theory shift 0.344, simulated mean error +0.341, SD 0.382
#    star      N = 101: theory shift 0.336, simulated mean error +0.331, SD 0.336

环形网络各人的度相同,影响力完全平均,误差恰为 1/N1/\sqrt{N},从 11 人的 0.302 降到 10,001 人的 0.010。N\sqrt{N} 个枢纽的网络中最大影响力从 0.182 降到 0.005,误差也降到 0.050——它是明智的,只是比环慢。3 个精英的网络中最大影响力停在 0.111,误差停在约 0.193;星形网络的中心影响力趋于 1/3,误差停在 0.333。后两者都不明智:人数增加多少,误差都不会再下降。偏差的传递与公式一致:环形网络中一个普通成员带有偏差 +1+1 时,21 人的共识只偏移 0.048(模拟 0.046),101 人时 0.010(模拟 0.008);星形网络中中心带有同样的偏差时,共识偏移 0.344(模拟 0.341)与 0.336(模拟 0.331),几乎不随人数缩小。

德马尔佐、瓦亚诺斯与兹维贝尔 2003 年从另一个角度得到相近的结论:如果人们没有意识到自己反复听到的信息来自同一来源(「说服偏差」),一个人的影响力就取决于他在网络中的位置,而不仅是他的信息有多准确 (DeMarzo et al. 2003)。弗里德金与约翰森 1990 年的模型让每个人始终保留一部分初始意见(「固执」),这时群体一般不会完全达成一致 (Friedkin and Johnsen 1990)。

人们真的这样更新吗

证据

德格鲁特式更新的实验证据。 钱德拉塞卡、拉雷吉与桑德里 2020 年在《计量经济学》上报告了两项网络学习实验:665 名印度村民与 350 名墨西哥 ITAM 大学的学生,在看到网络邻居的上一轮猜测后再作猜测。结构估计表明,村民样本中约 10% 的人像贝叶斯学习者那样更新,学生样本中约 50%,其余的人更接近德格鲁特式的平均或跟随多数 (Chandrasekhar et al. 2020)。

证据

网络结构与群体估计。 洛伦茨、劳胡特、施魏策尔与黑尔宾 2011 年的实验发现,让参与者看到他人的估计后,估计的多样性下降,而群体的准确度并没有相应提高,社会影响可能削弱群体智慧 (Lorenz et al. 2011)。贝克尔、布拉克比尔与森托拉 2017 年让 1,360 名在线参与者分三轮估计数量(第一轮独立,后两轮看到邻居的平均估计),比较 40 人的去中心化网络与中心化网络 (Becker et al. 2017)。去中心化网络中,群体平均估计的误差从 0.69 个标准差降到 0.62(约 10%),个人误差下降 23%,估计的多样性下降 43%。中心化网络的结果取决于中心人物:中心人物的初始估计偏向真值的一侧时(12 次试验),平均估计的误差下降 43%(0.56 降到 0.32 个标准差);偏离真值时(13 次),误差上升 19%。总体而言,中心化网络中社会影响并没有可靠地改善群体估计。他们还发现,估计越准的人修改得越少(修改幅度与初始误差的相关系数为 0.41),这使去中心化网络的群体平均也能变准。

贝克尔等人的结果与戈卢布—杰克逊的理论一致,也补充了一个理论中没有的机制:如果「固执程度」与准确度相关,反复平均可以改善群体估计,而不只是保持平均值不变。第 26 本已经讨论过多样性预测定理与相关误差为什么会削弱群体智慧,这里不再重复。

假说 · 尚未验证 · 中心人物的偏差按影响力传递

作者的推测:在真实的小组数值估计任务中,若用「被多少人看到」近似每个人的影响力 πi\pi_i,那么中心人物的系统偏差对小组最终估计的影响,约等于 πi\pi_i 乘以这个偏差,再减去由于大家被拉近而减少的那部分噪声(第八章的程序显示后一部分不可忽略)。第八章的试验可以检验这一推测的方向:若中心化结构与去中心化结构在中心席位带有相同偏差时最终误差没有差别,推测就是错的。

本章小结

德格鲁特模型中,强连通且非周期的网络必然达成共识,共识是初始意见按影响力 π\pi 的加权平均;分歧按 |λ2|t|\lambda_2|^t 衰减,谱隙只描述渐近速率。戈卢布与杰克逊证明,群体明智当且仅当最大影响力随人数趋于 0;收敛快慢与是否明智无关。星形与「精英」网络收敛快却不明智,中心人物的偏差按其影响力传递给整个群体。实验表明多数人的更新接近德格鲁特式平均;中心化网络中的社会影响能否改善估计,取决于中心人物是否偏离真值。下一章讨论人们只听取与自己相近的意见时会发生什么。

参考文献

Becker, Joshua, Devon Brackbill, and Damon Centola. 2017. “Network Dynamics of Social Influence in the Wisdom of Crowds.” Proceedings of the National Academy of Sciences 114 (26): E5070–76. https://doi.org/10.1073/pnas.1615978114.
Chandrasekhar, Arun G., Horacio Larreguy, and Juan Pablo Xandri. 2020. “Testing Models of Social Learning on Networks: Evidence from Two Experiments.” Econometrica 88 (1): 1–32. https://doi.org/10.3982/ECTA14407.
DeGroot, Morris H. 1974. “Reaching a Consensus.” Journal of the American Statistical Association 69 (345): 118–21. https://doi.org/10.2307/2285509.
DeMarzo, Peter M., Dimitri Vayanos, and Jeffrey Zwiebel. 2003. “Persuasion Bias, Social Influence, and Unidimensional Opinions.” The Quarterly Journal of Economics 118 (3): 909–68.
French, John R. P. 1956. “A Formal Theory of Social Power.” Psychological Review 63: 181–94.
Friedkin, Noah E., and Eugene C. Johnsen. 1990. “Social Influence and Opinions.” The Journal of Mathematical Sociology 15: 193–206. https://doi.org/10.1080/0022250X.1990.9990069.
Golub, Benjamin, and Matthew O. Jackson. 2010. “Naïve Learning in Social Networks and the Wisdom of Crowds.” American Economic Journal: Microeconomics 2 (1): 112–49. https://doi.org/10.1257/mic.2.1.112.
Golub, Benjamin, and Matthew O. Jackson. 2012. “How Homophily Affects the Speed of Learning and Best-Response Dynamics.” The Quarterly Journal of Economics 127 (3): 1287–338. https://doi.org/10.1093/qje/qjs021.
Lorenz, Jan, Heiko Rauhut, Frank Schweitzer, and Dirk Helbing. 2011. “How Social Influence Can Undermine the Wisdom of Crowd Effect.” Proceedings of the National Academy of Sciences 108 (22): 9020–25. https://doi.org/10.1073/pnas.1008636108.
Olfati-Saber, Reza, J. Alex Fax, and Richard M. Murray. 2007. “Consensus and Cooperation in Networked Multi-Agent Systems.” Proceedings of the IEEE 95 (1): 215–33.

Fan, Y. (2026). Collective Dynamics, Coupled-Oscillator Synchrony and Distributed Consensus: From the Kuramoto Phase Transition and Vicsek Flocking to DeGroot Spectral Convergence, Read Beside Classical Chinese Thought on Harmony and Conformity [集群动力学、耦合振子同步与分布式共识的数学模型] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23828063 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).