DLA Fractals

Diffusion-Limited Aggregation produces strikingly branched structures from a simple rule: a random walker sticks on contact with an existing cluster. The resulting fractal geometry bears a remarkable resemblance to the dendritic patterns of unplanned urban growth.

1. The DLA Algorithm

Diffusion-Limited Aggregation, introduced by Witten and Sander (1981), proceeds as follows:

Place a seed particle at the origin.
Launch a random walker from a circle far from the cluster.
The walker performs an unbiased random walk on the lattice.
When the walker reaches a site adjacent to the cluster, it sticks permanently.
Repeat from step 2.

The key physics: because the walker must diffuse to reach the cluster, tips and protrusions are more likely to capture walkers than fjords and indentations. This “tip effect” creates positive feedback—tips grow faster, producing the characteristic branching morphology.

The growth probability at the cluster surface is governed by the Laplacian field:

$$\nabla^2 c = 0 \quad \text{(outside cluster)}, \qquad c\big|_{\text{cluster}} = 0, \qquad c\big|_{\infty} = 1$$

The growth probability at a surface site is proportional to $|\nabla c|$, the local concentration gradient. Tips have higher gradients, hence higher growth probability.

2. Fractal Dimension via Box-Counting

A DLA cluster is a fractal: its mass scales as a non-integer power of its radius. The box-counting dimension is the standard way to quantify this. Cover the cluster with boxes of side length $\varepsilon$ and count the number $N(\varepsilon)$ of non-empty boxes:

$$N(\varepsilon) \sim \varepsilon^{-d_f}$$

Taking logarithms:

$$d_f = -\lim_{\varepsilon \to 0} \frac{\ln N(\varepsilon)}{\ln \varepsilon}$$

In practice, we compute $d_f$ as the negative slope of $\ln N$ vs. $\ln \varepsilon$ over a range of box sizes.

Known Results

2D DLA: $d_f \approx 1.71$
3D DLA: $d_f \approx 2.50$
A filled disk has $d_f = 2$; DLA is always more tenuous
The exact value in 2D remains unproven analytically—it is a numerical result

3. Mass-Radius Scaling

An equivalent characterisation uses the mass-radius relation. Count the number of occupied sites $M(R)$ within radius $R$ of the seed:

$$M(R) \sim R^{d_f}$$

For a compact cluster, $M \sim R^2$ in 2D. For DLA with $d_f \approx 1.71$, the cluster is significantly less dense than a filled disk. The density within radius $R$ thusdecreases with $R$:

$$\rho(R) = \frac{M(R)}{\pi R^2} \sim R^{d_f - 2} \to 0 \quad \text{as } R \to \infty$$

This declining density profile is a hallmark of fractal urban sprawl.

4. Urban Analogy: Unplanned Growth

Makse, Havlin, and Stanley (1995) demonstrated that the urban boundaries of cities like Berlin and London exhibit fractal dimensions consistent with DLA-like growth processes. The analogy works as follows:

Random walker = potential developer searching for a building site.
Sticking = building adjacent to existing development (access to roads, utilities, social networks).
Tip effect = development along transport corridors extends fingers of urbanisation into the countryside.
Fjord screening = green spaces between corridors remain undeveloped because they are hard to reach.

Measured fractal dimensions of city boundaries typically fall in the range $d_f \approx 1.2\text{--}1.8$, with more “sprawling” cities having lower values (more dendritic) and more compact cities approaching $d_f = 2$.

5. DLA Simulation with Box-Counting

The simulation below grows a DLA cluster particle-by-particle, then computes the box-counting fractal dimension from a log-log fit.

DLA Simulation with Box-Counting Fractal Dimension

Python

script.py140 lines

import numpy as np
import matplotlib.pyplot as plt
from collections import defaultdict

np.random.seed(42)

# --- DLA Simulation ---
grid_size = 201
centre = grid_size // 2
grid = np.zeros((grid_size, grid_size), dtype=bool)
grid[centre, centre] = True  # seed

n_particles = 800
max_radius = 5  # will grow dynamically

# Neighbour offsets (4-connected)
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

cluster_x = [centre]
cluster_y = [centre]

for p in range(n_particles):
    # Launch from circle of radius max_radius + 10
    launch_r = max_radius + 15
    angle = np.random.uniform(0, 2*np.pi)
    x = int(centre + launch_r * np.cos(angle))
    y = int(centre + launch_r * np.sin(angle))

stuck = False
    steps = 0
    kill_r = launch_r * 3

while not stuck and steps < 50_000:
        # Random walk step
        direction = np.random.randint(4)
        x += dx[direction]
        y += dy[direction]
        steps += 1

# Kill if too far
        dist = np.sqrt((x - centre)**2 + (y - centre)**2)
        if dist > kill_r:
            # Relaunch
            angle = np.random.uniform(0, 2*np.pi)
            x = int(centre + launch_r * np.cos(angle))
            y = int(centre + launch_r * np.sin(angle))
            continue

# Check for adjacency to cluster
        for d in range(4):
            nx, ny = x + dx[d], y + dy[d]
            if 0 <= nx < grid_size and 0 <= ny < grid_size and grid[nx, ny]:
                if 0 <= x < grid_size and 0 <= y < grid_size and not grid[x, y]:
                    grid[x, y] = True
                    cluster_x.append(x)
                    cluster_y.append(y)
                    r = np.sqrt((x - centre)**2 + (y - centre)**2)
                    if r > max_radius:
                        max_radius = r
                    stuck = True
                break

cluster_x = np.array(cluster_x)
cluster_y = np.array(cluster_y)

# --- Box-counting dimension ---
def box_count(points_x, points_y, box_sizes):
    counts = []
    for eps in box_sizes:
        boxes = set()
        for px, py in zip(points_x, points_y):
            boxes.add((int(px // eps), int(py // eps)))
        counts.append(len(boxes))
    return np.array(counts)

box_sizes = np.array([2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64])
# Filter to reasonable range
box_sizes = box_sizes[box_sizes < max_radius]
N_boxes = box_count(cluster_x, cluster_y, box_sizes)

# Fit slope
log_eps = np.log(box_sizes)
log_N = np.log(N_boxes)
slope, intercept = np.polyfit(log_eps, log_N, 1)
d_f = -slope

# --- Mass-radius relation ---
radii = np.sqrt((cluster_x - centre)**2 + (cluster_y - centre)**2)
r_bins = np.linspace(1, max_radius*0.9, 30)
mass_r = np.array([np.sum(radii <= rb) for rb in r_bins])
# Fit mass-radius exponent
mask_mr = mass_r > 5
log_r = np.log(r_bins[mask_mr])
log_m = np.log(mass_r[mask_mr])
df_mr, _ = np.polyfit(log_r, log_m, 1)

# --- Visualisation ---
fig, axes = plt.subplots(1, 3, figsize=(15, 5))

# (a) DLA cluster
ax = axes[0]
ax.scatter(cluster_y - centre, cluster_x - centre, s=0.3, c='teal', alpha=0.7)
ax.set_aspect('equal')
ax.set_title(f'DLA Cluster ({len(cluster_x)} particles)')
ax.set_xlabel('x')
ax.set_ylabel('y')
ax.set_facecolor('black')

# (b) Box-counting log-log
ax = axes[1]
ax.plot(log_eps, log_N, 'o', color='teal', markersize=6)
fit_x = np.linspace(log_eps.min(), log_eps.max(), 50)
ax.plot(fit_x, slope*fit_x + intercept, '--', color='crimson',
        linewidth=2, label=f'd_f = {d_f:.3f}')
ax.set_xlabel('ln(box size)')
ax.set_ylabel('ln(N boxes)')
ax.set_title('Box-Counting Dimension')
ax.legend(fontsize=11)

# (c) Mass-radius
ax = axes[2]
ax.loglog(r_bins, mass_r, 'o', color='teal', markersize=4)
r_fit = np.linspace(r_bins[mask_mr].min(), r_bins[mask_mr].max(), 50)
ax.loglog(r_fit, np.exp(_)*r_fit**df_mr, '--', color='crimson',
          linewidth=2, label=f'd_f(M-R) = {df_mr:.3f}')
ax.set_xlabel('R')
ax.set_ylabel('M(R)')
ax.set_title('Mass-Radius Scaling')
ax.legend(fontsize=11)

plt.tight_layout()
plt.savefig('output.png', dpi=130, bbox_inches='tight')
plt.show()

print(f"Box-counting fractal dimension: d_f = {d_f:.4f}")
print(f"Mass-radius fractal dimension:  d_f = {df_mr:.4f}")
print(f"Expected (2D DLA):              d_f ~ 1.71")
print(f"Total particles: {len(cluster_x)}")

Click Run to execute the Python code

Code will be executed with Python 3 on the server

6. Planning Implications

The fractal dimension of a city is not merely an aesthetic curiosity—it has direct consequences for infrastructure costs. If the urban footprint has fractal dimension $d_f$, then the road network needed to serve $M$ residents scales as:

$$L_{\text{road}} \sim M^{1/d_f}$$

A lower $d_f$ (more fractal, more sprawl) means more road per capita. DLA-like growth ($d_f \approx 1.7$) is roughly 20% more expensive in infrastructure than compact growth ($d_f \approx 2.0$) per unit population served.

← Part 8 Overview Fractional Fokker-Planck →