Barabási–Albert Preferential Attachment

// Barabasi-Albert preferential attachment.
// Start from a small clique; each step add 1 node attached to m=2 existing
// nodes with probability proportional to degree. Force-directed layout.
// Inset shows the log-log degree histogram developing a power-law tail.

const N_MAX = 140, M = 2, M0 = 4;
const MAX_E = (M0 * (M0 - 1)) / 2 + (N_MAX - M0) * M;

let xs, ys, vxs, vys, deg, eA, eB, stub;
let n = 0, nE = 0, stubLen = 0;
let W = 0, H = 0, addAcc = 0;

function init({ width, height }) {
  W = width; H = height;
  xs = new Float32Array(N_MAX); ys = new Float32Array(N_MAX);
  vxs = new Float32Array(N_MAX); vys = new Float32Array(N_MAX);
  deg = new Int32Array(N_MAX);
  eA = new Int32Array(MAX_E); eB = new Int32Array(MAX_E);
  stub = new Int32Array(2 * MAX_E);
  reset();
}

function reset() {
  n = M0; nE = 0; stubLen = 0; addAcc = 0;
  const cx = W * 0.5, cy = H * 0.5;
  for (let i = 0; i < N_MAX; i++) deg[i] = 0;
  for (let i = 0; i < M0; i++) {
    const a = (i / M0) * Math.PI * 2;
    xs[i] = cx + Math.cos(a) * 18; ys[i] = cy + Math.sin(a) * 18;
    vxs[i] = 0; vys[i] = 0;
  }
  for (let i = 0; i < M0; i++)
    for (let j = i + 1; j < M0; j++) addEdge(i, j);
}

function addEdge(a, b) {
  eA[nE] = a; eB[nE] = b; nE++;
  deg[a]++; deg[b]++;
  stub[stubLen++] = a; stub[stubLen++] = b;
}

function addNode() {
  if (n >= N_MAX) return;
  const i = n;
  let sx = 0, sy = 0;
  for (let k = 0; k < n; k++) { sx += xs[k]; sy += ys[k]; }
  sx /= n; sy /= n;
  const r = 40 + Math.random() * 30, a = Math.random() * Math.PI * 2;
  xs[i] = sx + Math.cos(a) * r; ys[i] = sy + Math.sin(a) * r;
  vxs[i] = 0; vys[i] = 0;

  // Sample M distinct targets from the stub list (deg-weighted).
  const picked = [];
  let tries = 0;
  while (picked.length < M && tries < 200) {
    tries++;
    const t = stub[(Math.random() * stubLen) | 0];
    if (t === i) continue;
    let dup = false;
    for (let q = 0; q < picked.length; q++) if (picked[q] === t) { dup = true; break; }
    if (!dup) picked.push(t);
  }
  for (let k = 0; picked.length < M && k < n; k++) {
    let dup = false;
    for (let q = 0; q < picked.length; q++) if (picked[q] === k) { dup = true; break; }
    if (!dup) picked.push(k);
  }
  n++;
  for (let k = 0; k < picked.length; k++) addEdge(i, picked[k]);
}

function physics(dt) {
  const REP = 70, SPRING = 0.04, REST = 32, CENTER = 0.006;
  const cx = W * 0.5, cy = H * 0.5;
  for (let i = 0; i < n; i++) {
    let fx = (cx - xs[i]) * CENTER, fy = (cy - ys[i]) * CENTER;
    for (let j = 0; j < n; j++) {
      if (i === j) continue;
      const dx = xs[i] - xs[j], dy = ys[i] - ys[j];
      const d2 = dx * dx + dy * dy + 0.5;
      const inv = REP / d2;
      fx += dx * inv; fy += dy * inv;
    }
    vxs[i] = (vxs[i] + fx * dt) * 0.85;
    vys[i] = (vys[i] + fy * dt) * 0.85;
  }
  for (let e = 0; e < nE; e++) {
    const a = eA[e], b = eB[e];
    const dx = xs[b] - xs[a], dy = ys[b] - ys[a];
    const d = Math.sqrt(dx * dx + dy * dy) + 0.001;
    const f = (d - REST) * SPRING, ux = dx / d, uy = dy / d;
    vxs[a] += ux * f; vys[a] += uy * f;
    vxs[b] -= ux * f; vys[b] -= uy * f;
  }
  const pad = 14;
  for (let i = 0; i < n; i++) {
    xs[i] += vxs[i] * dt * 8; ys[i] += vys[i] * dt * 8;
    if (xs[i] < pad) { xs[i] = pad; vxs[i] *= -0.4; }
    if (xs[i] > W - pad) { xs[i] = W - pad; vxs[i] *= -0.4; }
    if (ys[i] < pad) { ys[i] = pad; vys[i] *= -0.4; }
    if (ys[i] > H - pad) { ys[i] = H - pad; vys[i] *= -0.4; }
  }
}

function nodeColor(d, maxD) {
  const t = Math.min(1, Math.log(1 + d) / Math.log(1 + Math.max(2, maxD)));
  return `hsl(${(220 - 220 * t).toFixed(0)},${70 + 20 * t}%,${50 + 15 * t}%)`;
}

function drawInset(ctx) {
  const W0 = Math.min(180, W * 0.4), H0 = Math.min(120, H * 0.32);
  const x0 = W - W0 - 10, y0 = H - H0 - 10;
  ctx.fillStyle = "rgba(0,0,0,0.62)";
  ctx.fillRect(x0, y0, W0, H0);

  let maxD = 1;
  for (let i = 0; i < n; i++) if (deg[i] > maxD) maxD = deg[i];
  const NB = 10, counts = new Int32Array(NB);
  const base = Math.pow(maxD, 1 / NB);
  for (let i = 0; i < n; i++) {
    const d = deg[i];
    if (d < 1) continue;
    let b = Math.floor(Math.log(d) / Math.log(base));
    if (b < 0) b = 0; if (b >= NB) b = NB - 1;
    counts[b]++;
  }
  let maxC = 1;
  for (let b = 0; b < NB; b++) if (counts[b] > maxC) maxC = counts[b];

  const pad = 22, ax = x0 + pad, ay = y0 + 8;
  const aw = W0 - pad - 8, ah = H0 - pad - 12;
  ctx.strokeStyle = "rgba(220,220,230,0.6)"; ctx.lineWidth = 1;
  ctx.beginPath();
  ctx.moveTo(ax, ay); ctx.lineTo(ax, ay + ah); ctx.lineTo(ax + aw, ay + ah);
  ctx.stroke();

  // Reference power-law slope -3 in log-log (BA prediction P(k) ~ k^-3).
  ctx.strokeStyle = "rgba(255,180,90,0.85)"; ctx.setLineDash([3, 3]);
  ctx.beginPath();
  ctx.moveTo(ax + 2, ay + 4); ctx.lineTo(ax + aw - 2, ay + ah - 2);
  ctx.stroke(); ctx.setLineDash([]);

  for (let b = 0; b < NB; b++) {
    if (counts[b] === 0) continue;
    const fx = b / NB, fy = Math.log(1 + counts[b]) / Math.log(1 + maxC);
    const bx = ax + fx * aw, bw = aw / NB - 1, bh = fy * ah;
    ctx.fillStyle = "rgba(120,200,255,0.9)";
    ctx.fillRect(bx, ay + ah - bh, bw, bh);
  }
  ctx.fillStyle = "#cfd6e4"; ctx.font = "10px monospace";
  ctx.textAlign = "left"; ctx.textBaseline = "alphabetic";
  ctx.fillText("log P(k)", x0 + 4, y0 + 12);
  ctx.fillText("log k", x0 + W0 - 32, y0 + H0 - 4);
  ctx.fillStyle = "rgba(255,180,90,0.95)";
  ctx.fillText("slope ~ -3", x0 + 36, y0 + 22);
}

function drawHUD(ctx, maxD) {
  ctx.fillStyle = "rgba(0,0,0,0.55)";
  ctx.fillRect(10, 10, 200, 70);
  ctx.fillStyle = "#fff"; ctx.font = "12px monospace";
  ctx.textAlign = "left"; ctx.textBaseline = "alphabetic";
  ctx.fillText(`Barabasi-Albert  m=${M}`, 18, 26);
  ctx.fillText(`nodes  = ${n}/${N_MAX}`, 18, 44);
  ctx.fillText(`edges  = ${nE}`, 18, 60);
  ctx.fillText(`max k  = ${maxD}`, 18, 76);
}

function tick({ ctx, dt, width, height }) {
  if (width !== W || height !== H) { W = width; H = height; }
  if (n >= N_MAX) {
    addAcc += dt;
    if (addAcc > 2.5) reset();
  } else {
    addAcc += dt;
    const RATE = 4;
    while (addAcc > 1 / RATE && n < N_MAX) { addNode(); addAcc -= 1 / RATE; }
  }
  physics(Math.min(dt, 0.05));

  ctx.fillStyle = "rgba(8,10,18,0.55)";
  ctx.fillRect(0, 0, W, H);

  let maxD = 1;
  for (let i = 0; i < n; i++) if (deg[i] > maxD) maxD = deg[i];

  ctx.strokeStyle = "rgba(150,160,190,0.32)"; ctx.lineWidth = 1;
  ctx.beginPath();
  for (let e = 0; e < nE; e++) {
    ctx.moveTo(xs[eA[e]], ys[eA[e]]); ctx.lineTo(xs[eB[e]], ys[eB[e]]);
  }
  ctx.stroke();

  for (let i = 0; i < n; i++) {
    const d = deg[i], r = 2 + Math.sqrt(d) * 1.4;
    ctx.fillStyle = nodeColor(d, maxD);
    ctx.beginPath();
    ctx.arc(xs[i], ys[i], r, 0, Math.PI * 2);
    ctx.fill();
  }

  drawHUD(ctx, maxD);
  drawInset(ctx);
}