Influence Maximization

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 $k$ 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) \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.

The network below has 20 nodes. Each directed edge carries a fixed propagation probability. Pick a budget $k$ 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 $k$ randomly chosen seeds.

<!-- {{c_intro}} -->
<div class="controls">
  <label>{{lbl_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">{{btn_greedy}}</button>
    <button id="btn-random" type="button">{{btn_random}}</button>
    <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
</div>
<canvas id="graph-canvas" width="480" height="280"></canvas>
<div class="legend">
  <span class="dot seed-g"></span>{{legend_greedy_seed}}
  <span class="dot seed-r"></span>{{legend_random_seed}}
  <span class="dot active"></span>{{legend_reached}}
  <span class="dot idle"></span>{{legend_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; }

// Code not found

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)$ of optimal.

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)$ is monotone ($f(S) \leq f(S \cup \{v\})$ for any $v$) and submodular (the marginal gain of adding $v$ diminishes as $S$ 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) \approx 63.2\%$ of the optimum.
• The approximation ratio is tight. No polynomial-time algorithm can do better than $(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."

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

• Viral marketing: identify the $k$ most influential customers to seed a free product trial, maximizing organic word-of-mouth reach.
• Public health: in an epidemic, which $k$ 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 $k$ edges or nodes to minimize the spread of false information — is also submodular and admits similar guarantees.
• Sensor placement: place $k$ 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.

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)$ — 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.