Introduction

Imagine you are deciding whether to try a new social platform. You are not simply swayed by one friend's recommendation. Instead you wait until enough of your contacts have joined — a personal tipping point. Cross it, and you join too. The Linear Threshold Model (LTM) turns this intuition into mathematics.

Introduced by Mark Granovetter in 1978 and formalized by David Kempe, Jon Kleinberg, and Éva Tardos in their landmark 2003 paper, the LTM works as follows. Each node vv in a graph holds a threshold θv∈[0,1]\theta_v \in [0,1], drawn uniformly at random or set by hand. Each directed edge (u,v)(u, v) carries a weight wu,v≥0w_{u,v} \geq 0 such that the weights of all edges into vv sum to at most 1. A node becomes active (adopts the behavior) as soon as the total weight of its already-active neighbors meets or exceeds its threshold:

∑u∈N(v), u activewu,v  ≥  θv\sum_{u \in N(v),\, u \text{ active}} w_{u,v} \;\geq\; \theta_v

The process unfolds in discrete rounds. An initially seeded set of nodes SS is activated at time 0. In each subsequent round every inactive node that now meets its threshold activates. Once active a node stays active forever — the model is monotone. The cascade runs until no more activations are possible.

The central question is influence maximization: given a budget of kk seeds, which set SS of size kk triggers the largest final cascade? This turns out to be a deep computational problem connected to submodular optimization.

Watch the Cascade

Each circle is a node with a personal threshold shown as a percentage — the fraction of neighbor weight that must adopt before the node joins. Edges carry equal weight split among a node's in-neighbors. Click any gray node to seed it, then press Run one round to advance the cascade one step at a time, or Run to end to see the final result at once. Press Reset to start over.

<!-- Interactive Linear Threshold Model: click nodes to seed, then step or run the cascade -->
<div class="controls">
  <button id="btn-step" type="button">Run one round</button>
  <button id="btn-run" type="button">Run to end</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<div class="status-row">
  <span class="label">Round:</span>
  <span id="round-num">0</span>
  <span id="status-msg" class="status-msg"></span>
</div>
<svg id="graph" viewBox="0 0 400 320" aria-label="Network cascade visualization"></svg>
<p class="hint">Click any gray node to toggle it as a seed (red). The label shows current-weight/threshold for inactive nodes.</p>

/* Styles for the LTM cascade demo */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: default; }
.status-row { display: flex; align-items: center; gap: .5rem; font-size: .9rem;
              font-weight: 600; margin-bottom: .3rem; }
.label { color: #666; font-weight: 400; }
.status-msg { color: #0a7d33; }
.hint { font-size: .82rem; color: #555; margin: .4rem 0 0; line-height: 1.4; }
/* Node state colors: inactive=gray, seed=red, active=teal */
.node-circle { stroke-width: 2; cursor: pointer; transition: fill .25s; }
.node-inactive { fill: #c9ccd1; stroke: #9aa0a9; }
.node-seed { fill: #e63946; stroke: #b02531; }
.node-active { fill: #2a9d8f; stroke: #1d7a6e; }
.node-label { font: 700 11px ui-monospace, monospace; fill: #fff; pointer-events: none;
              text-anchor: middle; dominant-baseline: central; }
.node-thresh { font: 400 9px system-ui; fill: #333; pointer-events: none;
               text-anchor: middle; dominant-baseline: hanging; }
.edge-line { stroke: #bcc0c6; stroke-width: 1.5; fill: none; marker-end: url(#arrow); }
.edge-active { stroke: #2a9d8f; stroke-width: 2; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Linear Threshold Model simulation — a node activates when the weighted sum of active neighbors meets its threshold

// 6-node directed graph: id, SVG position, and personal threshold theta
const NODES = [
  { id: 0, x: 200, y:  50, thresh: 0.40 },
  { id: 1, x:  80, y: 140, thresh: 0.34 },
  { id: 2, x: 320, y: 140, thresh: 0.50 },
  { id: 3, x:  80, y: 250, thresh: 0.34 },
  { id: 4, x: 200, y: 250, thresh: 0.60 },
  { id: 5, x: 320, y: 250, thresh: 0.34 }
];
// Directed edges (u -> v); weights are split equally among each node's in-neighbors
const EDGES = [
  [0,1],[0,2],[1,3],[1,4],[2,4],[2,5],[3,4],[4,5]
];

// Build in-neighbor weight map: each in-neighbor contributes 1/deg_in weight
const INW = Array.from({ length: NODES.length }, () => ({}));
for (const [u, v] of EDGES) {
  if (!INW[v][u]) INW[v][u] = 0;
  INW[v][u]++;
}
for (let v = 0; v < NODES.length; v++) {
  const total = Object.values(INW[v]).reduce((a, b) => a + b, 0) || 1;
  for (const u in INW[v]) INW[v][u] /= total;
}

let state = NODES.map(() => 'inactive'); // node state: inactive | seed | active
let round = 0;
let done = false;

const svg = document.getElementById('graph');
const roundEl = document.getElementById('round-num');
const statusEl = document.getElementById('status-msg');

function buildSVG() {
  // Render the full SVG: edges first, then node circles and labels
  svg.innerHTML = `
    <defs>
      <marker id="arrow" markerWidth="7" markerHeight="7" refX="6" refY="3.5"
              orient="auto">
        <path d="M0,0 L7,3.5 L0,7 z" fill="#bcc0c6"/>
      </marker>
      <marker id="arrow-active" markerWidth="7" markerHeight="7" refX="6" refY="3.5"
              orient="auto">
        <path d="M0,0 L7,3.5 L0,7 z" fill="#2a9d8f"/>
      </marker>
    </defs>`;
  // Draw edges with active-state coloring
  for (const [u, v] of EDGES) {
    const nu = NODES[u], nv = NODES[v];
    const dx = nv.x - nu.x, dy = nv.y - nu.y;
    const dist = Math.sqrt(dx * dx + dy * dy);
    const r = 20;
    const sx = nu.x + (dx / dist) * r;
    const sy = nu.y + (dy / dist) * r;
    const ex = nv.x - (dx / dist) * (r + 5);
    const ey = nv.y - (dy / dist) * (r + 5);
    const isActive = (state[u] === 'active' || state[u] === 'seed') &&
                     (state[v] === 'active' || state[v] === 'seed');
    const cls = isActive ? 'edge-line edge-active' : 'edge-line';
    const marker = isActive ? 'url(#arrow-active)' : 'url(#arrow)';
    svg.innerHTML += `<line class="${cls}" x1="${sx}" y1="${sy}" x2="${ex}" y2="${ey}" marker-end="${marker}"/>`;
  }
  // Draw node circles with state color and threshold label
  for (const n of NODES) {
    const cls = 'node-circle node-' + state[n.id];
    const pct = Math.round(n.thresh * 100);
    const wt = calcWeight(n.id);
    const wPct = Math.round(wt * 100);
    // Show current-weight/threshold for inactive nodes, star for seeds, check for active
    const lbl = state[n.id] === 'inactive' ? `${wPct}/${pct}%` : (state[n.id] === 'seed' ? '★' : '✓');
    svg.innerHTML += `
      <circle class="${cls}" cx="${n.x}" cy="${n.y}" r="20"
              onclick="toggleSeed(${n.id})"/>
      <text class="node-label" x="${n.x}" y="${n.y}">${lbl}</text>
      <text class="node-thresh" x="${n.x}" y="${n.y + 25}">${pct}%</text>`;
  }
}

function calcWeight(v) {
  // Sum of weights from active/seed in-neighbors
  return Object.entries(INW[v]).reduce((acc, [u, w]) => {
    return acc + ((state[u] === 'active' || state[u] === 'seed') ? w : 0);
  }, 0);
}

function toggleSeed(id) {
  if (done) return;
  state[id] = state[id] === 'seed' ? 'inactive' : 'seed';
  buildSVG();
  updateButtons();
}

function stepRound() {
  if (done) return;
  let activated = 0;
  const next = [...state];
  for (let v = 0; v < NODES.length; v++) {
    if (state[v] !== 'inactive') continue;
    if (calcWeight(v) >= NODES[v].thresh) { next[v] = 'active'; activated++; }
  }
  state = next;
  round++;
  roundEl.textContent = round;
  buildSVG();
  if (activated === 0) {
    done = true;
    const total = state.filter(s => s !== 'inactive').length;
    statusEl.textContent = i18nFmt('Cascade complete — %n% node(s) adopted.', { n: total });
  } else {
    statusEl.textContent = i18nFmt('%n% node(s) activated this round.', { n: activated });
  }
  updateButtons();
}

function runAll() {
  // Advance rounds until no more activations
  while (!done) stepRound();
}

function reset() {
  state = NODES.map(() => 'inactive');
  round = 0;
  done = false;
  roundEl.textContent = 0;
  statusEl.textContent = '';
  buildSVG();
  updateButtons();
}

function updateButtons() {
  document.getElementById('btn-step').disabled = done;
  document.getElementById('btn-run').disabled = done;
}

document.getElementById('btn-step').addEventListener('click', stepRound);
document.getElementById('btn-run').addEventListener('click', runAll);
document.getElementById('btn-reset').addEventListener('click', reset);

buildSVG();
updateButtons();
Result
Console

Notice that the cascade can stall even when many nodes are activated — a node with a high threshold resists until almost all its neighbors have adopted. The order in which you pick seeds matters enormously: two seeds that reinforce each other's neighborhoods can reach far more nodes than two equally influential seeds that cover disjoint parts of the graph.

The Real Complexity

The LTM produces beautifully predictable cascades, but choosing the best seeds is computationally brutal.

  • Checking a given seed set is easy: simulate the cascade in O(∣V∣+∣E∣)O(|V| + |E|) time per round.
  • Finding the optimal kk-seed set is NP-hard. Kempe, Kleinberg and Tardos (2003) proved this by reduction from Set Cover. Exhaustively trying every kk-subset takes (∣V∣k)\binom{|V|}{k} evaluations — infeasible for realistic graphs.
  • The silver lining is submodularity. The influence function σ(S)\sigma(S) — the expected number of nodes activated by seed set SS — is monotone and submodular: adding a seed to a larger set produces at most as much extra coverage as adding it to a smaller set (diminishing returns). This structure enables the classic greedy algorithm: repeatedly add the seed that gives the greatest marginal gain.
  • The greedy algorithm achieves a (1−1/e)≈0.632(1 - 1/e) \approx 0.632 approximation guarantee — proven optimal for any polynomial-time algorithm under standard complexity assumptions. This means greedily selected seeds activate at least 63% as many nodes as the theoretically best seeds.

The result is a textbook example of a problem where the gap between "verify a solution" and "find the best solution" is provably large — yet a smart approximation rescues practical usability. This mirrors the situation in P vs NP: hard to solve optimally, but often tame with the right algorithm.

Where It Matters

The threshold cascade mechanism describes a surprising range of real phenomena:

  • Viral marketing: a company selects a small group of highly-connected early adopters to seed a product launch. LTM-based influence maximization guides which influencers to target — Kempe et al. showed the greedy strategy consistently outperforms hub-based heuristics on real social graphs.
  • Epidemiology: while disease spread is often modeled with SIR/SIS models, threshold-based variants capture behavioral immunity — people adopt protective behaviors (vaccines, masks) once enough peers do.
  • Opinion dynamics and political mobilization: voter turnout, protest participation, and norm adoption all show threshold effects. A community can remain inert until a critical fraction mobilizes, then tip rapidly.
  • Technology adoption: the classic "network externality" — a phone, a platform, a programming language becomes more valuable as more people use it, creating a threshold effect for switching.
  • Misinformation and fact-checking: understanding cascade dynamics helps design counter-campaigns: seeding accurate information into the right positions can preempt a false narrative before it tips.

The model's core insight — that local peer pressure accumulates into global cascades — applies wherever individual decisions depend on what neighbors do. It connects naturally to network flow analysis and to the theory of graph coloring (which asks about feasible local assignments under global constraints).

Conclusion

The Linear Threshold Model captures something profound: collective behavior emerges from purely local rules. Each node only watches its immediate neighbors and compares their combined weight to a personal threshold. Yet from these simple comparisons, global waves of adoption — or silence — arise.

Finding which seeds to plant is NP-hard, but submodularity saves us: the greedy algorithm guarantees more than 63% of the optimal spread, and that bound is tight. The LTM is therefore one of the cleanest illustrations of a theme running through all of theoretical computer science — that the hardness of optimization and the possibility of near-optimal approximation are two sides of the same coin, one visible in P vs NP and the other in the rich theory of approximation algorithms.

The next time an idea, a product, or a movement tips from niche to mainstream, remember: it probably crossed a threshold, one neighbor at a time.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/linear-threshold-model/Content licensed under CC BY-NC 4.0.