Introduction

Imagine you have a rumor to spread — or a product to launch, or a vaccine policy to promote. You can personally tell it to exactly k people in a social network, and then let word of mouth do the rest. Each person who hears it has some chance of passing it along to their friends. The question is: which k people do you choose?

This is Influence Maximization: given a directed social graph and a probability model for how information travels along edges, find the seed set of size kk that maximizes the expected number of people who eventually hear the message.

The problem was placed on firm algorithmic footing in 2003 by David Kempe, Jon Kleinberg, and Éva Tardos. Their landmark paper showed two things at once: the exact problem is NP-hard, and yet a beautifully simple greedy algorithm is provably near-optimal — always reaching at least (1−1/e)≈63%(1 - 1/e) \approx 63\% of the best possible spread.

The secret behind that guarantee is submodularity — a mathematical property that says "the more you already have, the less you gain from adding one more." If a function is submodular and monotone, greedy works.

Seeds vs. Random

The network below has 20 nodes. Each directed edge carries a fixed propagation probability. Pick a budget kk with the slider, then press Run greedy to let the algorithm pick seeds one at a time, always choosing the node that adds the most expected spread. Press Run random to compare against kk randomly chosen seeds.

<!-- Influence Maximization demo: greedy seed selection vs random selection. -->
<div class="controls">
  <label>Budget k = <span id="k-val">3</span>
    <input type="range" id="k-slider" min="1" max="6" value="3">
  </label>
  <div class="btns">
    <button id="btn-greedy" type="button">Run greedy</button>
    <button id="btn-random" type="button">Run random</button>
    <button id="btn-reset" type="button" class="ghost">Reset</button>
  </div>
</div>
<canvas id="graph-canvas" width="480" height="280"></canvas>
<div class="legend">
  <span class="dot seed-g"></span>Greedy seed
  <span class="dot seed-r"></span>Random seed
  <span class="dot active"></span>Reached
  <span class="dot idle"></span>Idle
</div>
<div id="status" class="status"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.controls { display: flex; flex-wrap: wrap; align-items: center; gap: .6rem; margin-bottom: .5rem; }
label { font-size: .9rem; display: flex; align-items: center; gap: .4rem; }
input[type=range] { width: 90px; accent-color: #1d6fa8; }
.btns { display: flex; gap: .4rem; flex-wrap: wrap; }
button { font: 600 13px system-ui; padding: .38rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
canvas { display: block; border-radius: 10px; background: #f0f4f8;
         max-width: 100%; height: auto; border: 1px solid #d0d8e0; }
.legend { display: flex; flex-wrap: wrap; gap: .5rem 1rem; font-size: .8rem;
          align-items: center; margin-top: .4rem; }
.dot { display: inline-block; width: 10px; height: 10px; border-radius: 50%;
       border: 1.5px solid #555; margin-right: 3px; }
.dot.seed-g { background: #f4a261; border-color: #c1440e; }
.dot.seed-r { background: #e63946; border-color: #a31f2a; }
.dot.active { background: #4cc9f0; border-color: #1a7fa8; }
.dot.idle   { background: #cdd9e3; border-color: #8fa0ae; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.4em; margin-top: .4rem; }
.status.ok  { color: #0a7d33; }
.status.tie { color: #555; }
.status.bad { color: #c92f3c; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// 20-node directed social network.
// Each node has (id, x, y) for layout.
const NODES = [
  { id: 0, x: 60,  y: 60  },
  { id: 1, x: 160, y: 40  },
  { id: 2, x: 260, y: 60  },
  { id: 3, x: 360, y: 50  },
  { id: 4, x: 430, y: 120 },
  { id: 5, x: 100, y: 130 },
  { id: 6, x: 200, y: 120 },
  { id: 7, x: 310, y: 130 },
  { id: 8, x: 420, y: 200 },
  { id: 9, x: 50,  y: 200 },
  { id: 10, x: 150, y: 200 },
  { id: 11, x: 250, y: 200 },
  { id: 12, x: 340, y: 210 },
  { id: 13, x: 110, y: 260 },
  { id: 14, x: 220, y: 255 },
  { id: 15, x: 320, y: 260 },
  { id: 16, x: 430, y: 265 },
  { id: 17, x: 60,  y: 260 },
  { id: 18, x: 180, y: 140 },
  { id: 19, x: 390, y: 160 }
];
// Directed edges: [source, target, propagation-probability].
const EDGES = [
  [0,1,0.7],[0,5,0.5],[1,2,0.6],[1,6,0.5],[2,3,0.6],[2,7,0.5],
  [3,4,0.7],[3,7,0.4],[4,8,0.6],[4,19,0.5],[5,9,0.5],[5,10,0.6],
  [5,6,0.4],[6,10,0.5],[6,11,0.5],[7,11,0.6],[7,12,0.5],[8,12,0.7],
  [8,16,0.5],[9,13,0.6],[9,17,0.5],[10,13,0.5],[10,14,0.6],
  [11,14,0.5],[11,15,0.6],[12,15,0.5],[12,16,0.6],[13,17,0.4],
  [14,15,0.4],[15,16,0.4],[18,6,0.6],[18,10,0.5],[19,12,0.6],[1,18,0.5]
];
// Build adjacency list.
const ADJ = {};
NODES.forEach(n => ADJ[n.id] = []);
EDGES.forEach(([u,v,p]) => ADJ[u].push({ to: v, p }));

// Estimate expected spread via Monte Carlo simulation.
function estimateSpread(seeds, trials) {
  let total = 0;
  for (let t = 0; t < trials; t++) {
    const reached = new Set(seeds);
    const queue = [...seeds];
    while (queue.length) {
      const u = queue.shift();
      for (const { to, p } of ADJ[u]) {
        if (!reached.has(to) && Math.random() < p) {
          reached.add(to);
          queue.push(to);
        }
      }
    }
    total += reached.size;
  }
  return total / trials;
}

// Greedy seed selection: pick the node with largest marginal gain each round.
function greedySeeds(k) {
  const chosen = [];
  for (let i = 0; i < k; i++) {
    let best = -1, bestScore = -1;
    for (const n of NODES) {
      if (chosen.includes(n.id)) continue;
      const score = estimateSpread([...chosen, n.id], 200);
      if (score > bestScore) { bestScore = score; best = n.id; }
    }
    chosen.push(best);
  }
  return chosen;
}

// Random seed selection: pick k nodes uniformly at random.
function randomSeeds(k) {
  const pool = NODES.map(n => n.id).sort(() => Math.random() - 0.5);
  return pool.slice(0, k);
}

// Run one cascade simulation to visualize the actual reached set.
function simulateFull(seeds) {
  const reached = new Set(seeds);
  const queue = [...seeds];
  while (queue.length) {
    const u = queue.shift();
    for (const { to, p } of ADJ[u]) {
      if (!reached.has(to) && Math.random() < p) {
        reached.add(to);
        queue.push(to);
      }
    }
  }
  return reached;
}

const canvas = document.getElementById('graph-canvas');
const ctx = canvas.getContext('2d');
let state = { greedySeeds: [], greedyReached: new Set(), randomSeeds: [], randomReached: new Set(), mode: 'idle' };

// Render the graph on the canvas.
function draw() {
  const W = canvas.width, H = canvas.height;
  ctx.clearRect(0, 0, W, H);
  // Draw edges first (below nodes).
  for (const [u, v, p] of EDGES) {
    const a = NODES[u], b = NODES[v];
    ctx.beginPath();
    ctx.strokeStyle = `rgba(100,120,140,${0.25 + p * 0.35})`;
    ctx.lineWidth = 1 + p;
    ctx.moveTo(a.x, a.y); ctx.lineTo(b.x, b.y);
    ctx.stroke();
    // Draw arrowhead.
    const angle = Math.atan2(b.y - a.y, b.x - a.x);
    const ax = b.x - 9 * Math.cos(angle), ay = b.y - 9 * Math.sin(angle);
    ctx.beginPath();
    ctx.fillStyle = `rgba(100,120,140,${0.4 + p * 0.3})`;
    ctx.moveTo(ax, ay);
    ctx.lineTo(ax - 6 * Math.cos(angle - 0.4), ay - 6 * Math.sin(angle - 0.4));
    ctx.lineTo(ax - 6 * Math.cos(angle + 0.4), ay - 6 * Math.sin(angle + 0.4));
    ctx.fill();
  }
  // Draw nodes on top.
  for (const n of NODES) {
    const isGSeed = state.greedySeeds.includes(n.id);
    const isRSeed = state.randomSeeds.includes(n.id);
    const gReached = state.greedyReached.has(n.id);
    const rReached = state.randomReached.has(n.id);
    let fill = '#cdd9e3', stroke = '#8fa0ae';
    if (isGSeed) { fill = '#f4a261'; stroke = '#c1440e'; }
    else if (isRSeed) { fill = '#e63946'; stroke = '#a31f2a'; }
    else if (gReached || rReached) { fill = '#4cc9f0'; stroke = '#1a7fa8'; }
    ctx.beginPath();
    ctx.arc(n.x, n.y, 11, 0, 2 * Math.PI);
    ctx.fillStyle = fill; ctx.fill();
    ctx.strokeStyle = stroke; ctx.lineWidth = 2; ctx.stroke();
    ctx.fillStyle = '#333'; ctx.font = '9px system-ui';
    ctx.textAlign = 'center'; ctx.textBaseline = 'middle';
    ctx.fillText(n.id, n.x, n.y);
  }
}

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

const kSlider = document.getElementById('k-slider');
const kVal = document.getElementById('k-val');
kSlider.addEventListener('input', () => { kVal.textContent = kSlider.value; });

document.getElementById('btn-greedy').addEventListener('click', () => {
  const k = +kSlider.value;
  setStatus('Computing greedy seeds...', 'tie');
  // Defer so the browser can paint the running message first.
  setTimeout(() => {
    const seeds = greedySeeds(k);
    const reached = simulateFull(seeds);
    state = { greedySeeds: seeds, greedyReached: reached, randomSeeds: [], randomReached: new Set(), mode: 'greedy' };
    draw();
    setStatus(i18nFmt('Greedy k=%k%: reached %n% nodes.', { k, n: reached.size }), 'ok');
  }, 10);
});

document.getElementById('btn-random').addEventListener('click', () => {
  const k = +kSlider.value;
  const seeds = randomSeeds(k);
  const reached = simulateFull(seeds);
  const prev = state;
  state = { greedySeeds: prev.greedySeeds, greedyReached: prev.greedyReached, randomSeeds: seeds, randomReached: reached, mode: 'both' };
  draw();
  if (prev.greedySeeds.length === 0) {
    setStatus(i18nFmt('Random k=%k%: reached %n% nodes. Run greedy to compare.', { k, n: reached.size }), 'tie');
  } else {
    const gSize = prev.greedyReached.size;
    const cls = gSize >= reached.size ? 'ok' : 'bad';
    setStatus(i18nFmt('Greedy reached %gn% nodes · Random reached %rn% nodes.', { gn: gSize, rn: reached.size }), cls);
  }
});

document.getElementById('btn-reset').addEventListener('click', () => {
  state = { greedySeeds: [], greedyReached: new Set(), randomSeeds: [], randomReached: new Set(), mode: 'idle' };
  draw();
  setStatus('', '');
});

draw();
Result
Console

The greedy strategy wins almost every time — and the guarantee is mathematical, not just lucky. Because the spread function is submodular, each additional greedy pick is worth at most as much as the previous one, and the cumulative shortfall stays bounded below (1−1/e)(1 - 1/e) of optimal.

The Real Complexity

How hard is influence maximization, really?

  • The exact problem is NP-hard. Kempe, Kleinberg & Tardos (2003) proved this under both the Independent Cascade model (each edge fires once, independently) and the Linear Threshold model (a node activates when enough neighbors are active). Finding the seed set that maximizes expected spread exactly is as hard as any problem in NP.
  • Even computing the spread of a given seed set is #P-hard — counting the exact number of reachable nodes in a probabilistic graph requires summing over exponentially many outcomes. In practice, the spread is estimated via Monte Carlo simulation.
  • But greedy comes with a proof. The key insight is that the spread function f(S)f(S) is monotone (f(S)≤f(S∪{v})f(S) \leq f(S \cup \{v\}) for any vv) and submodular (the marginal gain of adding vv diminishes as SS grows). Nemhauser, Wolsey & Fisher (1978) proved that for any such function, the greedy algorithm — repeatedly add the element with the largest marginal gain — achieves at least (1−1/e)≈63.2%(1 - 1/e) \approx 63.2\% of the optimum.
  • The approximation ratio is tight. No polynomial-time algorithm can do better than (1−1/e)(1 - 1/e) unless P vs NP collapses.

This makes influence maximization one of the cleanest examples of a hard combinatorial problem where theory gives us a meaningful guarantee rather than just "good luck."

Where It Matters

The influence maximization framework appears wherever a small intervention must cascade broadly:

  • Viral marketing: identify the kk most influential customers to seed a free product trial, maximizing organic word-of-mouth reach.
  • Public health: in an epidemic, which kk individuals should receive a limited vaccine supply first to minimize total infections? The same submodular structure applies.
  • Rumor and misinformation control: the complementary problem — block kk edges or nodes to minimize the spread of false information — is also submodular and admits similar guarantees.
  • Sensor placement: place kk sensors in a water network to detect contamination as early as possible. Krause et al. showed this too is a submodular maximization problem.
  • Recommender systems and A/B testing: seeding early adopters in a social platform to maximize feature uptake follows the same logic.

The mathematical tools here — submodularity, greedy approximation, Monte Carlo estimation — travel well across domains. Understanding influence maximization means understanding a whole family of "pick few, affect many" problems.

Conclusion

Influence maximization captures something deep: sometimes the best is out of reach, but "good enough" comes with a proof. The greedy algorithm cannot be beaten by more than a factor of (1−1/e)(1 - 1/e) — not because we haven't tried harder, but because mathematics says the gap is tight.

The secret ingredient is submodularity — a diminishing-returns property that tames a combinatorially explosive search space. Wherever you see it, greedy tends to work well, and the theory of greedy algorithms tells you exactly how well.

So the next time a product launch asks "who do we tell first?", the answer is not guesswork — it's a provably near-optimal greedy walk through a submodular landscape, and the math is on your side.

Share this article

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

Comments

Loading comments...

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