GA-PSO: Breaking the Efficiency Bottleneck of Influence Maximization with Directed Evolution

Executive Summary

TL;DR: Influence Maximization (IM) — finding the top-K nodes to trigger a "word-of-mouth" cascade — has long been trapped between the slow-but-accurate Greedy algorithms and the fast-but-unreliable Heuristics. This paper introduces GA-PSO, an evolutionary framework that uses a Direction Vector to guide mutations and a LIEEX function to estimate spread without expensive simulations. It achieves SOTA greedy-level accuracy while slashing runtime by over 60%.

Context: This work represents a significant refinement in the "Intelligent Optimization" branch of IM research, moving away from pure stochastic search toward a more "physically-aware" guided evolution.

The Core Problem: The Accuracy-Efficiency Trade-off

The challenge of IM is twofold:

1. Estimation Cost: Evaluating the influence of a node set $\sigma (S)$ typically requires thousands of Monte-Carlo simulations, making it a computational nightmare for large graphs.
2. Search Blindness: Classic Genetic Algorithms (GA) rely on random mutation. In a network with millions of nodes, the probability of "stumbling" upon the optimal K nodes via random swaps is infinitesimally small.

Methodology: Evolution with a Compass

The authors tackle these issues through three distinct layers:

1. LIEEX: Influence Estimation Beyond the Horizon

Previous models like LIE only looked at two-hop neighbors. The authors proposed LIEEX (LIE Extension). It calculates the expected activation probability by considering:

• The seed set $S$.
• One-hop neighbors ($N^{(1)}$).
• Two-hop neighbors ($N^{(2)}$) and their external connections ($d^{out}$).

This allows the algorithm to "see" further into the network without actually running a simulation.

2. Guided Mutation via Direction Vectors

The standout innovation is the Direction Vector ($D_i$). Instead of flipping a coin to mutate a node, the algorithm compares an individual's "genes" (selected nodes) with the current local best ($I_{pbest}$) and global best ($G_{pbest}$).

• If a node is already present in the "Best" sets, it is preserved (low mutation probability).
• If a node is absent from the "Best" sets, the direction vector flags it for replacement.

Figure 1: The Direction Vector logic effectively acts as a compass, pulling the population toward high-influence manifolds.

Experiments and Results

Accuracy parity with CELF

Testing across four datasets (p2p-Gnutella08, Ca-GrQc, CondMat, HepTh), GA-PSO consistently matched the performance of CELF (the gold-standard optimized greedy algorithm). In some cases, as $K$ increased, GA-PSO actually surpassed CELF by discovering better global combinations that greedy approaches might miss due to their incremental nature.

Figure 2: Influence spread comparison across different seed sizes (K).

The Efficiency Win

The most striking result is the time efficiency. While CELF's runtime explodes on larger graphs like Ca-CondMat (taking hours), GA-PSO remains relatively stable, showing an average 65% reduction in runtime compared to standard GA.

Figure 3: Runtime comparison showing the scalability of GA-PSO.

Critical Insight & Conclusion

The Takeaway: The success of GA-PSO highlights a growing trend in graph optimization: Inductive Bias Matters. By baking "network common sense" (like Diffusion Degree Centrality and local-hop influence) into a meta-heuristic, we can search the massive discrete space of social networks far more effectively than through "raw" computation or "blind" evolution.

Limitations: The paper currently operates under the Independent Cascade (IC) model. Future work should validate if these direction vectors hold up under the Linear Threshold (LT) model or in dynamic networks where edges change over time.

Final Thought: If you are building a viral marketing engine or a rumor-containment system, the GA-PSO framework offers a blueprint for "Guided Intelligence" that doesn't require a supercomputer to run.