Unlocking the "Strict" Side of Social Influence: Moving Beyond Simple Submodularity

TL;DR

While it has long been known that social influence spread is submodular (exhibiting diminishing returns), this paper proves for the first time that under certain conditions, it is strictly submodular. By assuming $k$-connected graph structures and strictly submodular marginal threshold functions, the authors demonstrate that the greedy algorithm for influence maximization performs strictly better than the classical $(1-1/e)$ theoretical floor.

Perspective: From Diminishing Returns to Strict Inequality

In the world of combinatorial optimization, submodularity is the "convexity" of discrete sets. Since the seminal work by Kempe et al. (2003), we have relied on this property to justify why a simple greedy strategy works well for picking "influencers" in a network. However, "submodular" often includes the possibility of equality—where adding a node to a small set or a large set results in the exact same gain.

This paper asks: When is the gain strictly better for the smaller set? This is not just a mathematical nuance; strict submodularity is the engine behind the uniqueness of optimal solutions and improved algorithmic convergence.

The Core Challenge: The Probabilistic Gap

The influence spread $\sigma (A)$ is the expected number of active nodes. Proving it is submodular is hard because it involves integrating over all possible random thresholds $het{a}_v$ for every node.

The authors tackle the General Threshold Model, where a node $v$ becomes active if the weight of its active neighbors $f_v(S)$ exceeds a random threshold $het{a}_v$.

The difficulty lies in showing that $f(A)+f(B)>f(A\cup B)+f(A\cap B)$—the strict version of the submodular inequality.

Methodology: Levering Graph Connectivity

The researchers' breakthrough relies on two pillars:

1. Strict Incremental Definition: They characterize strict submodularity through the lens of marginal gains: ${\Delta }_{x}f(A)>{\Delta }_{x}f(B)$ for $A\subset B$.
2. K-Connectivity: By assuming the network is $k$-connected, they ensure there are enough paths for a single seed to "make a difference."

They utilize a modified process $Q^{-}$, which allows for analytical tracking of how influence "overflows" when moving from a seed set $A$ to a larger set $B$. By finding a specific "neighborhood" of threshold values where a path from a new seed $x$ reaches a node $y\in B\setminus A$, they prove that the marginal influence of $x$ on $A$ is inherently larger than on $B$.

Results: Why "Strict" Matters for Performance

The most impactful result for practitioners is Theorem 3.5. It updates the classic Nemhauser (1978) result for the greedy algorithm:

• Classical Bound: $f(A)\ge (1-e^{-1})opt$
• New Bound: $f(A)>(1-e^{-1})opt$

While the numerical constant $(1-1/e\approx 0.632)$ remains the same, the strict inequality implies that the worst-case scenario (where greedy barely hits the limit) is avoided in $k$-connected networks with strictly submodular local thresholds.

Deep Insight & Conclusion

This work bridges a gap between pure set-function theory and social network analysis. It reveals that the topology of the network (connectivity) and the psychology of the nodes (threshold function curvature) work together to create a search space that is well-behaved.

Limitations: The requirement for $k$-connectivity is strong. In extremely sparse or fragmented "echo chamber" networks, strict submodularity might break down, returning us to standard submodularity where gains can stagnate.

Future Outlook: The authors suggest extending this to DR-submodularity on integer lattices. This would move the conversation from "binary" influence (active/inactive) to "intensity-based" influence, which is far more applicable to modern viral marketing and digital engagement metrics.