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.
- Group-Level Influence: As Hieu V. Duong et al. demonstrate in Groups Influence with Minimum Cost in Social Networks, when a group is only considered "influenced" if the collective score of its members crosses a specific threshold, the resulting function is neither submodular nor supermodular.
- Probabilistic Coverage: If an organization requires a guarantee that a specific reach threshold will be met with a minimum probability, Peng Zhang et al. show in Minimizing seed set selection with probabilistic coverage guarantee in a social network that the probability distribution over network coverage completely breaks the diminishing returns property.
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.
- Diffusion Games: In competitive settings, S. Rasoul Etesami et al. show in Complexity of Equilibrium in Diffusion Games on Social Networks that tie-breaking rules for equidistant seeds introduce non-submodular utilities. Adding more seeds can paradoxically create neutral, non-infected zones, reducing total reach.
- Node Blocking: When mitigating misinformation by strategically "blocking" nodes, the benefit of blocking a specific user depends heavily on which other users are blocked. The authors of Efficient Influence Minimization via Node Blocking (Jinghao Wang et al.) and Minimizing the Influence of Misinformation via Vertex Blocking (Jiadong Xie et al.) note that the reduction in spread is non-supermodular, meaning simple additive heuristics cannot navigate the complex structural dependencies between blockers.
- Temporal Dynamics: When accounting for real-world delays—such as fake news spreading faster than the truth—the objective function becomes highly non-submodular, as shown by Farnoosh Hashemi et al. in Misinformation Mitigation under Differential Propagation Rates and Temporal Penalties.
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.
3. Network-Aware and Structural Search
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.