Genetic Algorithms for Influence Maximization: Breaking the Greedy Bottleneck

TL;DR

Influence Maximization (IM)—the task of finding the $k$ most influential nodes in a network to trigger a "viral" cascade—is a cornerstone of social network analysis. While greedy algorithms provide theoretical guarantees, they are often too slow for real-world graphs. This paper introduces a Genetic Algorithm (GA) approach that matches SOTA greedy performance while remaining agnostic to the underlying graph structure, offering a faster and more robust alternative for massive networks.

The Problem: The High Cost of Influence

In social networks, "influence" isn't just about how many followers you have (degree centrality); it's about the reach of the information you spread. This is modeled by stochastic processes like the Independent Cascade or Weighted Cascade.

The industry standard, the General Greedy algorithm, is a hill-climbing approach. It starts with an empty set and iteratively adds the node that offers the maximum marginal gain. While it guarantees a solution within 63% of the optimum, its complexity is staggering. On a graph with millions of edges, simulating thousands of cascades for every possible node addition is a computational dead end.

Conversely, simple heuristics (like picking the top-$k$ nodes by degree) are fast but "dumb"—they can be easily tricked by network topologies where high-degree nodes have overlapping audiences or live in isolated clusters.

Methodology: Evolution as an Optimization Tool

The authors propose a simple yet effective GA framework. By treating a set of $k$ seed nodes as a "chromosome," the algorithm evolves a population of solutions over generations.

The Core Mechanism

1. Representation: An individual is a fixed-size sequence of $k$ node IDs.
2. Fitness Evaluation: The "Influence" $\sigma (A_0)$ is calculated by running the Cascade Model 100 times and averaging the number of activated nodes.
3. Genetic Operators: 1-point crossover and random mutation.
4. Selection: Tournament selection with generational elitism (keeping the best performers).

The beauty of this approach lies in its topology-agnostic nature. Unlike heuristics that rely on out-degrees or bridge-node features, the GA only cares about the final influence count, allowing it to navigate complex fitness landscapes that stump traditional algorithms.

Experimental Insights

The GA was tested against two distinct datasets: Wiki-Vote (dense, high-degree variance) and Amazon (large, flat degree distribution).

1. Performance vs. Heuristics

On the Wikipedia dataset, the GA consistently matched the General Greedy performance. Remarkably, on the Amazon dataset, degree-based heuristics performed worse than random sampling, while the GA remained highly effective.

2. Computational Efficiency

While GA is often considered slow, in the context of IM, it can be a speed demon. On the Amazon dataset, the GA found high-quality solutions in half the time (core hours) required by the General Greedy algorithm for small $k$.

Figure: Comparison across Wiki and Amazon datasets. The GA (Red line) remains competitive with or superior to General Greedy (Blue line) and Degree-based methods.

Deep Insight: Why GA Works Here

The "influence landscape" of a social network is often multimodal. There are usually many different sets of $k$ nodes that yield similar total influence.

• Greedy algorithms are "locked in" by their initial choices—once a node is picked, it stays.
• GAs maintain a population, allowing them to explore multiple "peaks" in the influence landscape simultaneously. This diversity is crucial for avoiding the diminishing returns often seen in submodular optimization.

Parameter Sensitivity

The authors noted that:

• Elitism (keeping 2-4% of the best) prevents losing the "best-so-far" seeds.
• Tournament Size of 5 provided the best balance between selection pressure and maintaining diversity.
• Population Size of 100 was sufficient even for the Amazon graph with >260k nodes.

Conclusion and Outlook

This paper refutes the notion that Genetic Algorithms are too slow for large-scale graph problems. By leveraging the stochastic nature of influence cascades within a survival-of-the-fittest framework, GAs provide a robust, parallelizable, and scalable solution to Influence Maximization.

Future Directions: The next logical step is Memetic Algorithms—combining GA's global search with graph-based local search (like swapping a seed node with its neighbor) to further accelerate convergence.

Keywords: Social Network, Influence Maximization, Genetic Algorithms, Combinatorial Optimization, Cascade Models.