The Million-Follower Fallacy, Submodularity, and Why Your Influencer Strategy Probably Doesn’t Work

A working introduction to influence maximization on graphs — what the math says, what the data says, and why marketing teams keep getting it wrong.

In 1994, the Hush Puppies brand was almost dead. Sales had fallen to 30,000 pairs a year, mostly to small-town shoe stores. Wolverine, the parent company, was preparing to phase the brand out. Then, sometime in late 1994, a few young people in downtown Manhattan started wearing them — bought cheap from thrift stores, worn ironically. Designers Isaac Mizrahi and Anna Sui put them on runway models. By the end of 1995 Wolverine sold 430,000 pairs; by 1996, 1.7 million. Malcolm Gladwell opened The Tipping Point with the story.

The Hush Puppies revival is the canonical example of viral diffusion in marketing economics: a product spreads through a social network not because of mass advertising but because of the network’s own structure. If you could engineer this, the implications are enormous — instead of a $100M Super Bowl ad, you find the right hundred customers, give them free samples, and the network does the rest. This is the seeding problem in viral marketing, and it has been studied seriously, with real mathematical machinery, since at least Domingos & Richardson (2001).

It is also a problem where most practitioners are doing something demonstrably suboptimal. This article walks through the model, the classical result, the surprising empirical fact about heuristics, and where the real machine-learning leverage actually is. All experiments use a 400-node synthetic social network and run end-to-end in under two minutes; all code is included.

The model: Independent Cascade

The standard formulation goes back to Kempe, Kleinberg & Tardos (KDD 2003). You have a directed social graph G = (V, E), where each edge (u, v) carries a probability p_uv that u will activate v if u itself has just been activated. You pick a seed set S ⊆ V of initial adopters. The Independent Cascade (IC) process unfolds in discrete time:

• At step 0, only the seeds are active.
• When a node u becomes active at step t, it gets exactly one chance, at step t+1, to activate each currently-inactive out-neighbour v, succeeding independently with probability p_uv.
• A node, once active, stays active forever — but it only ever attempts to activate each neighbour once.
• The process stops when no new activations occur.

The quantity we care about is σ(S), the expected number of active nodes at the end, averaged over the randomness of the cascade. The implementation is direct:

def simulate_ic(adj_prob, seeds, rng):
    active = set(seeds)
    frontier = set(seeds)
    while frontier:
        next_frontier = set()
        for u in frontier:
            for v, p in adj_prob.get(u, ()):
                if v in active:
                    continue
                if rng.random() < p:
                    next_frontier.add(v)
        active |= next_frontier
        frontier = next_frontier
    return active

σ(S) has no closed form for a general graph, so we estimate it by Monte Carlo — running the cascade a few hundred times and averaging. The figure below shows a single realisation on a 60-node synthetic social graph, starting from one seed.

A four-panel visualisation of one IC cascade on a 60-node graph. Orange = newly activated this step, dark blue = previously activated, grey = inactive. The cascade is trapped in one community; a second cluster at the bottom-left never gets infected.

The cascade is stochastic, monotone, and unforgiving of network structure: a single seed in the wrong community can have very large or very small reach depending on which edges happened to fire. Notice that the bottom-left cluster never gets infected — there are bridges to it, but none of them happened to fire in this realisation.

There is a sister model, the Linear Threshold (LT), in which each node draws a private threshold and activates when the weighted sum of its active in-neighbours exceeds it. The mathematical results below carry over essentially unchanged, so we’ll stick to IC for the rest of the article.

The optimization problem and what KKT 2003 actually proves

Given a budget of k seeds, the marketer wants to solve

max  σ(S)   subject to  |S| = k.

This is NP-hard. It’s reducible from the Set Cover problem in a few lines, so don’t bother looking for a polynomial-time exact algorithm. The usual moves of integer programming will not save you either: the objective σ is the expectation of a random combinatorial quantity, with no concise representation.

What Kempe, Kleinberg & Tardos proved is that you don’t need an exact algorithm. The function σ has two structural properties that together yield a strong approximation guarantee:

1. Monotonicity: adding a seed never reduces reach. S ⊆ T ⇒ σ(S) ≤ σ(T).
2. Submodularity: the marginal gain of a new seed is bigger when the current seed set is smaller. σ(S ∪ {v}) − σ(S) ≥ σ(T ∪ {v}) − σ(T) for all S ⊆ T not containing v. This is just the diminishing-returns property — the more your campaign already covers, the less any one new seed adds.

Nemhauser, Wolsey & Fisher (1978) had shown decades earlier that for any monotone submodular set function, the simple greedy algorithm — at each step, add the element with the largest marginal gain — achieves at least (1 − 1/e) ≈ 63% of the optimum. KKT 2003’s contribution was proving that σ satisfies the conditions, so the bound applies to influence maximization.

def greedy_seeds(adj_prob, nodes, k, n_runs=100, seed=0):
    chosen = []
    chosen_set = set()
    for _ in range(k):
        best_v, best_gain = None, -1.0
        base = expected_reach(simulate_ic, adj_prob, chosen_set,
                              n_runs=n_runs, seed=seed)
        for v in nodes:
            if v in chosen_set: continue
            r = expected_reach(simulate_ic, adj_prob, chosen_set | {v},
                               n_runs=n_runs, seed=seed)
            if (r - base) > best_gain:
                best_gain, best_v = r - base, v
        chosen.append(best_v)
        chosen_set.add(best_v)
    return chosen

This is grossly inefficient — O(k · n · R · |E|) where R is the number of Monte Carlo runs — and chokes on networks of more than a few thousand nodes. Leskovec et al. (KDD 2007) introduced CELF (Cost-Effective Lazy Forward), which uses submodularity itself to skip most of the work: a node’s marginal gain can only decrease as we add seeds, so we keep gains in a max-heap and re-evaluate only when a node bubbles to the top. Often 100x faster, exact same answer.

So far, so clean. The textbook story is: the problem is NP-hard, greedy gives 63%, CELF makes it tractable, ship it. This is also where the textbook story stops being true.

What practitioners actually do, and why it usually works

Marketing teams almost never run CELF. They look at follower counts. Or, on a slightly more sophisticated day, PageRank. These are O(n + m) one-shot computations, no diffusion model required, no Monte Carlo. They also sometimes use betweenness centrality, the “structural holes” / brokerage metric of Burt (1992), reasoning that a node that sits on many shortest paths is positioned to influence diverse audiences.

How much does this cost in expected reach? The honest answer, on most realistic networks, is almost nothing.

Here is the comparison on a 400-node scale-free social network (two Barabási–Albert communities joined by sparse bridges, IC with p_uv = 1/in-degree(v) by default). I ran the same five strategies, with the same random seed for the Monte Carlo evaluation, varying the seed budget from 1 to 25.

Two-panel chart. Left panel (‘standard regime’): CELF, PageRank, and Degree are essentially indistinguishable, all reaching ~90 nodes; betweenness lags slightly; random is far below. Right panel (‘Million Follower Fallacy’): CELF is clearly highest at ~53 reach, all the centrality heuristics are stuck around 41 — below the random baseline of 42.

The left panel is the standard regime: heuristics tie CELF to within Monte-Carlo noise, while running 100x faster. This is not a flaw in our experiment — it’s a robust empirical finding. Goyal, Bonchi & Lakshmanan (2011) did the same comparison on real datasets (Flixster, NetHEPT, DBLP) and found that high-degree heuristics consistently land within 5% of greedy. The structural reason is that on scale-free graphs, the top-k highest-degree nodes are also the top-k “best seeds” in any sensible diffusion model — the hubs really do dominate. KKT’s theoretical 63% guarantee is loose; the practical gap is usually far smaller.

So why does anyone use CELF? Two reasons. The first is the right panel.

The Million-Follower Fallacy

Cha, Haddadi, Benevenuto & Gummadi (ICWSM 2010) collected two billion tweets and looked at three measures of “influence” on Twitter: indegree (follower count), retweets, and mentions. Their bombshell finding is in the title: “Measuring User Influence in Twitter: The Million Follower Fallacy.” Follower count correlates almost not at all with retweets or mentions. The accounts at the very top of the follower distribution — celebrities, news outlets — get retweeted at a much lower rate per follower than mid-sized accounts. Aral & Walker (2012) found similar results in a randomized field experiment on Facebook.

The mechanism is intuitive. If you follow a thousand accounts, your feed is a firehose, and any individual post is unlikely to register. If you follow fifty, you actually read them. So engagement per follower drops with the source’s out-degree.

We can encode this directly in p_uv:

def assign_ic_probs(G, base_p, engagement_penalty, seed=2):
    in_deg = dict(G.in_degree())
    out_deg = dict(G.out_degree())
    for u, v in G.edges():
        recv = 4.0 / max(in_deg[v], 4)
        send = (1.0 / (1.0 + out_deg[u])) ** engagement_penalty
        G[u][v]["p"] = base_p * recv * send
    # ...renormalise so mean p = base_p

The right panel of the figure above is the same network, with engagement_penalty = 1.5 and the mean p_uv re-normalised to be the same as on the left. Now the picture is starkly different. CELF reaches 53 nodes; degree, PageRank, and betweenness are all stuck at 41 — below the random baseline of 42. The intuitive marketing playbook (“send free product to the people with the most followers”) is, in this regime, demonstrably worse than spending the same budget at random.

The reason is exactly what Cha et al. predicted. Top-degree nodes are dense in followers, but each of those edges has a tiny p_uv. Greedy notices this — its marginal gains are computed from σ, which depends on p_uv — so it picks differently. Heuristics, which look only at the graph’s topology, can’t see what’s happening on the edges.

This is the first half of the modern story: the optimization gap shows up when the diffusion process is not symmetric in graph topology. When edge weights matter, you need an algorithm that uses them.

The actual hard problem: where do p_uv values come from?

Notice that everything above assumes p_uv is given. Of course it isn’t. The probability that a particular customer will be persuaded by a particular friend’s recommendation is unobserved, idiosyncratic, and probably not even stable across time. You cannot just set p_uv = 0.05 and pretend you’ve solved the problem.

What you do have, in most realistic settings, is cascade data: timestamped logs of past adoption events. Someone retweets, someone replies, someone clicks “I bought this because Sarah recommended it.” From a corpus of these you can in principle estimate p_uv. The classical reference is Saito, Nakano & Kimura (2008), who give an EM-style maximum-likelihood estimator for IC. Goyal, Bonchi & Lakshmanan (2010) introduced a simpler “static Bernoulli” estimator that treats each edge as an independent Bernoulli trial:

For each cascade, walk through it in time order. For every edge (u, v) such that u activated at step t:

• if v activated at step t+1, count this as a success;
• if v was still inactive at step t+1 (i.e. never activated, or activated later through a different path), count this as a failure.

Take the success rate as p_uv. This estimator is biased — when v activates from multiple sources at once, the credit gets split somewhat arbitrarily — but it is fast and has no hyperparameters. With a structural Beta prior centred on 1/in_degree(v) (the KKT “weighted cascade” weight), it is also fairly robust to sparse data:

def estimate_probs_bernoulli(cascades, G, prior_strength=5.0):
    succ, trials = defaultdict(int), defaultdict(int)
    edges_out = {u: list(G.successors(u)) for u in G.nodes()}
    in_deg = dict(G.in_degree())

    for c in cascades:                              # c: {node: activation_step}
        for u, t_u in c.items():
            for v in edges_out[u]:
                t_v = c.get(v)
                if t_v is None:
                    trials[(u, v)] += 1
                elif t_v == t_u + 1:
                    succ[(u, v)] += 1
                    trials[(u, v)] += 1

    p_hat = {}
    for u, v in G.edges():
        p0 = 1.0 / max(in_deg[v], 4)               # structural prior
        s, n = succ[(u, v)], trials[(u, v)]
        p_hat[(u, v)] = (s + prior_strength * p0) / (n + prior_strength)
    return p_hat

Now we can ask the operationally interesting question: how much past cascade data do you need before model-based seeding meaningfully beats the parameter-free heuristic?

To answer that, I generated T cascades from the true Million-Follower-Fallacy world, fit p_hat from them, ran CELF on (G, p_hat), and then evaluated the chosen 20 seeds in the true world — measuring real reach, not estimated reach. The contrast is what matters.

Line chart with x-axis ‘Number of past cascades observed’ on a log scale from 10 to 3000, y-axis ‘Expected reach σ(S)’. Three horizontal reference lines: oracle (CELF on true probabilities) at 43.1, top-degree at 33.5, random at 34.9. The ‘CELF on learned probabilities’ line starts at ~34 with 10 cascades, stays flat through 100 cascades, then climbs to ~37 at 300 cascades and ~38.7 at 3000 cascades.

Three things in this chart deserve attention. First, the oracle (CELF with the true p_uv) reaches 43, the top-degree heuristic reaches 33.5 — worse than random — confirming the previous figure. Second, with very little data (T = 10 to T = 100 cascades), the learned model produces seeds barely better than random, because the structural prior dominates and the prior happens to look like degree-based seeding. Third, somewhere around T = 300 the learned model overtakes random and starts closing the gap to the oracle, ending at about 90% of the way there with 3000 cascades.

The message is not that more data is always worth it. The message is that the binding constraint in real viral marketing is almost never the optimization algorithm; it is whether you have enough observational cascades to learn the diffusion parameters at all. A team that runs greedy on garbage p_uv estimates is no better off than a team that picks by follower count. A team that has invested in collecting a few thousand clean cascades — including the failed ones, which is the part everyone forgets — has a real edge.

Where the modern (GNN) approaches fit

The Bernoulli MLE above is a strong baseline, but it has a serious limitation: it estimates p_uv for each edge independently. There is no sharing of information across edges, no use of node features (age, location, prior purchases), and no extrapolation to edges that were never exercised in the training cascades. Two edges between very similar pairs of users get totally separate estimates.

This is exactly the gap that GNN-based diffusion models close. The modern pipeline (papers worth reading: IMINFECTOR, Panagopoulos et al. 2020; GLIE, Panagopoulos et al. 2021; DeepIM, Ling et al. 2023) typically looks like:

1. Train a node encoder f(node) → ℝ^d with a GNN, using cascade prediction as the supervised signal.
2. Parameterise p_uv = σ(g(f(u), f(v), edge_features)) for some learned g.
3. Optimise the joint likelihood of all observed cascades end-to-end.

The schematic in PyTorch Geometric is short:

import torch
from torch_geometric.nn import SAGEConv

class CascadeModel(torch.nn.Module):
    def __init__(self, n_features, hidden=64, layers=2):
        super().__init__()
        self.convs = torch.nn.ModuleList(
            [SAGEConv(n_features if i == 0 else hidden, hidden)
             for i in range(layers)])
        self.edge_head = torch.nn.Sequential(
            torch.nn.Linear(2 * hidden, hidden),
            torch.nn.ReLU(),
            torch.nn.Linear(hidden, 1))

    def forward(self, x, edge_index):
        h = x
        for conv in self.convs:
            h = torch.relu(conv(h, edge_index))
        return h                                    # node embeddings

    def edge_p(self, h, src, dst):
        return torch.sigmoid(self.edge_head(
            torch.cat([h[src], h[dst]], dim=-1))).squeeze(-1)

The training loss is the negative log-likelihood of every observed activation/non-activation pair, summed over cascades. Once trained, you query edge_p(h, u, v) for every edge to get a p_hat matrix and feed it to CELF as before. Empirically these models reduce the data requirement by an order of magnitude — what took the Bernoulli MLE 3000 cascades takes a GNN about 300 — because they can pool information across structurally-similar edges.

The catch is that you need node features for the GNN to have anything to share information over. Pure topology gets you almost nothing beyond what the structural prior already provides; the lift comes from features like demographics, content tags, prior interaction history, and cross-platform identity links. This is also why the academic benchmarks (where features are skimpy) understate the gain that a real marketing team would see.

What the framework still ignores

A short list of things this entire formulation gets wrong, in roughly increasing order of importance:

The graph is treated as known and static. In practice you observe a sample of edges (the platform you happen to have logs from), and the network is reshaped daily by new follows, unfollows, and content-driven exposure. Even on Twitter the directed follow graph is a poor proxy for the actual influence graph, because algorithmic recommendation routes around it.

Cascade observability is biased. You see successful viral events because they are visible; the equivalent failed launches are unrecorded. Any estimator trained on observed cascades is fitted to survivorship bias.

Adoption is not Bernoulli. People talk to each other; thresholds compound; brand sentiment shifts; everyone in a community sees the campaign at once. Any fixed p_uv is a reduction of dynamics that have memory and feedback.

The biggest missing thing, though, is the result of Watts & Dodds (2007), “Influentials, Networks, and Public Opinion Formation.” They simulated influence cascades on millions of synthetic networks under a wide range of plausible parameter settings and found that, in most regimes, the size of cascades is determined far more by the susceptibility distribution of ordinary people than by who the seed was. The “influentials hypothesis” — the implicit theory of any influencer marketing strategy — works only in narrow corners of the parameter space, and there is empirical evidence that real social networks rarely sit in those corners. If they’re right, even a perfect solution to the influence-maximization problem is solving a problem of secondary importance: the variance in marketing outcomes is mostly about whether the world is ready to adopt your product, not about whom you ask first.

That is a sobering note for what is otherwise a very pretty piece of mathematics, and it is exactly the kind of caveat that the modelling tradition tends to bury. It is worth remembering when the next deck arrives recommending you spend $400,000 on twelve influencers.

When to use what

If you have no past cascade data and are spending less than a few hundred thousand dollars on a campaign: top-degree-by-follower-count plus diversity constraints (don’t pick three accounts in the same community) will get you most of what is gettable. Don’t bother with greedy.

If you have a few thousand observed cascades and your domain probably exhibits engagement-vs-reach trade-offs (most consumer markets do): fit a Bernoulli MLE with a structural prior, run CELF on the result, and you should outperform the heuristic by 10–30%.

If you have rich node features and tens of thousands of cascades: train a GNN-based diffusion model, validate it by holding out cascades, and use the inferred edge probabilities downstream.

If you are spending the money on the campaign anyway: spend a small slice of it on instrumentation, so that next year you have the cascade data you need. The compounding return on observability is, in the long run, much higher than the return on any one round of optimisation.

Brian Curry is an applied AI researcher and causal economist working at the intersection of causal inference, cognitive AI architecture, and the economics of intelligent automation. He is the founder of Vector1 Research, an independent lab publishing on agent systems, AI governance, marketing science, and the macroeconomics of AI-driven transformation. He has led data science and applied AI initiatives across enterprises including Koch Industries ($125B), Tractor Supply (Fortune 300), Vail Resorts, Hallmark, Garmin, AT&T, and McClatchy, and founded the 1,500-member KC AI Lab in 2016. His open-source contributions include Papilon, PyCausalSim, MeaningFlow, and Memory-Node Encapsulation. He writes daily at medium.com/@brian-curry-research and at vector1.ai.