TL;DR
While most influence maximization research assumes "diminishing returns" (submodularity), real-world social networks often exhibit complex, non-submodular behaviors. This paper introduces the concept of $\epsilon$-almost submodular functions to model these "nearly" submodular nodes and proves that even a small number of such nodes makes the problem significantly harder to solve, while providing new algorithms that offer provable performance guarantees in these tricky scenarios.
What Problem Does This Paper Address?
Influence Maximization (IM) is the classic problem of finding the $k$ most influential people in a social network to kickstart a trend or viral marketing campaign. For years, the field has relied on the assumption of submodularity. In plain English, this means "diminishing returns": the more friends you have who have already adopted a product, the less additional impact each new friend has on your decision to join.
However, empirical studies of networks like Flickr and LiveJournal show that reality is messier. Sometimes, you need a "critical mass" of friends to join before you feel the pressure to follow suit—a phenomenon called complex contagion. This creates a non-submodular "superlinear" effect. The challenge this paper tackles is: How do we maximize influence when the "diminishing returns" rule is broken by a fraction of the population?
Methods
The authors introduce a new mathematical framework: $\epsilon$-almost submodular functions. These are functions that aren't perfectly submodular but are "sandwiched" between two submodular functions within a factor of $(1-\epsilon)$.
The paper contributes in three main areas:
- Hardness Proofs: They use a "probabilistic-AND gate" gadget (built using binary trees) to show that if even a sublinear number of nodes are non-submodular, the problem becomes incredibly difficult to approximate (specifically, no $1/n^{\gamma/c}$ approximation is possible unless P=NP).
- The Galg-L Algorithm: To combat this hardness, they propose a greedy approach. Instead of trying to optimize the messy non-submodular function directly, they replace the threshold functions of the "difficult" nodes with their submodular lower bounds and then run a standard greedy algorithm.
- Theoretical Analysis: They use a clever mapping between probability spaces to prove that their algorithm achieves an approximation ratio of $(1 - 1/e)(1 - \epsilon)^\ell$, where $\ell$ is the number of non-submodular nodes.
Datasets
The authors evaluated their approach on three real-world social network datasets:
- NetHEPT: An academic collaboration network from arXiv (High Energy Physics) with ~15k nodes.
- Flixster: A movie rating social site where edges represent users rating the same movie shortly after one another (~29k nodes).
- DBLP: A large-scale computer science bibliography collaboration network (~650k nodes).
They manually injected two types of non-submodular functions ($\epsilon$-AS-1 and $\epsilon$-AS-2) into these networks to simulate different real-world behaviors observed in previous sociological studies.
Key Insights and Ideas
- Local Breaks Global: A major "aha moment" is the realization that submodularity is fragile. Even if most of the network behaves "normally," a tiny fraction of "complex" nodes can destroy the global submodularity of the influence spread, making standard greedy algorithms theoretically unreliable.
- The Power of the Sandwich: The authors show that you don't need to solve the non-submodular problem perfectly. By "sandwiching" the difficult nodes between submodular bounds, you can still leverage highly efficient, scalable algorithms (like TIM+) while maintaining a mathematical guarantee on how far off you might be.
- The "Leader" vs. "Follower" Distinction: The model reflects empirical findings that "ordinary users" usually follow submodular patterns, while "opinion leaders" or specific communities might require more complex triggers.
Key Results
- Theoretical Hardness: The paper establishes a strong negative result: influence maximization is significantly harder to approximate in the non-submodular regime than previously thought, even when nodes are "close" to being submodular.
- Algorithm Performance: In experiments, their proposed algorithms (TIM-L and TIM-U) consistently outperformed standard baselines like PageRank, High-degree heuristics, and even the naive Greedy algorithm in terms of total influence spread.
- Scalability: By integrating their theory with the TIM+ (Reverse Reachable Set) technique, they demonstrated that their approach can handle networks with millions of edges (like DBLP) in a reasonable timeframe, whereas a naive greedy approach would take weeks.
Limitations and Future Work
The primary limitation is the dependence on $\ell$ (the number of non-submodular nodes). As the number of "complex" nodes grows, the theoretical approximation guarantee $(1-\epsilon)^\ell$ decays exponentially. This means the algorithm is most effective when the non-submodularity is localized to a relatively small part of the network.
For future work, the authors suggest:
- Exploring models with arbitrary non-submodular functions that don't necessarily fit the $\epsilon$-almost submodular definition.
- Developing faster versions of the greedy process for these complex functions, as the current "sandwich" method is a workaround for the fact that non-submodular functions don't fit the "Triggering Model" used by modern fast IM algorithms.
Summary updated