Efficient Influence Maximization: Turning Hours into Milliseconds

TL;DR

Influence Maximization (IM) is the task of finding $k$ "seed" nodes in a social network to maximize the "word-of-mouth" effect. While the problem is NP-hard, this paper provides a breakthrough by proposing DegreeDiscountIC—a heuristic that runs in milliseconds yet matches the performance of greedy algorithms that typically take hours to complete.

Background: Why is IM so Hard?

The goal of Influence Maximization is simple: pick the most influential people to start a trend. However, calculating the exact expected influence of a seed set is notoriously difficult.

• The Greedy Trap: Classic algorithms pick seeds one-by-one. In each step, they simulate thousands of "cascades" to see who has the most impact.
• Scale Problem: On a graph with 30,000 nodes, these simulations (Monte-Carlo) can take days. Even the optimized CELF (Cost-Effective Lazy Forward) algorithm still takes hours.

Methodology: The "NewGreedy" and "DegreeDiscount"

The authors approached the efficiency problem from two distinct angles.

1. Optimized Greedy (NewGreedy)

Instead of simulating cascades for each node individually, the authors realized that for the Independent Cascade (IC) model, they could generate a random graph $G^{\prime }$ first. By finding reachable sets in $G^{\prime }$, they could update estimates for all nodes in a single linear scan. For the Weighted Cascade (WC) model, they adapted Cohen's Algorithm for randomized reachability estimation, further speeding up the process.

2. The Star-Graph Intuition (DegreeDiscountIC)

The most "elegant" contribution is the heuristic. Centrality measures like "Degree" usually fail because they ignore overlaps: if my friend is already a seed, my marginal influence is lower. The authors derived a mathematical discount: If a node $v$ has $t_v$ neighbors already selected as seeds, its degree $d_v$ should be treated as: $d_v-2t_v-(d_v-t_v)t_{v}p$ This formula accounts for the fact that $v$ might already be influenced by its neighbors, making its selection redundant.

Table 2: Time complexity comparison showing the dramatic efficiency of DegreeDiscount.

Experimental Battleground

The researchers tested their methods on real-life arXiv collaboration networks (NetHEPT and NetPHY).

• Influence Spread: DegreeDiscountIC essentially matched the influence spread of the optimal Greedy algorithm. In many cases, the lines on the graph were indistinguishable.
• Performance: While CELF took nearly 10,000 seconds, DegreeDiscount finished in 0.01 seconds.

Comparison of influence spread: DegreeDiscount (green) tracks the Greedy optimal (red) almost perfectly.

Critical Insight: The Heuristic Renaissance

This paper challenges the conclusion of earlier foundational work which suggested that simple heuristics are always inferior to greedy algorithms. By "fine-tuning" the heuristic (adding the degree discount), the authors proved that we can have our cake and eat it too: SOTA influence spread at blazingly fast speeds.

Limitations & Future Work

• The current specific discount formula $2t_v+(d_v-t_v)t_{v}p$ assumes a relatively small propagation probability ($p$).
• Future research could explore how these "discounts" change in much denser graphs or under different dynamics like the Linear Threshold (LT) model.

Conclusion

If you are building a viral marketing tool or analyzing information flow today, the takeaway is clear: Don't just use node degree, and don't waste days on Monte-Carlo simulations. A mathematically principled discount heuristic is often all you need to achieve high-performance results at scale.