Breaking the Computational Bottleneck of Social Influence Maximization

TL;DR

Influence maximization—the art of picking $K$ seeds to trigger a viral cascade—has long been a tug-of-war between the accuracy of Greedy algorithms and the speed of Centrality metrics. This paper bridges the gap by reframing the task as a Probabilistic Maximum Coverage Problem. By introducing structural clustering and adaptive neighborhood removal, the authors match SOTA greedy performance while operating over 300 times faster.

The Core Dilemma: Greedy vs. Centrality

In social network analysis, we typically use two models to describe diffusion:

1. Linear Threshold Model (LTM): A node activates if the weighted influence of its neighbors crosses a personal threshold.
2. Independent Cascade Model (ICM): Each active neighbor gets one shot at infecting an inactive friend with probability $p$.

The standard solution has been the Greedy Algorithm, which picks nodes with the highest marginal gain. While effective, it is agonizingly slow for large graphs because it requires thousands of Monte Carlo simulations per step. On the other hand, simply picking the "most popular" nodes (Degree Centrality) fails because popular people often hang out in the same circles—leading to influence overlap that wastes your seed quota.

Methodology: Smart Intensification & Diversification

1. Cluster-Based Heuristic (For LTM)

To solve LTM, the authors split the problem into a "Divide and Conquer" strategy:

• Diversification: They prune the network by removing weak edges (weight below threshold $\omega$). The remaining connected components are treated as "Clusters." By picking seeds from the $K$ largest clusters, they ensure that the influence is spread across different communities rather than concentrated in one.
• Intensification: Within each cluster, they pick the "Cluster Head"—the node with the highest weighted degree—to ensure maximum local impact.

Figure 1: Decomposing a complex network into independent clusters to ensure influence diversity.

2. Neighborhood-Removal Heuristic (For ICM)

For the cascade model, the authors tackle the overlap problem directly:

• Up-to-k-hop Degree: Instead of just counting direct friends, they evaluate a node by the "influence potential" of its 1-step or 2-step neighborhood.
• Dominance Check: Before adding a candidate node to the seed set, they check if its neighbors are already "dominated" by existing seeds. If a node has a high probability (defined by threshold $\eta$) of being activated by the current seed set anyway, it is discarded as redundant.

Experimental Results: Performance without the Price Tag

Testing on the Arxiv General Relativity collaboration network (~4k nodes, ~26k edges), the results were striking:

• Accuracy: In most scenarios, the proposed heuristics outperformed Betweenness and Degree centrality and were virtually indistinguishable from the Greedy algorithm.
• Efficiency: The computation time is where the methods shine. While the Greedy algorithm required hundreds of seconds, the proposed heuristics finished in sub-second times.

Figure 2: Performance in the LTM model shows that as the target seed size increases, the Cluster-based approach tracks the Greedy algorithm closely.

Quantitative Efficiency Comparison

Critical Insights & Future Outlook

The "Magic" of this paper lies in its recognition that Inversion is faster than Simulation. Instead of simulating a thousand cascades to see who is influential, the authors analyze the static topology to identify regions of redundancy.

Limitations:

• The cut-off threshold ($\omega$) and domination threshold ($\eta$) are hyper-parameters that require tuning based on the network's density.
• The approach assumes the network structure is fully known and static, which is rarely the case in real-time social media environments.

Takeaway: This research provides a highly practical framework for electronic commerce and viral marketing, proving that we don't need massive compute clusters to solve NP-hard social influence problems if we understand the underlying geometry of the network.