Hybrid GA-TAP: Revitalizing Social Influence Maximization with Dynamic Probabilities

TL;DR

Social Influence Maximization (IM) is the quest to find a handful of "super-spreaders" in a network to trigger a viral cascade. This paper introduces a novel hybrid approach that replaces static assumptions with dynamic probabilities. By fusing Topic Affinity Propagation (TAP) with a Genetic Algorithm (GA), the authors achieved a significant 6% to 13% improvement in influence spread over traditional benchmarks like High Degree and Greedy heuristics.

Contextual Positioning

Within the landscape of Social Network Analysis (SNA), IM has long been recognized as a bottleneck due to its NP-hard nature. While previous SOTA works focused on faster greedy approximations or simple evolutionary strategies, this paper addresses the "probability gap"—the fact that in reality, the likelihood of one user influencing another isn't just a fixed number; it's a dynamic function of their relationship and topic relevance.

The Problem: Why Static Heuristics Fail

Traditional methods like Discounted Degree or Weighted Cascade look at the graph's topology (who is connected to whom) but often ignore the strength of those connections. They treat every edge of a similar degree the same way. In reality, a "high degree" node might have many weak connections that don't actually facilitate info-spread.

The authors identify that the missing link is a robust way to calculate Edge-Specific Influence Probabilities before running the optimization.

Methodology: The Fusion of TAP and GA

The proposed methodology operates in two distinct phases:

1. Dynamic Probability Estimation

Instead of assuming a fixed threshold, the authors adapt the Topical Affinity Propagation algorithm.

• Physical Intuition: Every node has a "representative" neighbor that influences it most.
• The Logic: By calculating a "node feature function" and iteratively updating influence scores ($A_{ij}$ and $T_{ij}$) until convergence, the model assigns a unique probability ${\mu }_{ij}$ to every directed edge. This transforms the raw graph into a "Dynamic Probability Graph."

2. Genetic Algorithm (The Optimization Engine)

With the dynamic weights in place, the GA takes over to find the optimal $k$ nodes.

• Chromosomes: Each candidate solution is a set of $k$ seed nodes.
• Fitness Function: The Cascade Propagation Model, which simulates the actual spread using the newly calculated ${\mu }_{ij}$ weights.
• Evolution: Through tournament selection, 1-point crossover, and random mutation, the population evolves toward the global optimum.

Figure 1: The two-stage pipeline: Dynamic Probability Calculation followed by Genetic Optimization.

Experiments and Results

The authors tested their approach on two distinct datasets:

1. Wiki Vote Network: High out-degree ratio (nodes voting for others).
2. Amazon Co-purchased Network: Low out-degree ratio (products bought together).

Key Performance Insights:

• Superior Spread: In the Wiki Vote dataset, the proposed GA-TAP method outperformed the best heuristic (Discounted Degree) by 9%.
• Robustness: On the Amazon dataset, where node degrees are much lower (max out-degree 5), the improvement was even more pronounced—reaching 13% over the standard GA.
• Scalability: The method showed steady improvement as the number of seed nodes ($k$) increased from 10 to 50.

Figure 2: Performance comparison on the Wiki Vote dataset showing consistent lead over baseline heuristics.

Critical Analysis & Conclusion

The strength of this work lies in its Hybrid Nature. By separating the "weight estimation" (TAP) from the "set selection" (GA), it allows both components to do what they do best.

Takeaways:

• Dynamic Weights Matter: The 13% performance jump on Amazon's network proves that when structural information is sparse, the quality of edge probability estimation becomes the deciding factor for reaching the whole network.
• Limitations: The model currently assumes a single-topic specification for nodes. In the real world, users are multi-faceted (e.g., interested in both politics and technology).
• Future Path: Extending this to Multi-Topic Influence and Dynamic Graphs (where edges appear and disappear over time) is the logical next step for this framework.

Overall, this paper provides a strong case for moving away from "graph-only" heuristics toward "feature-aware" influence modeling.