Random walkers that stick on contact grow fractal trees, because the outer tips catch most of the walkers. The same instability appears in electrical discharges and river networks.
Like the sandpile, these clusters are fed one particle at a time, but nothing relaxes: each particle freezes where it sticks, and the outer tips catch most of the newcomers. The same instability drives a model of electrical discharge; the last section asks how much of it carries over to rivers.
Witten and Sander introduced diffusion-limited aggregation (DLA) in 1981: release a particle far from a seed, let it walk at random until it touches the cluster and sticks, then release the next. Close relatives describe zinc leaves grown by electrodeposition (Matsushita and colleagues 1984) and viscous fingers in a thin cell (Nittmann, Daccord and Stanley 1985).
Below, a walker that strays 10 cells past its launch circle is returned to the circle at an angle drawn from the distribution a free walk would follow, so none is discarded.
Figure 1. A DLA cluster grown from one seed until it reaches radius 126, colored by arrival order (dark early, gold late). Two estimates of the fractal dimension D: the slope of log N against log Rg (radius of gyration) over the last fourfold growth, and the slope of log N(<r), the mass within r of the seed, against log r for 3 ≤ r ≤ half the radius. Over seeds 1 to 40 (3,590 to 5,814 particles) the first averages 1.71 (range 1.56 to 1.82) and the second 1.66 (1.59 to 1.73); much larger simulations give 1.715 (Tolman and Meakin 1989).
The cluster branches instead of filling in because of screening. The chance u(x) that a walker from x reaches the launch circle before touching the cluster is the average of u over the four neighbors, so u obeys the discrete Laplace equation, 0 on the cluster and 1 on the circle. Walkers arrive where its contours crowd, at the tips; the branches around a fjord catch its walkers first. Figure 2 freezes a cluster and counts where fired walkers would have stuck.
Figure 2. A 3,000-particle DLA cluster grown as in Figure 1, and an Eden cluster of the same size, grown by filling a perimeter site chosen uniformly at random, ignoring the walkers. Each empty site on a cluster's outside is colored by its share of the seeded walkers fired so far, on a fixed log scale from 10−5 (pale) to 10−2 (dark); gray sites have caught none. The chart ranks sites from most to least hit and plots the cumulative share of walkers; equal exposure would follow the dashed diagonal.
After 60,000 walkers, half have landed on 2.3% of the DLA cluster's 3,499 perimeter sites and 71% of the sites have caught none; the Eden blob needs 15% of its sites to catch half. Tips that catch more grow faster, so a bump becomes a branch that sprouts bumps of its own: the Mullins–Sekerka instability that grows dendrites on a solidifying crystal.
Suppose a walker next to the cluster sticks only with probability p. It gets several chances to slip past the tips, which weakens screening and fills the cluster in, but only within the neighborhood it explores before sticking. Once branches are much longer than that, screening should return and the cluster cross over to ordinary DLA.
Figure 3. Full stickiness against reduced stickiness, each grown from seed 1 to radius 80. The chart plots the local dimension, the slope of log N(<r) against log r over [r/1.5, 1.5r], averaged over clusters from seeds 1 to 24 at each stickiness, computed while the figure is on screen; the dashed lines mark 2 and 1.71. A walker never steps onto an occupied cell.
Over 24 clusters, full stickiness gives a local dimension of 1.58 to 1.69, a little under 1.71 at this size. At p = 0.05 it holds near 1.83 out to r = 22, then falls to 1.73 at r = 32; at 0.1 it falls sooner, from 1.81 to 1.68. At 0.01 it is still 1.95 at r = 32: the crossover lies beyond this canvas.
The same growth can be computed without walkers. Solve Laplace's equation for a potential φ, 1 on the cluster and 0 on a distant boundary, and add one perimeter site with probability proportional to |∇φ|η. Niemeyer, Pietronero and Wiesmann proposed this dielectric breakdown model (DBM) in 1984 for branched surface discharges (Lichtenberg figures). At η = 1 a site grows in proportion to the field, as walkers arrive in DLA.
Figure 4. A discharge grows downward from a point on the top edge, with φ = 0 on the other edges; the glow shows the potential, relaxed by a few over-relaxed Gauss–Seidel sweeps after every step. Changing η restarts the growth. Because it grows toward grounded edges only a few hundred cells away, this discharge is sparser than a free DLA cluster even at η = 1.
Figure 5. Discharges grown outward from the center of a disk of radius 50 (φ = 0 on the rim), away from nearby edges, until they reach radius 40. Under each: D for the drawn run (seed 1), the slope of log N(<r) against log r for 2 ≤ r ≤ 0.6 of the cluster radius, then the mean over seeds 1 to 8 as they finish. After each added site the potential gets over-relaxed sweeps near it and over the disk; against a fully converged solve this misplaces at most 0.25% of the growth probability.
At η = 0 every perimeter site is equally likely: Eden growth, D = 1.99. At η = 1 the mean, 1.66, matches what Figure 1's clusters give from N(<r). Published values collected by Nicolás-Carlock and Carrillo-Estrada average 1.89, 1.70, 1.43, 1.26 and 1.11 at η = 0.5, 1, 2, 3 and 4; the eight runs here give 1.85, 1.66, 1.38, 1.15 and 1.11, scattering more at large η, where clusters hold only 130 to 180 particles.
River networks look like these trees. In the stream-power landscape below, rain falls evenly and each cell drains to its steepest downhill neighbor among eight; its drainage area A counts the cells whose water passes through it, itself included. The ground rises at rate U, except the bottom edge, held at sea level, and erodes at a rate that grows with the water and the slope S to the downstream cell:
Where water collects, erosion deepens the valley and steepens the slopes into it, capturing more area, so channel heads extend into the hillslope the way DLA tips extend into empty space.
Hover, tap or tab to a blue point to trace that order through the river network.
Figure 6. A simulated 100 × 100 landscape grown from low seeded noise, pits filled before each routing; darker ground is higher, on a fixed scale set by U/K, and blue marks channels, cells draining at least 20 cells. The chart counts stream segments per Strahler order on a log scale for this river (blue), the DLA cluster of Figure 1 (gold) and the discharge of Figure 4 (violet), with the fitted bifurcation ratio of each. The last readout is the median, over channel cells, of the simulated slope divided by (U/K)A−1/2.
Unlike DLA, this landscape reaches a steady state, S = (U/K)A−1/2, and the last readout climbs from 0 to 1 within about 200 steps. Double U and it drops to 0.5, then recovers within 200 steps while the relief grows 1.8 to 1.9 times.
In Strahler's ordering a channel with no tributaries is order 1, and two streams of order ω join to make order ω + 1. Horton noticed that segment counts fall by a roughly constant factor per order; on real rivers this bifurcation ratio is usually between 3 and 5, most often near 4. Ordered by attachment, the clusters land in or near that range too. Kirchner showed in 1993 that Horton's ratios describe virtually all possible branching networks, so they cannot tell which process built one.
Figure 7. The river of Figure 6 as it stands (blue) and a DLA cluster grown as in Figure 1 from seed 1 (gold). Left: the longest flow path above a cell against its drainage area, for areas of at least 20; for the cluster, path length back to the farthest tip against the number of particles hanging from a particle. Right: the fraction of cells or particles with area at least a, slope fitted from 10 to 1,000. Dashed: h = 0.58 and slope −0.43, from measured basins.
Hack found that main-stream length grows faster than the square root of basin area, L ∼ Ah, so large basins are elongated; measured basins give h = 0.57 to 0.60 (Maritan and colleagues 1996, tabulated by Dodds and Rothman). The simulated river gives 0.59 to 0.68 over terrains 1 to 6 between steps 200 and 4,000, and DLA clusters from seeds 1 to 6 give 0.61 to 0.65: Hack's law cannot separate them either. The area distribution can. Real basins have P(A ≥ a) ∼ a−0.43; the river gives slopes of 0.39 to 0.50 and the cluster 0.59 to 0.65.
Both processes send growth where a transported quantity (walkers, field, water) is already concentrated. In DLA it is a harmonic field over all the empty space, so a tip can starve a fjord many branch-widths away; in the stream-power model it is area summed down the flow tree, and basins interact only at their divides.
For one kind of river the analogy is exact. Streams fed by groundwater seepage, as in the sand of the Florida panhandle, grow forward in the direction from which groundwater enters their tips, and the water table obeys a Poisson equation. Devauchelle and colleagues showed in 2012 that this Laplacian growth predicts the splitting angle 2π/5 = 72°, and found it in the field.
Every walker here may cross cells it has already visited. The next essay forbids that: a walk that never revisits a cell spreads faster and models a polymer chain.