Random Surfer PageRank

// Monte Carlo PageRank via random-surfer simulation.
// Thousands of virtual hops/frame fill a visit histogram (alpha=0.85 follow
// outgoing edge, else teleport). Visit fraction converges to PageRank.
// One prototypical surfer is animated on top with a glowing trail.

const N = 12;
const ALPHA = 0.85;
const VHOPS = 4000; // virtual hops applied to histogram each frame
const TRAIL = 36;

let W = 0, H = 0;
let nx, ny;
let out, outDeg;
let visits, totalVisits = 0;
let trueRank;
let surfer = 0, surferPrev = 0;
let trailX, trailY, trailHead = 0, trailLen = 0;
let hopT = 0;
const HOP_DUR = 0.35;
let teleported = false, totalHops = 0, teleports = 0;
let phantom = 0;

function buildGraph() {
  const edges = [
    [0,1],[0,2],[0,3],[1,2],[1,4],[2,0],[2,5],[3,5],[3,6],
    [4,2],[4,7],[5,2],[5,8],[6,5],[6,9],[7,5],[8,2],[8,10],
    [9,5],[9,11],[10,5],[10,2],[11,5],[11,8],
  ];
  outDeg = new Int32Array(N);
  for (const [a] of edges) outDeg[a]++;
  out = new Array(N);
  const cur = new Int32Array(N);
  for (let i = 0; i < N; i++) out[i] = new Int32Array(Math.max(1, outDeg[i]));
  for (const [a, b] of edges) out[a][cur[a]++] = b;
}

function layout() {
  const cx = W * 0.5, cy = H * 0.5 + 6, R = Math.min(W, H) * 0.36;
  nx = new Float32Array(N); ny = new Float32Array(N);
  for (let i = 0; i < N; i++) {
    const a = -Math.PI / 2 + (i / N) * Math.PI * 2;
    nx[i] = cx + Math.cos(a) * R; ny[i] = cy + Math.sin(a) * R;
  }
}

function powerIteration() {
  trueRank = new Float64Array(N);
  let r = new Float64Array(N);
  for (let i = 0; i < N; i++) r[i] = 1 / N;
  const next = new Float64Array(N);
  for (let it = 0; it < 80; it++) {
    next.fill(0);
    let dangling = 0;
    for (let i = 0; i < N; i++) {
      if (outDeg[i] === 0) { dangling += r[i]; continue; }
      const share = (ALPHA * r[i]) / outDeg[i];
      for (let k = 0; k < outDeg[i]; k++) next[out[i][k]] += share;
    }
    const base = (1 - ALPHA) / N + (ALPHA * dangling) / N;
    for (let i = 0; i < N; i++) { next[i] += base; r[i] = next[i]; }
  }
  for (let i = 0; i < N; i++) trueRank[i] = r[i];
}

function init({ width, height }) {
  W = width; H = height;
  buildGraph(); layout(); powerIteration();
  visits = new Float64Array(N); visits[0] = 1; totalVisits = 1;
  surfer = 0; surferPrev = 0; phantom = 0;
  trailX = new Float32Array(TRAIL); trailY = new Float32Array(TRAIL);
  trailHead = 0; trailLen = 0;
  pushTrail(nx[0], ny[0]);
  hopT = 0; teleported = false; totalHops = 0; teleports = 0;
}

function pushTrail(x, y) {
  trailX[trailHead] = x; trailY[trailHead] = y;
  trailHead = (trailHead + 1) % TRAIL;
  if (trailLen < TRAIL) trailLen++;
}

function virtualStep() {
  let p = phantom;
  for (let k = 0; k < VHOPS; k++) {
    if (Math.random() < ALPHA && outDeg[p] > 0) {
      p = out[p][(Math.random() * outDeg[p]) | 0];
    } else {
      p = (Math.random() * N) | 0;
    }
    visits[p] += 1;
  }
  phantom = p;
  totalVisits += VHOPS;
}

function stepSurfer() {
  surferPrev = surfer;
  if (Math.random() < ALPHA && outDeg[surfer] > 0) {
    surfer = out[surfer][(Math.random() * outDeg[surfer]) | 0];
    teleported = false;
  } else {
    surfer = (Math.random() * N) | 0;
    teleported = true; teleports++;
  }
  totalHops++;
}

function nodeRadius(i) {
  const mc = totalVisits > 0 ? visits[i] / totalVisits : 1 / N;
  return 8 + Math.min(18, mc * 90);
}

function drawEdges(ctx) {
  ctx.strokeStyle = "rgba(120,130,160,0.32)"; ctx.lineWidth = 1;
  ctx.beginPath();
  for (let i = 0; i < N; i++) {
    for (let k = 0; k < outDeg[i]; k++) {
      const j = out[i][k];
      const dx = nx[j] - nx[i], dy = ny[j] - ny[i], L = Math.hypot(dx, dy) || 1;
      const r1 = nodeRadius(i) + 1, r2 = nodeRadius(j) + 4;
      ctx.moveTo(nx[i] + (dx / L) * r1, ny[i] + (dy / L) * r1);
      ctx.lineTo(nx[j] - (dx / L) * r2, ny[j] - (dy / L) * r2);
    }
  }
  ctx.stroke();
  ctx.fillStyle = "rgba(160,170,200,0.45)";
  for (let i = 0; i < N; i++) {
    for (let k = 0; k < outDeg[i]; k++) {
      const j = out[i][k];
      const dx = nx[j] - nx[i], dy = ny[j] - ny[i], L = Math.hypot(dx, dy) || 1;
      const r2 = nodeRadius(j) + 4;
      const ex = nx[j] - (dx / L) * r2, ey = ny[j] - (dy / L) * r2;
      const ang = Math.atan2(dy, dx), sz = 6;
      ctx.beginPath();
      ctx.moveTo(ex, ey);
      ctx.lineTo(ex - Math.cos(ang - 0.4) * sz, ey - Math.sin(ang - 0.4) * sz);
      ctx.lineTo(ex - Math.cos(ang + 0.4) * sz, ey - Math.sin(ang + 0.4) * sz);
      ctx.closePath(); ctx.fill();
    }
  }
}

function drawNodes(ctx) {
  for (let i = 0; i < N; i++) {
    const mc = totalVisits > 0 ? visits[i] / totalVisits : 1 / N;
    const tr = trueRank[i], err = Math.abs(mc - tr), r = nodeRadius(i);
    const hue = 220 - Math.min(180, tr * 800);
    ctx.fillStyle = `hsl(${hue},70%,${30 + Math.min(35, tr * 220)}%)`;
    ctx.beginPath(); ctx.arc(nx[i], ny[i], r, 0, Math.PI * 2); ctx.fill();
    ctx.strokeStyle = err < 0.005 ? "rgba(120,255,160,0.9)" : "rgba(255,255,255,0.45)";
    ctx.lineWidth = 1.5; ctx.stroke();
    ctx.fillStyle = "#fff"; ctx.textAlign = "center"; ctx.textBaseline = "middle";
    ctx.font = "bold 11px monospace"; ctx.fillText(String(i), nx[i], ny[i] - 4);
    ctx.font = "10px monospace"; ctx.fillText(mc.toFixed(3), nx[i], ny[i] + 8);
  }
}

function drawTrail(ctx) {
  if (trailLen < 2) return;
  for (let s = 0; s < trailLen - 1; s++) {
    const i0 = (trailHead - trailLen + s + TRAIL * 2) % TRAIL;
    const i1 = (trailHead - trailLen + s + 1 + TRAIL * 2) % TRAIL;
    const a = (s + 1) / trailLen;
    ctx.strokeStyle = `rgba(255,220,120,${a * 0.6})`;
    ctx.lineWidth = 1 + a * 2.5;
    ctx.beginPath();
    ctx.moveTo(trailX[i0], trailY[i0]); ctx.lineTo(trailX[i1], trailY[i1]);
    ctx.stroke();
  }
}

function drawSurfer(ctx, sx, sy) {
  const g = ctx.createRadialGradient(sx, sy, 1, sx, sy, 22);
  g.addColorStop(0, "rgba(255,240,170,0.9)"); g.addColorStop(1, "rgba(255,200,80,0)");
  ctx.fillStyle = g; ctx.beginPath(); ctx.arc(sx, sy, 22, 0, Math.PI * 2); ctx.fill();
  ctx.fillStyle = teleported && hopT < 0.5 ? "#ff90c0" : "#fff4b0";
  ctx.beginPath(); ctx.arc(sx, sy, 4.5, 0, Math.PI * 2); ctx.fill();
}

function drawHUD(ctx) {
  const pad = 10;
  ctx.fillStyle = "rgba(0,0,0,0.6)"; ctx.fillRect(pad, pad, 236, 86);
  ctx.fillStyle = "#fff"; ctx.font = "12px monospace";
  ctx.textAlign = "left"; ctx.textBaseline = "alphabetic";
  ctx.fillText(`alpha (damping)  = ${ALPHA.toFixed(2)}`, pad + 8, pad + 18);
  ctx.fillText(`virtual hops/fr  = ${VHOPS}`, pad + 8, pad + 34);
  ctx.fillText(`total hops       = ${totalVisits.toLocaleString()}`, pad + 8, pad + 50);
  const tp = totalHops > 0 ? (teleports / totalHops) : 0;
  ctx.fillText(`teleports        = ${(tp * 100).toFixed(1)}% (~${((1 - ALPHA) * 100).toFixed(0)}%)`, pad + 8, pad + 66);
  ctx.fillStyle = "rgba(120,255,160,0.9)";
  ctx.fillText("green ring = within 0.005 of true PR", pad + 8, pad + 82);

  let l1 = 0;
  for (let i = 0; i < N; i++) {
    const mc = totalVisits > 0 ? visits[i] / totalVisits : 1 / N;
    l1 += Math.abs(mc - trueRank[i]);
  }
  const bw = Math.min(260, W - 2 * pad), bh = 26, bx = pad, by = H - pad - bh;
  ctx.fillStyle = "rgba(0,0,0,0.6)"; ctx.fillRect(bx, by - 14, bw, bh + 14);
  ctx.fillStyle = "#fff"; ctx.font = "11px monospace";
  ctx.fillText(`|MC - PR|_1 = ${l1.toFixed(4)}`, bx + 6, by - 2);
  ctx.fillStyle = "#2a3554"; ctx.fillRect(bx + 6, by + 4, bw - 12, bh - 12);
  const frac = Math.max(0, Math.min(1, 1 - Math.min(1, l1 / 0.5)));
  ctx.fillStyle = "hsl(" + (120 * frac) + ",70%,55%)";
  ctx.fillRect(bx + 6, by + 4, (bw - 12) * frac, bh - 12);
}

function tick({ ctx, dt, width, height }) {
  if (width !== W || height !== H) { W = width; H = height; layout(); }
  virtualStep();
  hopT += dt / HOP_DUR;
  while (hopT >= 1) { hopT -= 1; stepSurfer(); }
  ctx.fillStyle = "#08080f"; ctx.fillRect(0, 0, W, H);
  drawEdges(ctx);
  let sx, sy;
  if (teleported) {
    sx = nx[surfer]; sy = ny[surfer];
    if (hopT < 0.05) pushTrail(sx, sy);
  } else {
    const t = hopT;
    sx = nx[surferPrev] * (1 - t) + nx[surfer] * t;
    sy = ny[surferPrev] * (1 - t) + ny[surfer] * t;
    pushTrail(sx, sy);
  }
  drawTrail(ctx); drawNodes(ctx); drawSurfer(ctx, sx, sy); drawHUD(ctx);
}