Introduction

You post something online, a few friends share it, some of their friends share it too — and suddenly it has reached a million people. What looks like magic follows a surprisingly clean mathematical rule.

The Independent Cascade Model (IC model), introduced by Kempe, Kleinberg and Tardos in 2003, captures diffusion in a network with one elegant idea: whenever a node first becomes active, it gets exactly one chance to activate each of its still-inactive neighbors. The probability of success along each edge is fixed in advance and each attempt is independent — a coin flip that the node only gets to make once.

The cascade then unfolds in rounds. In round one the initial seed set is active. In round two every seed flips its edge coins and activates some neighbors. Those newly active nodes flip their own coins in round three, and so on, until no new activations happen. The process always terminates.

Simple as this sounds, it is one of the most studied models in network science. It has been used to describe the spread of information on Twitter, the diffusion of new agricultural techniques among farmers, and the propagation of computer viruses — anything where exposure to an active neighbor gives you a single, stochastic nudge.

Watch the Spread

Click any node to toggle it as a seed (gold). Then press Run cascade to watch activation ripple outward round by round. Each edge fires at the probability shown on the slider — the higher the probability, the wider the reach tends to be.

<!-- Main layout — controls on top, canvas, status, buttons, hint -->
<div class="controls">
  <label class="prob-label">
    Edge probability: <strong id="prob-val">0.4</strong>
  </label>
  <input type="range" id="prob-slider" min="0" max="1" step="0.05" value="0.4" title="Adjust the activation probability per edge">
</div>
<canvas id="net" width="420" height="300" title="Network graph — click nodes to seed them"></canvas>
<div class="status" id="status">Click nodes to seed them, then run the cascade.</div>
<div class="stats" id="stats"></div>
<div class="btns">
  <button id="run" type="button">Run cascade</button>
  <button id="step" type="button">Step</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<p class="hint">Click nodes to mark seeds (gold), then press <b>Run cascade</b> or step through round by round. Each edge fires independently with the chosen probability.</p>

/* Base styles — layout, canvas, buttons, status text */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; background: #f8fafc; }
.controls { display: flex; align-items: center; gap: .6rem; margin-bottom: .4rem; flex-wrap: wrap; }
.prob-label { font-size: .9rem; color: #444; white-space: nowrap; }
input[type=range] { flex: 1; min-width: 120px; accent-color: #1d3557; }
canvas { display: block; border-radius: 10px; background: #fff;
         border: 1px solid #dde3ea; max-width: 100%; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0 .2rem; min-height: 1.4em; }
.status.running { color: #1d6fa4; }
.status.done { color: #0a7d33; }
.status.idle { color: #444; }
.stats { font-size: .85rem; color: #555; min-height: 1.2em; margin-bottom: .4rem; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .6rem; }
button { font: 600 14px system-ui; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: default; }
.hint { font-size: .85rem; color: #555; margin: 0; line-height: 1.45; }

/* Independent Cascade Model — each newly active node flips an edge coin once */
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

/* Graph nodes with pixel coordinates on the 420x300 canvas */
const NODES = [
  { id: 0, x: 210, y: 40 },
  { id: 1, x: 100, y: 110 },
  { id: 2, x: 320, y: 110 },
  { id: 3, x: 50,  y: 210 },
  { id: 4, x: 175, y: 190 },
  { id: 5, x: 295, y: 200 },
  { id: 6, x: 380, y: 210 },
  { id: 7, x: 120, y: 270 },
  { id: 8, x: 260, y: 265 }
];
/* Undirected edges; each active node tries each incident edge once */
const EDGES = [
  [0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,7],[4,7],[4,8],[5,8],[5,6],[6,8]
];

/* Node states: 0=inactive, 1=seed (gold), 2=active (red), 3=failed (unused) */
const STATE = { INACTIVE: 0, SEED: 1, ACTIVE: 2, FAILED: 3 };
let nodeState = [];     // current state per node index
let edgeFired = [];     // null=not tried, true=success, false=failed
let round = 0;          // current cascade round number
let newlyActive = [];   // nodes activated in the most recent round
let prob = 0.4;         // activation probability per edge
let animating = false;  // true while auto-stepping

const canvas = document.getElementById('net');
const ctx = canvas.getContext('2d');

/* Color palette for node/edge rendering */
const COLOR = {
  inactive: '#c9ccd1',
  seed:     '#f4c542',
  active:   '#e63946',
  failed:   '#c9ccd1',
  text:     '#1d3557',
  edgeBase: '#d0d7de',
  edgeHit:  '#e63946',
  edgeMiss: '#adb1b8'
};

function resetSim() {
  nodeState = NODES.map(() => STATE.INACTIVE);
  edgeFired = EDGES.map(() => null); // null means the edge has not been tried yet
  round = 0;
  newlyActive = [];
  animating = false;
  document.getElementById('run').disabled = false;
  document.getElementById('step').disabled = false;
  setStatus('Click nodes to seed them, then run the cascade.', 'idle');
  document.getElementById('stats').textContent = '';
  draw();
}

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t;
  s.className = 'status ' + cls;
}

/* Render all edges then all nodes on the canvas */
function draw() {
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  /* Draw edges first so nodes render on top */
  for (let i = 0; i < EDGES.length; i++) {
    const [a, b] = EDGES[i];
    const fired = edgeFired[i];
    ctx.beginPath();
    ctx.moveTo(NODES[a].x, NODES[a].y);
    ctx.lineTo(NODES[b].x, NODES[b].y);
    ctx.strokeStyle = fired === true ? COLOR.edgeHit : fired === false ? COLOR.edgeMiss : COLOR.edgeBase;
    ctx.lineWidth = fired !== null ? 2.2 : 1.4;
    ctx.stroke();
  }
  /* Draw nodes over edges */
  for (const n of NODES) {
    const st = nodeState[n.id];
    ctx.beginPath();
    ctx.arc(n.x, n.y, 16, 0, 2 * Math.PI);
    ctx.fillStyle = st === STATE.SEED ? COLOR.seed : st === STATE.ACTIVE ? COLOR.active : COLOR.inactive;
    ctx.fill();
    ctx.strokeStyle = '#fff';
    ctx.lineWidth = 2;
    ctx.stroke();
    ctx.fillStyle = COLOR.text;
    ctx.font = 'bold 12px system-ui';
    ctx.textAlign = 'center';
    ctx.textBaseline = 'middle';
    ctx.fillText(n.id, n.x, n.y);
  }
}

/* Advance the cascade by one round; returns true if more rounds may follow */
function doStep() {
  if (round === 0) {
    /* Round 0 means we are starting — collect seed nodes as initial active set */
    newlyActive = NODES.filter(n => nodeState[n.id] === STATE.SEED).map(n => n.id);
    if (newlyActive.length === 0) {
      setStatus('Select at least one seed node first.', 'idle');
      return false;
    }
    round = 1;
    setStatus(i18nFmt('Round %r% — activating neighbors…', { r: round }), 'running');
    draw();
    return true;
  }
  /* Each node active last round tries to activate its inactive neighbors */
  const justActive = newlyActive.slice();
  newlyActive = [];
  for (const src of justActive) {
    for (let i = 0; i < EDGES.length; i++) {
      const [a, b] = EDGES[i];
      let tgt = -1;
      if (a === src && nodeState[b] === STATE.INACTIVE) tgt = b;
      if (b === src && nodeState[a] === STATE.INACTIVE) tgt = a;
      if (tgt === -1) continue;
      /* Flip the edge coin — success with probability prob */
      const hit = Math.random() < prob;
      edgeFired[i] = hit;
      if (hit) {
        nodeState[tgt] = STATE.ACTIVE;
        newlyActive.push(tgt);
      }
    }
  }
  round++;
  draw();
  if (newlyActive.length === 0) {
    const total = nodeState.filter(s => s === STATE.ACTIVE || s === STATE.SEED).length;
    setStatus(i18nFmt('Cascade finished — %n% node(s) reached.', { n: total }), 'done');
    document.getElementById('stats').textContent =
      i18nFmt('%r% round(s), %n% of %total% nodes activated.', { r: round - 1, n: total, total: NODES.length });
    return false;
  }
  setStatus(i18nFmt('Round %r% — activating neighbors…', { r: round }), 'running');
  return true;
}

/* Run all rounds automatically with a short delay between them */
function runFull() {
  animating = true;
  document.getElementById('run').disabled = true;
  document.getElementById('step').disabled = true;
  function tick() {
    if (!animating) return;
    const more = doStep();
    if (more) setTimeout(tick, 700); // 700 ms pause so the user can see each wave
    else { animating = false; document.getElementById('step').disabled = false; }
  }
  tick();
}

/* Toggle node between inactive and seed when the user clicks on it */
canvas.addEventListener('click', e => {
  const rect = canvas.getBoundingClientRect();
  const scaleX = canvas.width / rect.width;
  const scaleY = canvas.height / rect.height;
  const mx = (e.clientX - rect.left) * scaleX;
  const my = (e.clientY - rect.top) * scaleY;
  for (const n of NODES) {
    const dx = mx - n.x, dy = my - n.y;
    if (dx * dx + dy * dy < 16 * 16) {
      if (nodeState[n.id] === STATE.INACTIVE) nodeState[n.id] = STATE.SEED;
      else if (nodeState[n.id] === STATE.SEED) nodeState[n.id] = STATE.INACTIVE;
      draw();
      break;
    }
  }
});

document.getElementById('prob-slider').addEventListener('input', e => {
  prob = parseFloat(e.target.value);
  document.getElementById('prob-val').textContent = prob.toFixed(2);
});
document.getElementById('run').addEventListener('click', runFull);
document.getElementById('step').addEventListener('click', doStep);
document.getElementById('reset').addEventListener('click', resetSim);

resetSim();
Result
Console

Notice that two runs from the same seeds can reach very different sets of nodes — because each edge flip is independent. The expected final size grows with edge probability, but individual runs are noisy. This randomness is exactly what makes predicting cascade outcomes analytically hard, and why influence maximization — choosing the best seeds — requires careful approximation algorithms.

The Real Complexity

The IC model raises a natural optimization question: given a budget of kk seeds, which kk nodes maximize the expected number of nodes eventually activated?

  • Computing expected spread exactly is #P-hard — as hard as counting satisfying assignments of a Boolean formula. Even simulating one run takes O(m)O(m) time, and you need exponentially many samples to pin down the expectation precisely.
  • Maximizing spread over all (nk)\binom{n}{k} seed sets is NP-hard in general. No polynomial algorithm is known that always finds the best seeds.
  • The silver lining: submodularity. Kempe, Kleinberg and Tardos (2003) proved that the expected spread function σ(S)\sigma(S) is monotone (adding a seed never hurts) and submodular (diminishing returns: adding a seed to a larger set gains no more than adding it to a smaller one). A classical theorem then guarantees that the simple greedy algorithm — repeatedly add the node with the highest marginal gain — achieves a (1−1/e)≈63%\bigl(1 - 1/e\bigr) \approx 63\% approximation of the optimum. This was a landmark result connecting counting problems and network optimization.
  • Scalability remains open. Each greedy step requires estimating σ\sigma via Monte Carlo simulation, making naive greedy slow on billion-node graphs. Faster variants (CELF, TIM+, IMM) are active research.

So the IC model sits in a rich zone: the stochastic process is clean and tractable for simulation, but optimizing over it touches #P and NP-hardness simultaneously.

Where It Matters

The "one chance per edge" rule turns out to describe a surprisingly wide range of real phenomena:

  • Viral marketing: a company wants to seed a product among influencers so word-of-mouth reaches as many people as possible — classic influence maximization under the IC model.
  • Epidemiology: each infected person has one contact window with each susceptible neighbor. The basic SIR epidemic model is a close cousin of IC, and the submodularity insight informs vaccination strategy.
  • Misinformation and rumor control: regulators ask which nodes to immunize (block) to minimize the spread of false information — the "competitive cascade" or "blocking" variant of IC.
  • Technology adoption: farmers adopt a new crop variety after enough neighbors demonstrate it; the IC model has been fit to real agricultural diffusion data in developing countries.
  • Cascading failures: in power grids and financial networks, a failure at one node can trigger neighbors with some probability — the IC model describes risk propagation.

The common thread is the same question P vs NP keeps raising: finding the optimal intervention is hard, but approximating it well is often tractable, and understanding why requires the full machinery of computational complexity.

Conclusion

The Independent Cascade Model packs a remarkable amount of insight into one rule: each newly activated node gets exactly one coin flip per outgoing edge. That minimalism makes it both analytically tractable and empirically realistic.

It also connects to deep computational questions. Computing the expected spread is #P-hard; choosing optimal seeds is NP-hard; yet the greedy approximation is provably near-optimal because the spread function is submodular. The interplay between probabilistic diffusion and algorithmic hardness — and the elegant escape through approximation — makes IC one of the most beautiful models in network science.

The next time a post explodes across your feed, remember: behind the chaos is a sequence of independent coin flips, and somewhere there is a tiny seed set that was just lucky enough — or strategically placed enough — to start the whole cascade.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/independent-cascade/Content licensed under CC BY-NC 4.0.