PageRank Power Iteration

const N = 20, ALPHA = 0.85;
const TOP_COLORS = ["#ffd166", "#ef476f", "#06d6a0"];
let xs, ys, vxs, vys;
let outDeg, adj, adjT;
let rank, rankNext;
let iters = 0, l1 = 1;
let W = 0, H = 0;
let topIdx = [0, 1, 2];

function mulberry32(a) {
  return function () {
    a = (a + 0x6d2b79f5) | 0;
    let t = a;
    t = Math.imul(t ^ (t >>> 15), t | 1);
    t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}

function buildGraph() {
  const rng = mulberry32(0xC0FFEE13);
  outDeg = new Int32Array(N);
  adj = Array.from({ length: N }, () => []);
  adjT = Array.from({ length: N }, () => []);
  for (let u = 0; u < N; u++) {
    const k = 1 + Math.floor(rng() * 4);
    const seen = new Set([u]);
    for (let e = 0; e < k; e++) {
      let v = Math.floor(rng() * N), tries = 0;
      while (seen.has(v) && tries < 12) { v = Math.floor(rng() * N); tries++; }
      if (seen.has(v)) continue;
      seen.add(v);
      adj[u].push(v); adjT[v].push(u); outDeg[u]++;
    }
  }
}

function init({ width, height }) {
  W = width; H = height;
  buildGraph();
  xs = new Float32Array(N); ys = new Float32Array(N);
  vxs = new Float32Array(N); vys = new Float32Array(N);
  const cx = W * 0.5, cy = H * 0.55, R = Math.min(W, H) * 0.34;
  for (let i = 0; i < N; i++) {
    const a = (i / N) * Math.PI * 2;
    xs[i] = cx + Math.cos(a) * R;
    ys[i] = cy + Math.sin(a) * R;
  }
  rank = new Float32Array(N);
  rankNext = new Float32Array(N);
  for (let i = 0; i < N; i++) rank[i] = 1 / N;
  iters = 0; l1 = 1;
}

function relax(dt) {
  const pad = 30, kRep = 9000, kSpring = 0.012;
  const restLen = Math.min(W, H) * 0.22;
  const cx = W * 0.5, cy = H * 0.55;
  for (let i = 0; i < N; i++) {
    let fx = 0, fy = 0;
    for (let j = 0; j < N; j++) {
      if (i === j) continue;
      const dx = xs[i] - xs[j], dy = ys[i] - ys[j];
      const inv = 1 / (dx * dx + dy * dy + 0.01);
      fx += dx * kRep * inv; fy += dy * kRep * inv;
    }
    const neigh = adj[i].concat(adjT[i]);
    for (let a = 0; a < neigh.length; a++) {
      const j = neigh[a];
      const dx = xs[j] - xs[i], dy = ys[j] - ys[i];
      const d = Math.hypot(dx, dy) + 0.001;
      const f = kSpring * (d - restLen);
      fx += (dx / d) * f; fy += (dy / d) * f;
    }
    fx += (cx - xs[i]) * 0.0009;
    fy += (cy - ys[i]) * 0.0009;
    vxs[i] = (vxs[i] + fx * dt) * 0.86;
    vys[i] = (vys[i] + fy * dt) * 0.86;
  }
  for (let i = 0; i < N; i++) {
    xs[i] += Math.max(-40, Math.min(40, vxs[i])) * dt;
    ys[i] += Math.max(-40, Math.min(40, vys[i])) * dt;
    if (xs[i] < pad) { xs[i] = pad; vxs[i] = -vxs[i] * 0.4; }
    if (xs[i] > W - pad) { xs[i] = W - pad; vxs[i] = -vxs[i] * 0.4; }
    if (ys[i] < pad + 70) { ys[i] = pad + 70; vys[i] = -vys[i] * 0.4; }
    if (ys[i] > H - pad) { ys[i] = H - pad; vys[i] = -vys[i] * 0.4; }
  }
}

function pagerankStep() {
  let sinkMass = 0;
  for (let i = 0; i < N; i++) if (outDeg[i] === 0) sinkMass += rank[i];
  const teleport = (1 - ALPHA) / N + (ALPHA * sinkMass) / N;
  let diff = 0;
  for (let j = 0; j < N; j++) {
    let s = 0;
    const ins = adjT[j];
    for (let a = 0; a < ins.length; a++) {
      const i = ins[a];
      s += rank[i] / outDeg[i];
    }
    const v = ALPHA * s + teleport;
    diff += Math.abs(v - rank[j]);
    rankNext[j] = v;
  }
  const tmp = rank; rank = rankNext; rankNext = tmp;
  iters++; l1 = diff;
  const idx = [0, 0, 0];
  for (let i = 1; i < N; i++) {
    const r = rank[i];
    if (r > rank[idx[0]]) { idx[2] = idx[1]; idx[1] = idx[0]; idx[0] = i; }
    else if (r > rank[idx[1]]) { idx[2] = idx[1]; idx[1] = i; }
    else if (r > rank[idx[2]]) { idx[2] = i; }
  }
  topIdx = idx;
  if (l1 < 1e-5 && iters > 30) {
    const k = Math.floor(Math.random() * N);
    rank[k] += 0.15;
    let s = 0; for (let i = 0; i < N; i++) s += rank[i];
    for (let i = 0; i < N; i++) rank[i] /= s;
    iters = 0; l1 = 1;
  }
}

function nodeRadius(i) { return 4 + rank[i] * N * 9; }

function drawArrow(ctx, x1, y1, x2, y2, headPad) {
  const dx = x2 - x1, dy = y2 - y1;
  const d = Math.hypot(dx, dy) + 0.001;
  const ux = dx / d, uy = dy / d;
  const ex = x2 - ux * headPad, ey = y2 - uy * headPad;
  ctx.beginPath(); ctx.moveTo(x1, y1); ctx.lineTo(ex, ey); ctx.stroke();
  const ah = 7;
  ctx.beginPath();
  ctx.moveTo(ex, ey);
  ctx.lineTo(ex - ux * ah - uy * (ah * 0.55), ey - uy * ah + ux * (ah * 0.55));
  ctx.lineTo(ex - ux * ah + uy * (ah * 0.55), ey - uy * ah - ux * (ah * 0.55));
  ctx.closePath(); ctx.fill();
}

function drawHUD(ctx) {
  const pad = 12;
  ctx.fillStyle = "rgba(0,0,0,0.6)";
  ctx.fillRect(pad, pad, 230, 78);
  ctx.fillStyle = "#fff";
  ctx.font = "13px monospace";
  ctx.textAlign = "left"; ctx.textBaseline = "alphabetic";
  ctx.fillText(`PageRank   α = ${ALPHA.toFixed(2)}`, pad + 10, pad + 20);
  ctx.fillText(`iter   = ${iters}`, pad + 10, pad + 38);
  ctx.fillText(`||Δr||₁ = ${l1.toExponential(2)}`, pad + 10, pad + 56);
  ctx.fillText(`n      = ${N}`, pad + 10, pad + 74);
  const lx = W - pad - 150, ly = pad;
  ctx.fillStyle = "rgba(0,0,0,0.6)";
  ctx.fillRect(lx, ly, 150, 78);
  ctx.fillStyle = "#fff";
  ctx.fillText("top 3 by rank", lx + 10, ly + 18);
  for (let k = 0; k < 3; k++) {
    const y = ly + 36 + k * 16;
    ctx.fillStyle = TOP_COLORS[k];
    ctx.beginPath(); ctx.arc(lx + 18, y - 4, 5, 0, Math.PI * 2); ctx.fill();
    ctx.fillStyle = "#fff";
    const idx = topIdx[k];
    ctx.fillText(`#${idx}  ${(rank[idx] * 100).toFixed(1)}%`, lx + 32, y);
  }
}

function tick({ ctx, dt, width, height }) {
  if (width !== W || height !== H) { W = width; H = height; }
  relax(Math.min(dt, 0.05));
  pagerankStep();
  ctx.fillStyle = "#0a0d14";
  ctx.fillRect(0, 0, W, H);
  ctx.strokeStyle = "rgba(160,170,200,0.35)";
  ctx.fillStyle = "rgba(160,170,200,0.55)";
  ctx.lineWidth = 1;
  for (let i = 0; i < N; i++) {
    const outs = adj[i];
    for (let a = 0; a < outs.length; a++) {
      const j = outs[a];
      drawArrow(ctx, xs[i], ys[i], xs[j], ys[j], nodeRadius(j) + 3);
    }
  }
  for (let i = 0; i < N; i++) {
    const r = nodeRadius(i);
    let color = "#7aa2f7";
    const k = topIdx.indexOf(i);
    if (k !== -1) color = TOP_COLORS[k];
    ctx.fillStyle = color;
    ctx.beginPath();
    ctx.arc(xs[i], ys[i], r, 0, Math.PI * 2);
    ctx.fill();
    ctx.strokeStyle = "rgba(0,0,0,0.5)";
    ctx.lineWidth = 1;
    ctx.stroke();
  }
  drawHUD(ctx);
}