For a school project, I’ve been reading lots of papers on good old PageRank. We’re doing something similar to this venerable algorithm in a streaming context. For a basis of comparison, I needed a simple, reliable implementation of the classic algorithm, and Matlab (octave) happens to excel at this kind of thing. So here’s my version. Initialized appropriately, this gives the same results as the diagram on the appropriate Wikipedia page. You probably wouldn’t want to run this on the web graph though: it wants to be run in a cluster at that scale.
function[R] = pagerank(A, R, d, epsilon)
N=size(A)(1);
E=ones(N);
R_last = R;
delta=epsilon;
while (delta >= epsilon)
R = (d * A + (1-d)/N * E) * R_last;
dist=R-R_last;
delta = sqrt(dot(dist,dist));
R_last = R;
end
R is the initial ranking vector. Typically this is just 1/N for each entry, but it can be some other probability distribution to arrive at personalized rankings. A is the column-oriented adjacency matrix divided by out-degree (with a plain adjacency matrix T, K=diag(sum(T)); A=K^-1 * T). Nodes with out-degree zero should be marked adjacent to everyone. d is the dampening factor, and epsilon is the convergence threshold.
I’m pretty sure my Matlab coding skills are quite lackluster, but it works.