5D Library › Collective Dynamics, Coupled-Oscillator Synchrony and Distributed Consensus · 中文

Chapter 5 DeGroot Consensus: Influence, Spectral Gap and the Wisdom of Crowds

Averaging again and again

The individuals of the first four chapters adjusted a phase or a direction; those of this chapter adjust a number — an estimate of some quantity, or an opinion. The simplest model is repeated weighted averaging. French in 1956 already proposed this structure in “a formal theory of social power” (French 1956); DeGroot in 1974 wrote it in the Journal of the American Statistical Association as a statistical model of “reaching a consensus”: nn people each hold an initial estimate, and in each round everyone replaces their estimate by a weighted average of everyone’s, the weights expressing how much they trust each person (DeGroot 1974).

Calculation

Model and limit. Let TT be row-stochastic (Tij≥0T_{ij} \ge 0, each row summing to 1) and p(t+1)=Tp(t)p(t+1) = T p(t), so that p(t)=Ttp(0)p(t) = T^t p(0). If the directed graph of trust relations is strongly connected and aperiodic, then Tt→𝟏π⊤T^t \to \mathbf{1}\pi^{\top}, where π\pi is the left eigenvector of TT for eigenvalue 1 (π⊤T=π⊤\pi^{\top}T = \pi^{\top}, ∑iπi=1\sum_i\pi_i = 1). Everyone converges to the same value p∞=∑iπipi(0),p_\infty = \sum_i \pi_i\, p_i(0), and πi\pi_i is the influence of person ii (Golub and Jackson 2010). Aperiodicity is necessary: if two people swap opinions each round and neither keeps their own, the estimates swing back and forth for ever.

Speed of convergence. If TT is diagonalisable with eigenvalues ordered by modulus 1=|λ1|>|λ2|≥…1 = |\lambda_1| > |\lambda_2| \ge \dots, then ∥p(t)−p∞𝟏∥≤C|λ2|t,\|p(t) – p_\infty\mathbf{1}\| \le C\,|\lambda_2|^{t}, so disagreement shrinks geometrically at rate |λ2||\lambda_2|, faster the larger the spectral gap 1−|λ2|1 – |\lambda_2|. This is an asymptotic rate; the constant CC depends on how the initial opinions load on the different modes. On an undirected network with Tij=1/(di+1)T_{ij} = 1/(d_i + 1) (equal weight on oneself and each neighbour), TT is a reversible Markov chain and the influence has the explicit form πi=(di+1)/∑j(dj+1)\pi_i = (d_i + 1)/\sum_j(d_j + 1): influence is proportional to “how many people listen”.

The framework’s “spectral gap 1−|λ2|1 – |\lambda_2| as the rate of convergence” is right, with two caveats: it requires TT to be aperiodic (otherwise |λ2|=1|\lambda_2| = 1), and it describes the long-run rate; convergence in the first few rounds can be much faster. In continuous-time consensus protocols the corresponding quantity is the second-smallest eigenvalue of the Laplacian (the algebraic connectivity) (Olfati-Saber et al. 2007).

The program compares six networks of 21 people: the complete graph, a ring in which each person links to one neighbour on each side, a ring with two on each side, that ring plus 6 random shortcuts, two complete cliques joined by a single edge, and a star. Using the Jacobi method of Chapter 2 on the symmetrised matrix D1/2TD−1/2D^{1/2}TD^{-1/2}, it reports the largest influence max⁡iπi\max_i\pi_i, the effective number Neff=1/∑iπi2N_{\mathrm{eff}} = 1/\sum_i\pi_i^2, |λ2||\lambda_2|, the spectral gap and “the number of rounds for |λ2|t|\lambda_2|^t to fall to 1/100”, and simulates, from five random sets of initial opinions, the number of rounds for the disagreement (maximum minus minimum) to fall to 1 % of its initial value.

Calculation

# 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)

Two conclusions follow. First, fast and accurate are different things. Apart from the complete graph, which converges in one round, the star converges fastest (|λ2|=0.5|\lambda_2| = 0.5, about 7 rounds), but its centre has influence 0.344 and the effective number is only 7.1; the ring with one neighbour on each side has perfectly equal influence (effective number 21.0), but |λ2|=0.9704|\lambda_2| = 0.9704, so the asymptotic rate implies 154 rounds and the simulation needs 104.6 on average. Second, a structural “bottleneck” makes convergence very slow: with two cliques joined by one edge the influence is almost equal (0.054), but |λ2|=0.9846|\lambda_2| = 0.9846; the asymptotic rate implies 297 rounds and the simulation needs 152.2 on average — each clique agrees internally very quickly while the two cliques stay apart for a long time. The simulated numbers of rounds are all smaller than those predicted from |λ2||\lambda_2|, because random initial opinions do not load entirely on the slowest mode. Six shortcuts cut the ring’s convergence from 51 rounds (predicted) to 27, while raising the largest influence only from 0.048 to 0.060.

Left: root-mean-square error of the consensus against the number of people N for four kinds of network (log scales; independent signals with standard deviation 1). The ring’s error is 1/\sqrt{N}; the network with about \sqrt{N} hubs also tends to 0, more slowly; the “3 elites” and star networks do not improve with size. Right: decay of disagreement over rounds in five networks of 21 people (log scale); the two cliques with one bridge drop quickly in the first round and then stay for a long time at the disagreement between the cliques.

When is a crowd wise

Golub and Jackson asked in 2010: if each person’s initial estimate is the truth plus independent noise, does the consensus after repeated averaging approach the truth as the number of people grows? They call such a sequence of networks “wise” and prove that a sequence of networks is wise if and only if the largest influence max⁡iπi\max_i\pi_i tends to 0 as the population grows (Golub and Jackson 2010). The premise is that signals are independent, centred on the truth, and have variances bounded below by a positive number. They also give a characterisation — there is no “prominent family” of bounded size whose influence stays bounded away from zero — and sufficient conditions, “balance” and “minimal out-dispersion”. They stress that the speed of convergence and wisdom are unrelated: every combination of speed and accuracy is realised by some network. Golub and Jackson showed in 2012 that homophily (people interacting mainly with similar others) slows the formation of consensus, while the density of the network does not affect that speed (Golub and Jackson 2012).

The error of the consensus is ∑iπiei\sum_i\pi_i e_i; if individual noises are independent with variance 1, its root-mean-square value is ∑iπi2=1/Neff\sqrt{\sum_i\pi_i^2} = 1/\sqrt{N_{\mathrm{eff}}}; if person ii carries a systematic bias bb, the consensus shifts by πib\pi_i b. The program computes the error for four kinds of network (a ring with two neighbours on each side; about N\sqrt{N} mutually linked hubs, each with its own leaves; 3 “elites” linked to everyone plus a ring; a star) for populations from 11 to 10,001, and checks the transmission of bias with 4,000 Monte Carlo draws.

Calculation

# 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

In the ring everyone has the same degree, influence is perfectly equal, and the error is exactly 1/N1/\sqrt{N}, falling from 0.302 with 11 people to 0.010 with 10,001. In the network of N\sqrt{N} hubs the largest influence falls from 0.182 to 0.005 and the error to 0.050 — it is wise, only slower than the ring. In the network with 3 elites the largest influence stays at 0.111 and the error at about 0.193; in the star the centre’s influence tends to 1/3 and the error stays at 0.333. Neither of the last two is wise: however much the population grows, the error no longer falls. The transmission of bias matches the formula: in the ring, an ordinary member with bias +1+1 shifts the consensus of 21 people by only 0.048 (simulated 0.046) and of 101 people by 0.010 (simulated 0.008); in the star, a centre with the same bias shifts it by 0.344 (simulated 0.341) and 0.336 (simulated 0.331), hardly shrinking with size.

DeMarzo, Vayanos and Zwiebel reached a related conclusion from another angle in 2003: if people fail to recognise that the information they hear repeatedly comes from the same source (“persuasion bias”), a person’s influence depends on their position in the network, not only on how accurate their information is (DeMarzo et al. 2003). In the model of Friedkin and Johnsen in 1990, everyone always keeps part of their initial opinion (“stubbornness”), and then the group generally does not reach full agreement (Friedkin and Johnsen 1990).

Do people really update this way

Evidence

Experimental evidence on DeGroot-style updating. Chandrasekhar, Larreguy and Xandri reported two network-learning experiments in Econometrica in 2020: 665 villagers in India and 350 students at ITAM in Mexico guessed again after seeing their network neighbours’ previous guesses. Structural estimation showed that about 10 % of the village sample and about 50 % of the student sample updated like Bayesian learners, and the rest behaved more like DeGroot-style averagers or majority followers (Chandrasekhar et al. 2020).

Evidence

Network structure and group estimates. In the experiments of Lorenz, Rauhut, Schweitzer and Helbing in 2011, letting participants see others’ estimates reduced the diversity of estimates without a corresponding gain in the group’s accuracy; social influence can undermine the wisdom of crowds (Lorenz et al. 2011). Becker, Brackbill and Centola in 2017 had 1,360 online participants estimate quantities in three rounds (the first independent, the next two after seeing the mean estimate of their neighbours), comparing decentralised and centralised networks of 40 people (Becker et al. 2017). In decentralised networks the error of the group’s mean estimate fell from 0.69 to 0.62 standard deviations (about 10 %), individual error fell by 23 % and the diversity of estimates by 43 %. In centralised networks the result depended on the central person: when that person’s initial estimate lay on the side of the truth (12 trials), the error of the mean estimate fell by 43 % (from 0.56 to 0.32 standard deviations); when it lay away from the truth (13 trials), the error rose by 19 %. Overall, social influence did not reliably improve group estimates in centralised networks. They also found that the more accurate people revised less (the correlation between the size of revision and initial error was 0.41), which allowed the group mean in decentralised networks to become more accurate.

The results of Becker and colleagues agree with the theory of Golub and Jackson and add a mechanism the theory lacks: if “stubbornness” is related to accuracy, repeated averaging can improve a group’s estimate rather than merely preserving its mean. Volume 26 has already discussed the diversity prediction theorem and why correlated errors weaken the wisdom of crowds, and that is not repeated here.

Hypothesis · not established · A central person’s bias is transmitted in proportion to influence

The author’s conjecture: in real small-group numerical estimation tasks, if each person’s influence πi\pi_i is approximated by “how many people see their estimate”, the effect of a central person’s systematic bias on the group’s final estimate is about πi\pi_i times the bias, minus the part of the noise removed because everyone is pulled together (the program in Chapter 8 shows that the latter is not negligible). The Chapter 8 trial can test the direction of this conjecture: if centralised and decentralised structures, with the same bias on the central seat, give no difference in final error, the conjecture is wrong.

Summary

In the DeGroot model a strongly connected aperiodic network always reaches consensus, and the consensus is the influence-weighted average π\pi of initial opinions; disagreement decays like |λ2|t|\lambda_2|^t, and the spectral gap describes only the asymptotic rate. Golub and Jackson proved that a crowd is wise if and only if the largest influence tends to 0 as the population grows, and that speed and wisdom are unrelated. Stars and “elite” networks converge fast but are not wise, and the central person’s bias is passed to the whole group in proportion to influence. Experiments show that most people update close to DeGroot averaging; whether social influence improves estimates in centralised networks depends on whether the central person deviates from the truth. The next chapter asks what happens when people listen only to opinions close to their own.

References

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).