Research · Computational modelling · Monash FIT3139

Web navigation as a stochastic process

PageRank imagines a surfer who follows links at random and sometimes teleports. α\alpha is the link probability; 1−α1 - \alpha is a uniform jump. That makes the chain irreducible and gives one equilibrium. The textbook stops at linear algebra. This keeps going: random click times, an exact six-page web, then recovering α\alpha from behaviour alone.

The web
6 pages · 11 weighted links
Hidden α recovered
0.730 / 0.730
SA final loss
1.35e-8 · 3,376 evals
Monte Carlo error
MSE ∝ 1/K
Q1 · stochasticityGillespie SSA

With random click times instead of synchronous updates, does the surfer still converge to deterministic PageRank, and how fast?

Answer

Yes. Time-weighted occupancy over 400 runs matches the eigenvector by T = 500. At T = 5 the estimates scatter. The deterministic model hides that.

Q2 · calibrationSimulated annealing

Given only an observed stationary distribution, can the damping factor be recovered?

Answer

Yes. Metropolis acceptance, geometric cooling. Lands on α = 0.730 against a hidden 0.73, loss 1.35e-8, ~3,400 evals.

The surfer, live

The exact six-page web from the submission. Squares scale with rank; the tally below tracks the surfer. Drag α\alpha.

0 steps · 0 teleports · mse 0.0e+0

teal bars: exact eigenvector. dark bars: where the surfer has actually been. red arcs are teleports. note E holding at (1−α)/6: nothing links to it.

The base model

At page ii the surfer follows a weighted out-link with probability α\alpha, or teleports to any page uniformly with probability 1−α1 - \alpha. The transition matrix is

P=αW+1−αNP = \alpha W + \dfrac{1 - \alpha}{N}

The ranking is its left eigenvector for eigenvalue one. Every page receives at least (1−α)/N(1 - \alpha)/N, so nothing traps the chain. Page E above is the degenerate case: no in-links, so its rank equals the teleport floor exactly (1−α)/6(1 - \alpha)/6.

Question one

Gillespie replaces synchronous steps with exponential waiting times between clicks. Across 400 runs, time-weighted occupancy at horizon T=500T = 500 matches deterministic PageRank; at T=5T = 5 the estimates scatter.

Stochastic timing changes the journey, not the destination.

Question two

Hide a true damping factor α=0.73\alpha = 0.73, observe only the stationary distribution it produces, then search for the α\alpha that explains it. Metropolis acceptance with geometric cooling walks the loss landscape down and stops at 0.7300.730.

The same machinery fits link weights to real clickstreams.

Monte Carlo backbone

Every empirical estimate is checked against the exact eigenvector. Mean-squared error decays as

MSE∝1K\mathrm{MSE} \propto \dfrac{1}{K}

Measured across chain lengths from 10310^{3} to 2×1052 \times 10^{5}, landing at 2.6×10−72.6 \times 10^{-7}. The live tally above is that experiment running.

The algorithms

Weighted PageRank
Power iteration with dangling-page handling. The baseline everything else is measured against.
Gillespie SSA
Continuous-time surfer, exponential waits between clicks. Stationary distribution by time-weighted occupancy.
Chain-binomial DTMC
Exact 6-page P=αW+(1−α)/NP = \alpha W + (1 - \alpha)/N, solved by left eigendecomposition.
Monte Carlo estimation
Visit frequencies against the exact eigenvector; 1/K1/K error decay measured across chain lengths.
Simulated annealing
Metropolis acceptance exp⁡(−ΔL/T)\exp(-\Delta L / T), geometric cooling, minimising stationary-distribution error over α\alpha.
Source on GitHubThe pretraining report →The canopy deep-dive →Harvey Houlahan · FIT3139 final project · Monash