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

Chapter 3 Self-Propelled Particles and the Three-Zone Model: Noise, Alignment and Collective Memory

From computer animation to statistical physics

Flocks of birds and schools of fish have no conductor, yet they turn together. The first computational models came from two lines of work: Aoki in 1982 simulated fish schools with three rules — repulsion, parallel orientation and attraction (Aoki 1982); Reynolds in 1987 designed “boids” for computer animation, in which three local rules — separation, alignment and cohesion — produced lifelike group motion (Reynolds 1987). The two lines later merged into the two models of this chapter: the self-propelled particle model of Vicsek and colleagues in 1995, which keeps only the rule of alignment and is used to study the order–disorder transition under noise; and the three-zone model of Couzin and colleagues in 2002, which keeps all three rules and is used to study the different forms a group can take. The review by Vicsek and Zafeiris in 2012 summarises the large body of later work (Vicsek and Zafeiris 2012).

The Vicsek model

Calculation

The model. NN particles move at constant speed v0v_0 in a periodic box of side LL. At each step the direction of particle ii becomes the average direction of all particles (itself included) within radius 1, plus a random perturbation uniform on [−η/2,η/2][-\eta/2, \eta/2]: θi(t+1)=arg⁡(∑|xj−xi|<1eiθj(t))+Δθi,xi(t+1)=xi(t)+v0eiθi(t+1).\theta_i(t+1) = \arg\left(\sum_{\lvert x_j – x_i\rvert < 1} e^{i\theta_j(t)}\right) + \Delta\theta_i, \qquad x_i(t+1) = x_i(t) + v_0 e^{i\theta_i(t+1)}. The order parameter is the normalised magnitude of the average velocity, va=|∑ieiθi|/Nv_a = |\sum_i e^{i\theta_i}|/N. The control parameters are the noise η\eta and the density ρ=N/L2\rho = N/L^2 (Vicsek et al. 1995).

Vicsek and colleagues found that when the noise is below, or the density above, a critical value, the particles spontaneously move in a common direction and vav_a is clearly above 0; they first reported this as a continuous transition similar to an equilibrium phase transition. Two important corrections followed. First, in the two-dimensional equilibrium XY model a continuous symmetry cannot break spontaneously (there is no true long-range order); Toner and Tu showed in 1995 with a hydrodynamic theory that self-propelled particles, which align while they move and so carry information with them, can develop true long-range order even in two dimensions (Toner and Tu 1995). Second, Grégoire and Chaté showed in 2004, using much larger systems, that the transition in two dimensions is in fact discontinuous (first order), with density bands appearing near the transition and cohesion being lost (Grégoire and Chaté 2004). The smooth curves seen in small simulations therefore cannot decide the order of the transition.

The program repeats the noise scan of Vicsek and colleagues at density ρ=4\rho = 4 with v0=0.03v_0 = 0.03, comparing N=100N = 100 (L=5L = 5) with N=25N = 25 (L=2.5L = 2.5). Neighbours are found with cell lists; each run lasts 600 steps, vav_a is averaged over steps 300 to 600, and two random seeds are used for each noise value.

Calculation

# Vicsek et al. (1995): N particles, speed v0 = 0.03, periodic box L, radius 1.
#   theta_i(t+1) = arg( sum_{|x_j - x_i| < 1} e^{i theta_j} ) + U(-eta/2, eta/2)
#   x_i(t+1) = x_i(t) + v0 e^{i theta_i(t+1)};   order v_a = |sum_i e^{i theta_i}| / N
# Density rho = N / L^2 = 4 as in the original noise scan; cell lists of side 1.
# v_a is averaged over steps 300..600 and over 2 seeds.
import math, random

def vicsek(N, L, eta, steps=600, burn=300, seed=0, v0=0.03):
    rng = random.Random(seed); nc = int(L)
    x = [rng.uniform(0, L) for _ in range(N)]; y = [rng.uniform(0, L) for _ in range(N)]
    th = [rng.uniform(-math.pi, math.pi) for _ in range(N)]
    acc = 0.0
    for t in range(steps):
        cells = {}
        for i in range(N):
            cells.setdefault((int(x[i]) % nc, int(y[i]) % nc), []).append(i)
        c = [math.cos(a) for a in th]; s = [math.sin(a) for a in th]; new = []
        for i in range(N):
            cx, cy, sc, ss = int(x[i]) % nc, int(y[i]) % nc, 0.0, 0.0
            for dx in (-1, 0, 1):
                for dy in (-1, 0, 1):
                    for j in cells.get(((cx + dx) % nc, (cy + dy) % nc), ()):
                        ex = (x[j] - x[i] + L / 2) % L - L / 2
                        ey = (y[j] - y[i] + L / 2) % L - L / 2
                        if ex * ex + ey * ey < 1.0:
                            sc += c[j]; ss += s[j]
            new.append(math.atan2(ss, sc) + rng.uniform(-eta / 2, eta / 2))
        th = new
        x = [(a + v0 * math.cos(b)) % L for a, b in zip(x, th)]
        y = [(a + v0 * math.sin(b)) % L for a, b in zip(y, th)]
        if t >= burn:
            acc += math.hypot(sum(map(math.cos, th)), sum(map(math.sin, th))) / N
    return acc / (steps - burn)

if __name__ == "__main__":
    print("noise eta   v_a (N = 100, L = 5)   v_a (N = 25, L = 2.5)")
    for eta in (0.5, 1.0, 1.5, 2.0, 2.5, 3.0, 3.5, 4.0, 5.0, 6.0):
        a = sum(vicsek(100, 5.0, eta, seed=s) for s in (1, 2)) / 2
        b = sum(vicsek(25, 2.5, eta, seed=s) for s in (1, 2)) / 2
        print(f"   {eta:3.1f}            {a:.3f}                  {b:.3f}")
# noise eta   v_a (N = 100, L = 5)   v_a (N = 25, L = 2.5)
#    0.5            0.988                  0.989
#    1.0            0.952                  0.957
#    1.5            0.894                  0.907
#    2.0            0.815                  0.837
#    2.5            0.719                  0.753
#    3.0            0.594                  0.653
#    3.5            0.476                  0.552
#    4.0            0.326                  0.430
#    5.0            0.127                  0.233
#    6.0            0.093                  0.173

At low noise both sizes are almost perfectly ordered (va≈0.99v_a \approx 0.99 at η=0.5\eta = 0.5); as the noise grows the order falls gradually, to 0.326 at η=4.0\eta = 4.0 and 0.093 at η=6.0\eta = 6.0 for N=100N = 100. The curve of the small system is flatter: at η=5.0\eta = 5.0, vav_a is 0.233 for N=25N = 25 against 0.127 for N=100N = 100, partly because of finite-size fluctuations (N−1/2N^{-1/2} is 0.20 and 0.10 respectively). Systems this small show a smooth crossover, which does not contradict the discontinuous transition Grégoire and Chaté found in large systems — the discontinuity appears only at large enough scales.

Evidence

Topological neighbours. Ballerini and colleagues in 2008 reconstructed the three-dimensional positions of individual starlings in flocks over Rome by stereo photography and found that each bird interacts with a fixed number of nearest neighbours (about six to seven), not with all individuals within a fixed distance; that is, interaction depends on topological rather than metric distance. They argue that this keeps the flock cohesive when its density changes sharply, for example under attack by a predator (Ballerini et al. 2008).

This finding is a reminder that “within radius 1” in the Vicsek model is a modelling choice. The program in Chapter 4 crudely replaces topological neighbours by looking at a few randomly chosen companions each step.

The Vicsek model also connects to Chapter 5. Jadbabaie, Lin and Morse in 2003 linearised the noise-free Vicsek model and proved that, provided the graph of neighbour relations is “jointly connected” over successive intervals of time, all individuals’ directions eventually agree; this is essentially a DeGroot averaging process whose neighbour relations change over time (Jadbabaie et al. 2003).

Couzin’s three-zone model

The model of Couzin, Krause, James, Ruxton and Franks in 2002 gives each individual three concentric zones (Couzin et al. 2002):

  • zone of repulsion (radius rrr_r): whenever a neighbour enters it, the individual gives priority to moving away, and the other rules are suspended;
  • zone of orientation (width Δro=ro−rr\Delta r_o = r_o – r_r): the individual aligns with the neighbours in it;
  • zone of attraction (width Δra=ra−ro\Delta r_a = r_a – r_o): the individual moves towards the neighbours in it.

Each individual has a blind zone behind it, a maximum turning angle per step, and random error in its direction. In three dimensions, varying Δro\Delta r_o and Δra\Delta r_a gave four collective states: swarm (cohesive but disordered, with low polarisation and low angular momentum), torus (individuals circle around an empty core, with high angular momentum), dynamic parallel (aligned, with constant exchange of positions inside the group) and highly parallel (very strongly aligned, moving almost in a straight line). With very small Δro\Delta r_o the group swarms; with small Δro\Delta r_o and larger Δra\Delta r_a it forms a torus; as Δro\Delta r_o grows it becomes parallel. When both are very small the group tends to fragment.

The framework lists only three states (“swarm, rotating torus, parallel cruising”); the book follows the original paper and gives four. More important is the paper’s “collective memory”: with ra=14r_a = 14 fixed and ror_o increased gradually, the group changes from swarm to torus at about ro≈1.5r_o \approx 1.5 and to parallel above about 2.5; but when ror_o is decreased gradually, the group stays parallel, never returns to the torus, and goes back to a swarm only when ror_o falls below about 1.5. The same individual rules can correspond to different collective states depending on what the group has been through, although no individual “knows” that history.

The program is a two-dimensional simplification of the three-zone model: N=40N = 40, rr=1r_r = 1, Δra=10\Delta r_a = 10, a blind zone of 90°90° behind (field of view ±135°\pm 135°), maximum turning rate 70°70° per second, speed 3, direction error with standard deviation 0.05 radians, time step 0.1 seconds. For each Δro\Delta r_o, three random starts are run for 1,200 steps each; over the last 300 steps the program computes the polarisation pp (magnitude of the mean unit velocity) and the normalised angular momentum mm, and labels the state parallel if p>0.65p > 0.65, otherwise torus if m>0.45m > 0.45, otherwise swarm. Finally, starting from the parallel group formed at Δro=8\Delta r_o = 8, it checks whether the state at smaller Δro\Delta r_o depends on where the group started. The parameters are illustrative, and two-dimensional results cannot be matched number for number with the original three-dimensional ones.

Calculation

# Two-dimensional simplification of the three-zone model of Couzin et al. (2002).
# Zone of repulsion r_r = 1 (priority); else orientation within r_o = r_r + d_o and
# attraction within r_a = r_o + d_a. Blind angle: neighbours behind (outside +-135 deg of
# the heading) are unseen. Max turn 70 deg/s, speed 3, noise SD 0.05 rad, dt 0.1 s, N 40.
# Measures (last 300 of 1200 steps): polarisation p = |mean unit velocity|,
# rotation m = |mean of (r_i - centroid)/|r_i - c| x v_i|.
import math, random

N, RR, SPEED, DT, TURN, SEE = 40, 1.0, 3.0, 0.1, math.radians(70), math.radians(135)

def step(x, y, h, ro, ra, rng):
    new = []
    for i in range(N):
        rx = ry = ox = oy = ax = ay = 0.0; rep = False
        for j in range(N):
            if j == i: continue
            dx, dy = x[j] - x[i], y[j] - y[i]; d2 = dx * dx + dy * dy
            if d2 >= ra * ra: continue
            d = math.sqrt(d2) or 1e-9
            if d < RR:
                rep = True; rx -= dx / d; ry -= dy / d; continue
            if abs((math.atan2(dy, dx) - h[i] + math.pi) % (2 * math.pi) - math.pi) > SEE:
                continue
            if d < ro: ox += math.cos(h[j]); oy += math.sin(h[j])
            else: ax += dx / d; ay += dy / d
        if rep: dx, dy = rx, ry
        else:
            no, na = math.hypot(ox, oy), math.hypot(ax, ay)
            dx = (ox / no if no else 0) + (ax / na if na else 0)
            dy = (oy / no if no else 0) + (ay / na if na else 0)
        want = math.atan2(dy, dx) if (dx or dy) else h[i]
        want += rng.gauss(0, 0.05)
        turn = (want - h[i] + math.pi) % (2 * math.pi) - math.pi
        new.append(h[i] + max(-TURN * DT, min(TURN * DT, turn)))
    xs = [a + SPEED * DT * math.cos(b) for a, b in zip(x, new)]
    ys = [a + SPEED * DT * math.sin(b) for a, b in zip(y, new)]
    return xs, ys, new

def measures(x, y, h):
    cx, cy = sum(x) / N, sum(y) / N
    p = math.hypot(sum(map(math.cos, h)), sum(map(math.sin, h))) / N
    m = 0.0
    for a, b, t in zip(x, y, h):
        d = math.hypot(a - cx, b - cy) or 1e-9
        m += ((a - cx) * math.sin(t) - (b - cy) * math.cos(t)) / d
    return p, abs(m) / N

def run(d_o, d_a=10.0, seed=3, steps=1200, start=None):
    rng = random.Random(seed)
    if start is None:
        x = [rng.uniform(-4, 4) for _ in range(N)]
        y = [rng.uniform(-4, 4) for _ in range(N)]
        h = [rng.uniform(-math.pi, math.pi) for _ in range(N)]
    else: x, y, h = start
    ro = RR + d_o; ps = ms = 0.0
    for t in range(steps):
        x, y, h = step(x, y, h, ro, ro + d_a, rng)
        if t >= steps - 300:
            p, m = measures(x, y, h); ps += p; ms += m
    return ps / 300, ms / 300, (x, y, h)

def label(p, m):
    return "parallel" if p > 0.65 else ("torus/mill" if m > 0.45 else "swarm")

if __name__ == "__main__":
    print("d_o   (p, m) for 3 random starts (d_a = 10)                 states")
    for d_o in (0.0, 1.0, 2.0, 4.0, 8.0):
        res = [run(d_o, seed=s)[:2] for s in (1, 2, 3)]
        print(f"{d_o:3.0f}   " + "  ".join(f"({p:.2f}, {m:.2f})" for p, m in res)
              + "   " + ", ".join(label(p, m) for p, m in res))
    _, _, pol = run(8.0, seed=1)        # collective memory: start from a parallel group
    for d_o in (4.0, 2.0):
        p, m, _ = run(d_o, seed=1, start=pol)
        print(f"d_o = {d_o:.0f}, started from the parallel group of d_o = 8:"
              f"  p = {p:.2f}, m = {m:.2f} -> {label(p, m)}")
# d_o   (p, m) for 3 random starts (d_a = 10)                 states
#   0   (0.19, 0.15)  (0.17, 0.08)  (0.12, 0.07)   swarm, swarm, swarm
#   1   (0.11, 0.81)  (0.11, 0.85)  (0.09, 0.18)   torus/mill, torus/mill, swarm
#   2   (0.15, 0.70)  (0.68, 0.16)  (0.16, 0.82)   torus/mill, parallel, torus/mill
#   4   (0.33, 0.71)  (0.26, 0.77)  (0.11, 0.84)   torus/mill, torus/mill, torus/mill
#   8   (1.00, 0.01)  (0.96, 0.05)  (0.99, 0.14)   parallel, parallel, parallel
# d_o = 4, started from the parallel group of d_o = 8:  p = 0.84, m = 0.05 -> parallel
# d_o = 2, started from the parallel group of d_o = 8:  p = 0.08, m = 0.86 -> torus/mill

The two-dimensional simplification reproduces the qualitative sequence of the original paper: at Δro=0\Delta r_o = 0 all three runs swarm (pp from 0.12 to 0.19); at Δro=4\Delta r_o = 4 all three form a torus (mm from 0.71 to 0.84); at Δro=8\Delta r_o = 8 all three are parallel (pp from 0.96 to 1.00). The intermediate region is multistable: at Δro=1\Delta r_o = 1, two runs form a torus and one swarms; at Δro=2\Delta r_o = 2, two form a torus and one is parallel. Collective memory appears too: at Δro=4\Delta r_o = 4 all three random starts form a torus, but a group that starts parallel stays parallel (p=0.84p = 0.84, m=0.05m = 0.05); at Δro=2\Delta r_o = 2 the memory is gone and the parallel group turns into a torus (p=0.08p = 0.08, m=0.86m = 0.86). This part uses a single seed; rerun with seeds 2 and 3 during checking, the parallel group of seed 2 stays parallel at both Δro=4\Delta r_o = 4 and 2, while that of seed 3 breaks up into a swarm at Δro=4\Delta r_o = 4 (where the random start of the same seed forms a torus). So “a group started parallel ends differently from random starts” (history matters) holds for all three seeds, but whether the parallel state survives, and the Δro\Delta r_o at which the memory disappears, depend on chance and cannot be read off a single run.

Left: the order v_a of the Vicsek model against the noise \eta (density 4, N = 100 and N = 25, one seed). Right: polarisation p and angular momentum m of the two-dimensional three-zone model against the width of the zone of orientation \Delta r_o (one seed): very small \Delta r_o gives a swarm, intermediate values high angular momentum (torus), larger values high polarisation (parallel).

Evidence

Three states in real fish schools. Tunstrøm and colleagues in 2013 analysed schools of 30 to 300 golden shiners and identified at least three dynamically stable collective states: swarm, milling and polarised. Slowly swimming fish formed dense, disordered swarms; at higher speeds the school entered either a milling state or a highly mobile polarised state. Milling and polarised states coexist bistably over a range of conditions, and transitions between them are driven mainly by perturbations; the stability of each state also depends on the size of the school (Tunstrøm et al. 2013).

Hypothesis · not established · Changing a collective state requires crossing the memory region

Both the three-zone model and the fish data show that over a range of parameters two collective states coexist, and which one a group occupies depends on its history. The author’s conjecture is that in crowds that have to coordinate movement (for example walking crowds in the paradigm of Dyer and colleagues in Chapter 4), if the strength of an instruction to “keep your direction in line with those near you” is changed step by step, the turning point from loose to orderly differs from the turning point from orderly back to loose (there is hysteresis). This can be tested with crowd-walking experiments that scan in both directions: if the turning points in the two directions do not differ statistically, the conjecture is wrong. This is an analogy from animal-group models to human crowds and implies no advice about managing organisations.

Summary

The Vicsek model produces collective order from “alignment plus noise” alone; Toner and Tu explained the source of long-range order in two dimensions, and Grégoire and Chaté showed that the transition is discontinuous in large systems, so the smooth curves of small systems cannot decide its order. Couzin’s three-zone model gives four states — swarm, torus, dynamic parallel and highly parallel — with hysteretic “collective memory”; a two-dimensional simplification reproduces these qualitative conclusions, and real fish schools are multistable too. The next chapter asks how such a group is led in one direction by a few informed individuals.

References

Aoki, Ichiro. 1982. “A Simulation Study on the Schooling Mechanism in Fish.” Bulletin of the Japanese Society of Scientific Fisheries 48 (8): 1081–88. https://doi.org/10.2331/suisan.48.1081.
Ballerini, Michele, Nicola Cabibbo, Raphael Candelier, et al. 2008. “Interaction Ruling Animal Collective Behavior Depends on Topological Rather Than Metric Distance: Evidence from a Field Study.” Proceedings of the National Academy of Sciences 105 (4): 1232–37. https://doi.org/10.1073/pnas.0711437105.
Couzin, Iain D., Jens Krause, Richard James, Graeme D. Ruxton, and Nigel R. Franks. 2002. “Collective Memory and Spatial Sorting in Animal Groups.” Journal of Theoretical Biology 218 (1): 1–11.
Grégoire, Guillaume, and Hugues Chaté. 2004. “Onset of Collective and Cohesive Motion.” Physical Review Letters 92 (2): 025702. https://doi.org/10.1103/PhysRevLett.92.025702.
Jadbabaie, Ali, Jie Lin, and A. Stephen Morse. 2003. “Coordination of Groups of Mobile Autonomous Agents Using Nearest Neighbor Rules.” IEEE Transactions on Automatic Control 48 (6): 988–1001.
Reynolds, Craig W. 1987. “Flocks, Herds and Schools: A Distributed Behavioral Model.” Computer Graphics (SIGGRAPH ’87 Proceedings) 21 (4): 25–34.
Toner, John, and Yuhai Tu. 1995. “Long-Range Order in a Two-Dimensional Dynamical XY Model: How Birds Fly Together.” Physical Review Letters 75 (23): 4326–29. https://doi.org/10.1103/PhysRevLett.75.4326.
Tunstrøm, Kolbjørn, Yael Katz, Christos C. Ioannou, Cristián Huepe, Matthew J. Lutz, and Iain D. Couzin. 2013. “Collective States, Multistability and Transitional Behavior in Schooling Fish.” PLoS Computational Biology 9 (2): e1002915. https://doi.org/10.1371/journal.pcbi.1002915.
Vicsek, Tamás, András Czirók, Eshel Ben-Jacob, Inon Cohen, and Ofer Shochet. 1995. “Novel Type of Phase Transition in a System of Self-Driven Particles.” Physical Review Letters 75 (6): 1226–29. https://doi.org/10.1103/PhysRevLett.75.1226.
Vicsek, Tamás, and Anna Zafeiris. 2012. “Collective Motion.” Physics Reports 517 (3): 71–140. https://doi.org/10.1016/j.physrep.2012.03.004.

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