SCG: Efficient Influence Maximization via Set Covering Logic

TL;DR

Predicting the most influential individuals in a social network—the "super-spreaders"—is a computationally exhausting task. This paper introduces the Set Covering Greedy (SCG) algorithm, a topological approach that replaces slow simulations with a smart "m-neighbor" coverage strategy. It matches the performance of the best greedy algorithms but is thousands of times faster, completing in seconds what used to take days.

Background: The Cost of Influence

In viral marketing, the "Influence Maximization Problem" asks: if you can only pick $K$ people to give a free sample to, who should they be to trigger the largest cascade of adoptions?

Previous research by Kempe et al. proved that a Simple Greedy algorithm is effective but slow. Because the diffusion of ideas is stochastic (represented by models like ICM and LTM), the algorithm must run approximately 10,000 simulations for every potential node choice to see who might get infected. On a medium-sized network, this takes over 100 hours. Meanwhile, simple metrics like Degree Centrality (picking the person with the most friends) often fail because "popular" people often know the same crowd, leading to wasted effort through neighborhood overlapping.

Methodology: Thinking in Set Covers

The authors' core insight is that we can approximate diffusion influence by looking at the topology of the graph rather than simulating the "germ" spreading.

1. The m-Neighbor Concept

Instead of complex probabilities, SCG defines a node's influence as its $m$-neighbors—the set of all nodes within distance $m$.

• $m=1$: Immediate friends.
• $m=2$: Friends and friends-of-friends.

2. The SCG Algorithm

The algorithm behaves like a "Set Cover" solver:

1. Pick the node with the most $m$-neighbors.
2. Mark all those neighbors as "covered."
3. For the next pick, ignore the already covered neighbors and find the node that provides the largest uncovered marginal gain.

This avoids the redundancy trap of Degree Centrality and the computational black hole of the Simple Greedy algorithm.

Fig 1: Performance on the Blog dataset showing SCG (m=1, 2) outperforming standard approaches.

Experiments and Results

The authors tested SCG on various datasets, including NIPS co-authorship and a large Physics collaboration network (COA).

• Accuracy: In the Blog and COA datasets, SCG with $m=2$ or $m=3$ significantly outperformed High Degree and kept pace with the theoretical maximum of the Simple Greedy algorithm.
• Speed: The COA dataset (30k nodes) was impossible to process with the standard greedy algorithm using reasonable resources. SCG finished in less than 10 seconds.

Fig 2: In the COA dataset, SCG proves its scalability where the simple greedy approach fails to compute.

Visualizing the "Infection"

One of the most unique contributions of this paper is a visualization algorithm that maps social networks based on their diffusion probability. By using a force-directed approach—where nodes that infect each other frequently are pulled closer—we can literally "see" the clusters of influence.

Fig 3: The Blog network mapped with target nodes (squares) selected by SCG effectively distributed across the manifold.

Critical Insight & Conclusion

The SCG algorithm proves that network structure is often a sufficient proxy for diffusion dynamics. By shifting the problem from a stochastic simulation to a combinatorial geometry problem (Set Covering), the authors bypassed a massive computational bottleneck.

Takeaway for Practitioners: When working with massive social graphs, don't waste time simulating every possible "what-if" scenario. Focus on uncovered reach within a 2-to-3 step horizon. It is mathematically robust and computationally nearly instantaneous.