LAIM: Bridging the Gap Between Efficiency and Accuracy in Large-Scale Influence Maximization

TL;DR

Influence Maximization (IM) is critical for viral marketing but computationally expensive. This paper presents LAIM, a linear-time algorithm that approximates global influence via a recursive local-neighborhood calculation. It achieves state-of-the-art spread while being 7x to 50x faster and significantly more memory-efficient than previous benchmarks like IMM and TIM+.

Motivation: The Scalability Bottleneck

The Influence Maximization problem, first formalized by Kempe et al., is NP-hard. Early solutions relied on Monte-Carlo (MC) simulations, which are prohibitively slow ($O(knmRT)$). While subsequent works like CELF and RIS-based methods (IMM, TIM+) reduced this complexity, they still struggle with memory overhead or performance stability on mega-scale graphs.

The authors' core insight is simple: in the Independent Cascade (IC) model, influence usually doesn't propagate infinitely. Most impact is concentrated within a local vicinity. If we can accurately compute this "local influence" while avoiding the pitfalls of overcounting, we can approximate global influence in linear time.

Methodology: Recursive Local Influence

The technical heart of LAIM is its Influence Computation stage. To calculate the influence of node $u$ at layer $\gamma$, the authors propose a recursive formula that looks at the influence of its neighbors at layer $\gamma -1$.

The math involves an elegant subtraction to prevent "cycles" or re-activation in the IC model: $in{f}_G^{\gamma }(u)={\sum }_{v\in N(u)}{p}_{uv}(in{f}_G^{\gamma -1}(v)-p_{vu}in{f}_G^{\gamma -2}(u))$ This formula effectively removes the immediate back-influence of the parent node from the child’s account, ensuring the "one-time activation" rule of the IC model is respected.

The algorithm operates in two modes:

1. LAIM: A greedy iterative approach that recalculates influence after each seed selection.
2. FastLAIM: A single-pass approach that simply picks the top-$k$ nodes based on initial influence calculations.

Experiments & Results

The researchers tested LAIM on six real-world datasets, including Orkut (3M nodes) and LiveJournal (4M nodes).

1. Superior Spread

Contrary to the assumption that local approximation loses accuracy, LAIM and FastLAIM consistently matched or outperformed IMM and TIM+ in terms of actual influence spread (verified via 10,000 MC simulations).

2. Radical Speedup and Memory Efficiency

On the Orkut dataset, FastLAIM finished in 40 seconds, while IMM took nearly 5 minutes and TIM+ took over 30 minutes. More impressively, in smaller networks, LAIM used a fraction of the memory (megabytes vs. hundreds of megabytes), making it viable for resource-constrained environments.

Deep Insight & Conclusion

The success of LAIM proves that local structures in social networks are highly informative of a node's global cascading potential. By transitioning from global simulations to local recursive updates, the problem complexity shifts from being a function of stochastic simulations to a function of the network's degree distribution.

Limitations: While LAIM is incredibly fast, its current formulation is tied to the Independent Cascade model. Extending this recursive logic to the Linear Threshold (LT) model or continuous-time models would be a natural next step for the research community.

For practitioners, LAIM provides a robust "production-ready" tool for networks with hundreds of millions of edges where traditional greedy approaches would simply crawl.