Introduction
Influence Maximization (IM) is a fundamental problem in social network analysis, where the goal is to select a set of $k$ "seed" nodes to maximize the expected number of influenced individuals in a network. In practice, decision-makers often choose between two strategies: a non-adaptive approach, where all seeds are selected simultaneously, and an adaptive approach, where seeds are selected sequentially based on observed feedback from previous cascades.
The performance difference between these two strategies is quantified by the adaptivity gap—the ratio of the expected spread of the optimal adaptive policy to that of the optimal non-adaptive policy. While adaptivity inherently offers an advantage, determining the magnitude of this advantage has remained a significant theoretical challenge. This paper provides the first sub-linear upper bound on the adaptivity gap for general networks and offers tightened bounds for specific graph structures.
The Adaptivity Gap Problem
In the Independent Cascade (IC) model, the adaptivity gap represents how much better a strategy can perform if it reacts to real-time network feedback. Previous research established that the gap is at least $1.58$ (specifically $1 - 1/e$), but upper bounds for general graphs remained "linear" ($O(n)$), where $n$ is the number of nodes. For large-scale social networks, a linear bound is effectively uninformative, as it suggests the adaptive advantage could scale proportionally with the network size.
This research addresses the gap under the full-adoption feedback model, where the decision-maker observes the entire cascade triggered by a seed before selecting the next one. The goal is to prove that the advantage of being adaptive is much smaller than previously feared.
Methodology: The Hybrid Policy
To derive tighter bounds, the authors move away from traditional tools like Poisson processes and multilinear extensions, which often introduce mathematical "slack." Instead, they introduce a novel randomized hybrid non-adaptive policy.
This hybrid policy bridges the gap between adaptive and non-adaptive strategies by constructing a selection mechanism that combines elements of both. It begins with a subset of seeds from an optimal non-adaptive set and then selects subsequent seeds based on the probability distribution of an optimal adaptive policy. This approach allows for a recursive mathematical analysis that links the expected spread of both policies more directly, avoiding the approximation losses that plagued earlier proof techniques.
Key Results and Insights
Breaking the Linear Barrier
The paper’s most significant contribution is the proof that for any general graph, the adaptivity gap is upper-bounded by $n^{1/3} + 1$. This is the first sub-linear bound ever established for general networks, proving that the benefit of adaptivity is fundamentally constrained by the network's size in a non-linear fashion.
The Role of Network Structure
The research demonstrates that the adaptivity gap is closely linked to the "branchiness" or complexity of the graph. The authors evaluate several graph classes:
- General Graphs: Upper bound of $n^{1/3} + 1$.
- In-arborescences (Trees): The bound was tightened from $\approx 3.16$ to $2e^2 / (e^2 - 1) \approx 2.31$. This brings the theoretical upper bound significantly closer to known lower bounds.
- $\alpha$-bounded Graphs: In undirected graphs where the sum of degrees higher than two is limited by a constant $\alpha$, the gap is at most $\sqrt{\alpha} + O(1)$.
- Paths and Cycles (0-bounded): For these simple structures, the gap is at most $3e^3 / (e^3 - 1) \approx 3.16$.
These results suggest that in networks with low complexity—such as those that are mostly paths or cycles—the benefit of real-time adaptation is remarkably small.
Limitations and Future Directions
While the $n^{1/3}$ bound is a major theoretical advancement, a significant distance remains between this upper bound and the known constant lower bounds ($\approx 1.58$). Closing this remaining gap is a primary objective for future research.
Additionally, the current study assumes full-adoption feedback. Future work could apply the hybrid analysis technique to myopic feedback models, where only the immediate neighbors of seeds are observed. Finally, the results are specific to the Independent Cascade model; the Linear Threshold (LT) model remains an open challenge, as it lacks the "adaptive submodularity" property that facilitates the greedy strategies used in this analysis.
Summary updated