Non-Submodular Influence Optimization in Social Networks

37 concepts23 papers1 proposal

In the study of viral marketing and information diffusion, the gold standard for optimizing network influence has long relied on a mathematical property called submodularity. Submodularity formalizes the law of diminishing returns: adding an initial "seed" user to a small group of influencers yields a larger marginal increase in total network reach than adding that same user to a much larger group.

When an objective function is submodular, a simple, intuitive greedy algorithm—picking the single best node at each step—is guaranteed to find a solution within roughly 63% ($1 - 1/e$) of the global optimum.

However, real-world networks rarely behave so simply. When we introduce complex human behaviors, competition, or timing constraints, the assumption of diminishing returns collapses. We enter the domain of non-submodular influence optimization, where the marginal benefit of adding an influencer can actually increase as the seed set grows. In these scenarios, standard greedy algorithms fail spectacularly, demanding entirely new theoretical frameworks and algorithmic paradigms.


Why Submodularity Fails in the Real World

To understand why submodularity breaks down, consider how information actually spreads. In simple contagion models, a single exposure to a piece of news is enough to trigger adoption. But real-world scenarios often involve complex contagions, where individuals require reinforcement from multiple social ties before changing their behavior.

1. Cumulative Activation and Synergy

When adoption requires multiple exposures—such as buying an expensive product or joining a social movement—nodes exhibit threshold behavior. As explored by Xiaohan Shan et al. in Cumulative activation in social networks, a user might only activate after a cumulative threshold of peer influence is met.

Imagine a user who needs two friends to adopt a product before they buy it. If you select only one of their friends as a seed, the marginal gain is zero. If you select a second friend, the user suddenly activates. Here, the marginal benefit of the second seed is higher than the first. This synergy directly violates submodularity.

2. Group Thresholds and Confidence Guarantees

Often, the goal is not merely to maximize the expected number of individual clicks, but to influence entire communities or achieve high-certainty targets.

3. Competition and Information Minimization

When multiple entities compete for the same network, or when the objective shifts to minimizing the spread of harmful information, the optimization landscape warps further.


The Inapproximability Wall

What happens to our algorithms when submodularity disappears? They hit a severe computational wall. Without diminishing returns, local greedy choices can lead down dead-end paths, missing global optima entirely.

The theoretical severity of this breakdown is stark. In Influence Maximization with $\varepsilon$-Almost Submodular Threshold Functions, Q. Li proves that if even a sublinear number of nodes deviate slightly from submodularity (termed $\varepsilon$-almost submodular), the problem becomes NP-hard to approximate within any meaningful factor. A parallel study by Qiang Li et al. (Influence Maximization with ε-Almost Submodular Threshold Functions) demonstrates that theoretical approximation guarantees decay exponentially as the number of non-submodular nodes grows.

Furthermore, Grant Schoenebeck et al. show in Beyond Worst-case (In)approximability of Nonsubmodular Influence Maximization that there is a sharp mathematical threshold: even minor relaxations like 2-quasi-submodularity render the problem NP-hard to approximate, even when assuming simplified network structures like hierarchical blockmodels. Standard heuristics like greedy selection or centrality metrics fail completely, as noted by Matteo Castiglioni et al. in Election Manipulation on Social Networks: Seeding, Edge Removal, Edge Addition.


Algorithmic Strategies for the Non-Submodular Landscape

To overcome these limitations, researchers have developed alternative algorithmic paradigms that embrace or bypass non-submodularity.

1. Acting Locally for Complex Contagions

In submodular settings, the optimal strategy is to spread seeds far apart to avoid overlap. However, for complex contagions, Grant Schoenebeck et al. demonstrate in Think Globally, Act Locally: On the Optimal Seeding for Nonsubmodular Influence Maximization that the optimal strategy is the exact opposite: clustering seeds tightly within a single community. This local concentration triggers a synergistic chain reaction that cascades outward, turning the lack of submodularity into an advantage.

2. Sandwich Approximation

When an objective function is neither submodular nor supermodular, the authors of Competitive Influence Maximization within Time and Budget Constraints in Online Social Networks: An Algorithmic Approach (Hieu V. Duong et al.) utilize a "Sandwich Approximation" framework. This technique bounds the non-submodular objective between a submodular lower bound and a supermodular upper bound, allowing algorithms to inherit provable performance guarantees by optimizing the bounding functions.

Other approaches exploit graph topology directly. Matteo Bergamaschi et al. introduce a Network-aware Direct Search (NaDS) method in An Efficient Network-aware Direct Search Method for Influence Maximization, restricting the optimization search space to nodes directly connected to current seeds, bypassing global non-submodular complexity. For misinformation blocking, Jiadong Xie et al. leverage "dominator trees" to map out the complex, non-additive dependencies between blockers, accelerating optimization by orders of magnitude.

Key Foundational Work

Threshold Models for Competitive Influence in Social Networks (2010) — contributed 2 concept elements to this direction.
Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization (2011) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_non_submodular_objective_functions_c54b15f0,
  title = {non-submodular objective functions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-submodular-objective-functions/rdr_c54b15f046e04d58b6cefb1f39349184},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_non_submodular_objective_functions_c54b15f0_v1,
  title = {non-submodular objective functions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-submodular-objective-functions/rdr_c54b15f046e04d58b6cefb1f39349184/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake