Efficient Influence Maximization: Scaling Viral Marketing with Set Covering Greedy Algorithm

TL;DR

This research addresses the bottleneck of "Influence Maximization"—finding the $K$ most influential people in a network to trigger a cascade of information. While the standard Greedy algorithm is accurate, it is excruciatingly slow. The authors propose the Set Covering Greedy (SCG) algorithm, which uses structural neighborhood covering to achieve better influence results than traditional methods in a fraction of the time (seconds vs. hours).

The Scalability Wall in Social Networks

In the world of viral marketing, identifying "seeds" (initial adopters) is the holy grail. However, we face a dual challenge:

1. Complexity: Finding the optimal $K$ nodes is NP-hard.
2. Redundancy: Simply picking people with the most friends (Degree Centrality) often fails because their social circles overlap. If two "influencers" share the same audience, your second seed is wasted.
3. Computational Cost: The standard "Simple Greedy" algorithm requires running 10,000+ Monte Carlo simulations for every potential node selection to estimate influence spread. For a network of 30,000 nodes, this can take days or weeks of CPU time.

Methodology: The Set Covering Intuition

The authors' core "Insight" is that influence is essentially a coverage problem. Instead of simulating a random process, they look at the Geodesic Distance ($d_{u,v}$).

1. The SCG Algorithm

The SCG algorithm treats each node as the center of a potential "influence sphere."

• Step 1: Define an $m$-neighbor set $S_u^{(m)}$ for every node $u$ (nodes within distance $m$).
• Step 2: Pick the node $v$ that covers the most "uncovered" neighbors.
• Step 3: Mark all nodes in $v$'s neighborhood as "covered" and repeat until $K$ nodes are chosen.

This approach explicitly prevents Neighborhood Overlapping, ensuring that each selected seed reaches a fresh segment of the network.

2. Physics-Inspired Visualization

The paper also introduces a novel way to "see" the network. Instead of traditional spring-embedder layouts, they use the Information Diffusion Model to define distances. If node A often infects node B in simulations, they are pulled together in the 2D map.

The map reveals "basins of influence" where nodes are tightly clustered by their infection probability.

Experimental Showdown

The authors tested SCG against the gold-standard Simple Greedy and the baseline Degree Centrality across three datasets: NIPS, Blog, and COA.

Performance vs. Efficiency

• Superior Spread: In almost all tests (whether using the Independent Cascade Model or the Linear Threshold Model), SCG achieved a wider cascade than its competitors.
• Speed: On the COA dataset (30,561 nodes), the Simple Greedy algorithm was computationally unfeasible. SCG completed the task in under 10 seconds.

Fig 1: On the Blog dataset, SCG (with neighborhood size m=2) significantly outperforms both the standard Greedy and Degree Centrality.

Critical Insight & Perspectives

The brilliance of SCG lies in its diffusion-model-agnostic nature. Unlike the Simple Greedy method, which must be re-simulated if you change the infection probability or the model type (from ICM to LTM), SCG relies purely on the topology.

Limitations: While SCG is incredibly fast, its accuracy depends on the choice of the neighborhood size $m$. If $m$ is too small, it reverts toward Degree Centrality; if $m$ is too large, it might overestimate the reach of a single node in high-threshold models.

Conclusion

This work provides a bridge between theoretical influence maximization and practical, large-scale application. By reframing influence as a set-covering problem, the authors unlocked a way to process networks with tens of thousands of nodes in real-time, providing a vital tool for data mining and viral marketing strategy.