Int-Div: Balancing Collaboration and Coverage in Social Influence Maximization

TL;DR

The Influence Maximization (IM) problem—selecting $K$ seeds to trigger the largest cascade—has long been torn between the accuracy of Greedy algorithms and the speed of simple heuristics. This paper introduces Int-Div, a heuristic that bridges this gap. By explicitly modeling "Intensification" (how seeds work together) and "Diversification" (how to avoid overlap), it achieves near-optimal results at a fraction of the computational cost (reducing runtime from 58 days to about 1 hour on large networks).

The Core Conflict: Clustering vs. Spreading

Most influence maximization strategies fail for one of two reasons:

1. Redundancy: Centrality-based methods (like selecting high-degree nodes) often pick seeds that are close to each other. Their influence circles overlap, wasting the "budget" on nodes already likely to be activated.
2. Complexity: High-fidelity simulations used in Greedy algorithms require thousands of Monte Carlo runs for every potential seed selection, making them unusable for networks like Facebook or LinkedIn.

The authors' insight is rooted in metaheuristics: effective search requires Intensification (exploiting the teamwork effect where multiple neighbors activate a common node) and Diversification (exploring new, untapped regions of the graph).

Methodology: The Marginal Influence Increment (MII)

The heart of the paper is the Marginal Influence Increment (MII). When selecting a new seed $i$ given an existing set $S$, the algorithm doesn't just look at $i$'s degree. It calculates: $MI{I}_i(S)=(1-p_i(S))(1+IN{T}_i(S)+DI{V}_i(S))$

• $(1-p_i(S))$: The probability that $i$ isn't already influenced by $S$. If $i$ is likely already active, its value as a seed drops.
• $IN{T}_i(S)$ (Intensification): Evaluates the "boost" node $i$ gives to neighbors that are already neighbors of $S$.
• $DI{V}_i(S)$ (Diversification): Evaluates the influence $i$ brings to "fresh" nodes that current seeds cannot reach.

To further refine this, the authors use an up-to-2-hop degree metric, acknowledging the "strength of weak ties"—the idea that your neighbor's influence is as vital as your own.

Figure 1: A social graph illustrating the seed selection process where Node C and A are prioritized to maximize coverage while acknowledging shared neighbors.

Performance: Greedy Results at Heuristic Speeds

The experimental results are striking across both Linear Threshold (LTM) and Independent Cascade (ICM) models.

1. Accuracy

On the Epinions (ESN) dataset (75k nodes), the Greedy algorithm becomes "computationally infeasible" once the seed set exceeds 12. Int-Div, however, continues to scale, maintaining a performance profile that hugs the Greedy curve almost perfectly.

2. Efficiency

The runtime data reveals the true value of Int-Div. In a collaboration network (CN), while Greedy takes 18.1 hours, Int-Div finishes in just 0.0228 hours (approx. 82 seconds).

Table 2: Comparison of computation times showing Int-Div operating at 3 orders of magnitude faster than Greedy.

Critical Analysis & Takeaways

The brilliance of Int-Div lies in its Local-to-Global Approximation. By only looking at 2-hop neighborhoods and calculating MII, it captures the essential dynamics of a global cascade without the need for exhaustive simulation.

Limitations:

• The paper assumes static network topology. In real-world viral marketing, the network may be dynamic or partially observed.
• While MII is effective, the specific weights ($b_{i,j}$) in LTM are often hard to estimate in real life.

Conclusion: Int-Div proves that sophisticated influence modeling doesn't have to be slow. By balancing the drive to "cluster" for localized activation and "spread" for broad reach, this heuristic provides a production-ready solution for viral marketing and information dissemination.