The Linear Threshold Model

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 $v$ in a graph holds a threshold $\theta_v \in [0,1]$, drawn uniformly at random or set by hand. Each directed edge $(u, v)$ carries a weight $w_{u,v} \geq 0$ such that the weights of all edges into $v$ 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:

$$\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 $S$ 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 $k$ seeds, which set $S$ of size $k$ triggers the largest final cascade? This turns out to be a deep computational problem connected to submodular optimization.

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.

<!-- {{c_html_intro}} -->
<div class="controls">
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="status-row">
  <span class="label">{{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="{{aria_graph}}"></svg>
<p class="hint">{{hint_click}}</p>

/* {{c_css_intro}} */
* { 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; }
/* {{c_css_nodes}} */
.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; }

// Code not found

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 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|)$ time per round.
• Finding the optimal $k$-seed set is NP-hard. Kempe, Kleinberg and Tardos (2003) proved this by reduction from Set Cover. Exhaustively trying every $k$-subset takes $\binom{|V|}{k}$ evaluations — infeasible for realistic graphs.
• The silver lining is submodularity. The influence function $\sigma(S)$ — the expected number of nodes activated by seed set $S$ — 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) \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.

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

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.