Introduction
Influence Maximization (IM) is a fundamental problem in social network analysis, aimed at identifying a small set of "seed" nodes that can trigger the largest possible cascade of information. While the problem is NP-hard, greedy algorithms provide a $(1 - 1/e)$ approximation ratio, provided the influence spread can be accurately estimated. However, traditional estimation methods like Monte Carlo simulations are computationally prohibitive for large-scale networks, and modern sampling-based methods (e.g., RIS, IMM) face significant memory and time constraints as networks scale to billions of edges.
This paper proposes a novel "hop-based" approach to bridge the gap between fast but inaccurate heuristics and accurate but slow sampling methods. By focusing on the first few steps of information propagation, the authors introduce algorithms that achieve state-of-the-art accuracy with significantly reduced computational overhead.
The Shallow Cascade Hypothesis
The core motivation for this work is the empirical observation that in real-world social networks, the vast majority of influence spread occurs within the first few "hops" from the seed nodes.
As shown in the figure above, the marginal gain in influence spread diminishes rapidly beyond the first two hops. By leveraging this "shallow cascade" reality, the authors transform the stochastic simulation problem into a deterministic probability update problem focused on local neighborhoods.
Methodology
The authors introduce two primary algorithms, OneHop and TwoHop, which calculate the exact activation probabilities for nodes within one or two hops of the seed set.
Algorithmic Framework
The proposed approach operates within the standard greedy framework for influence maximization.
To make this framework efficient, the authors contribute:
- Exact Short-Hop Calculation: Derivation of exact formulas for activation probabilities within a 2-hop radius under the Independent Cascade (IC) model.
- Incremental Updates: The
OneHopIncrementandTwoHopsIncrementalgorithms allow for local updates to influence scores. When a new seed is selected, only the probabilities of nodes within its 2-hop neighborhood are recalculated, ensuring scalability. - TwoHop-O (Upper Bounding): To address the bottleneck of the initial seed selection round, a mathematical upper bound on node influence is used in conjunction with the Cost-Effective Lazy Forward (CELF) optimization.
- Theoretical Foundations: The authors prove that their hop-based influence function is both submodular and monotone, preserving the theoretical guarantees of the greedy approach.
Experimental Evaluation
The algorithms were tested on datasets ranging from citation networks (NetHEPT) to massive social graphs like Twitter (42M nodes, 1.5B edges).
Key Findings
- Effectiveness: TwoHop achieved influence spread nearly identical to state-of-the-art sampling methods like IMM and D-SSA, outperforming traditional heuristics.
- Efficiency: On the massive Twitter dataset, TwoHop-O was approximately four orders of magnitude faster than IMM, completing seed selection in 15 seconds compared to over 2,000 seconds for IMM.
- Scalability: The hop-based approach maintains a memory footprint of $O(|V|)$, allowing it to process billion-edge graphs on a single machine where other methods failed due to memory exhaustion.
Conclusion
By focusing on the local nature of influence spread, the hop-based approach provides a highly efficient and effective solution for Influence Maximization in massive networks. While the method assumes relatively shallow cascades—a condition met by most real-world social networks—it offers a robust alternative to complex sampling techniques, particularly when computational resources or time are limited.
Summary updated