networks
Choose the first hundred believers
It is 2003, and viral marketing has a budget and a graph: a company can seed its product with a hundred free samples across a social network of millions, hoping cascades of word-of-mouth do the rest. Formalize influence spread as a probabilistic process on the graph, then face the optimization: choosing the seed set that maximizes expected adoption is NP-hard — but the objective has a saving structure, diminishing returns, under which a greedy algorithm carries a provable guarantee of a constant fraction of optimal. Prove it, and say when the model's assumptions break. Get it wrong and the budget is spent on celebrities whose cascades overlap wastefully — or the same mathematics is later deployed, unexamined, to seed political messaging.
Who this problem belongs to
The two figures whose methods fit it best, out of 48 in contention.
Kleinberg co-authored, with David Kempe and Eva Tardos, 'Maximizing the Spread of Influence through a Social Network' (2003), the paper that literally formalized this exact problem: modeling cascades as a probabilistic diffusion process on a graph, proving the influence-maximization objective is NP-hard, and proving that its submodularity, diminishing returns from adding more seeds, lets a greedy algorithm achieve a provable constant-factor approximation to optimal. That paper is not analogous to this scenario, it is its direct historical origin, down to the same year and the same seed-set framing. His broader research on network structure and cascades gives him unmatched authority on when the model's independence and threshold assumptions break in real social data. No other career on this card maps this precisely onto the problem's exact mathematics and history, which is why his score sits at the maximum.
Guestrin's research on submodular function optimization, including provably near-optimal algorithms for placing sensors and detecting outbreaks under budget constraints with Krause and Leskovec, directly extends the Kempe-Kleinberg-Tardos influence-maximization framework this problem describes, proving faster, scalable greedy variants that exploit submodularity's diminishing-returns structure at real-world scale. His distributed machine learning systems work (GraphLab) also gives him genuine engineering authority over running these algorithms on large social graphs, the practical half of this problem's demand. His interpretability research (LIME) further shows sustained interest in understanding when and why a model's recommendations, seed sets, in this case, actually work. His score sits just below Kleinberg's founding formalization because his contributions, while foundational to the field's scaling, arrived as direct extensions rather than the original problem.
Fought here
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
48 figures are scored on this problem. Draw it in a battle to see where you land.