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”: 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 be row-stochastic (, each row summing to 1) and , so that . If the directed graph of trust relations is strongly connected and aperiodic, then , where is the left eigenvector of for eigenvalue 1 (, ). Everyone converges to the same value and is the influence of person (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 is diagonalisable with eigenvalues ordered by modulus , then so disagreement shrinks geometrically at rate , faster the larger the spectral gap . This is an asymptotic rate; the constant depends on how the initial opinions load on the different modes. On an undirected network with (equal weight on oneself and each neighbour), is a reversible Markov chain and the influence has the explicit form : influence is proportional to “how many people listen”.
The framework’s “spectral gap as the rate of convergence” is right, with two caveats: it requires to be aperiodic (otherwise ), 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 , it reports the largest influence , the effective number , , the spectral gap and “the number of rounds for 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 (, 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 , 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 ; 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 , 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.
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 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 ; if individual noises are independent with variance 1, its root-mean-square value is ; if person carries a systematic bias , the consensus shifts by . The program computes the error for four kinds of network (a ring with two neighbours on each side; about 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.336In the ring everyone has the same degree, influence is perfectly equal, and the error is exactly , falling from 0.302 with 11 people to 0.010 with 10,001. In the network of 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 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 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 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 of initial opinions; disagreement decays like , 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
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).