Submodular Optimization for Influence Maximization in Networks

This direction is merged into another direction: greedy approximation guarantees. Its last version stays readable and citable here.

Version 1 of 1167 papers244 conceptsfrozen 2026-10-04

Imagine you are launching a new app and want it to go viral. You have a limited budget to give free "pro" accounts to 100 people. To maximize the total number of users, should you pick the 100 most famous celebrities? Or 100 people from different social circles? This is the Influence Maximization (IM) problem: selecting a small set of "seed" nodes in a network to trigger the largest possible cascade of adoption.

At first glance, this problem is a computational nightmare. In a network of millions, the number of ways to choose 100 seeds is astronomical—far beyond what any supercomputer could check. However, research over the last two decades has revealed that influence in social networks follows a mathematical pattern called submodularity. This property turns an impossible search into a simple, provably effective strategy.

The Intuition of Diminishing Returns

The core of this research direction is the observation that social influence exhibits "diminishing returns." In mathematics, this is known as submodularity.

Think of it this way: if you have already convinced 1,000 people in a neighborhood to use your app, adding one more influential neighbor provides a small marginal gain because most of their friends are already "infected" by the idea. But if you only had 10 people, that same influential neighbor would reach a much larger pool of "uninfected" friends.

David Kempe 0001 and Éva Tardos formalized this in their landmark paper, Maximizing the spread of influence through a social network. They proved that for common models of social contagion, the influence function is submodular. This means that as the set of seeds grows, the "marginal boost" you get from adding one more seed always stays the same or decreases.

Why the Greedy Algorithm Wins

Because influence is submodular, we don't need to find the perfect global set of seeds. Instead, we can use a Greedy Algorithm:

  1. Start with an empty set.
  2. Find the single person who provides the largest increase in expected spread.
  3. Add them to your set.
  4. Repeat until your budget is spent.

Kempe et al. (2003) proved that this simple, "myopic" strategy is guaranteed to reach at least 63% (specifically $1 - 1/e$) of the optimal possible influence. You don't need to be perfect; you just need to be greedy.

While Kempe's work focused on simple models, Elchanan Mossel and Sebastien Roch provided the "missing mathematical link" in On the Submodularity of Influence in Social Networks. They proved that if individual interactions follow diminishing returns, the entire network-wide spread inherits that property, confirming that greedy strategies are mathematically sound for a vast range of viral marketing scenarios.

Beyond Viral Marketing

The power of submodularity extends far beyond selling products. Researchers have realized that any process that "spreads" through a network can be optimized using these same principles:

Scaling to the Real World

The original greedy algorithm was effective but slow, requiring millions of simulations to estimate influence. To make this practical for modern social media, researchers like Jure Leskovec and Andreas Krause developed methods like NETINF to infer hidden networks from timing data (Inferring networks of diffusion and influence).

More recently, Wei Chen has pushed the boundaries of efficiency, developing algorithms that can handle millions of nodes by using "reverse reachable" graph structures. These optimizations allow us to apply the 63% guarantee to networks the size of the entire internet.

Summary

The research direction of Submodular Influence Maximization works because it identifies a fundamental "law of nature" in networks: the more you have already influenced a system, the harder it is to influence it further. By proving that this "diminishing returns" property holds, researchers have transformed the chaotic problem of social cascades into a rigorous, solvable science. Whether we are stopping a pandemic, securing a power grid, or launching a startup, submodularity gives us a mathematical "north star" for making the most impactful choices.

Papers in this version

Showing 60 of 167 papers.

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_submodular_optimization_for_influence_ma_d8c3c00e,
  title = {Submodular Optimization for Influence Maximization in Networks},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/submodular-optimization-for-influence-maximization-in-networks/rdr_d8c3c00e982145ce941e6d284dacefc7},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_submodular_optimization_for_influence_ma_d8c3c00e_v1,
  title = {Submodular Optimization for Influence Maximization in Networks},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/submodular-optimization-for-influence-maximization-in-networks/rdr_d8c3c00e982145ce941e6d284dacefc7/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}