An Island-Based Evolutionary Algorithm with a Novel Fitness Approximation Function for the Influence Maximization Problem

Abstract

nfluence Maximization (IM) seeks the set of nodes that maximizes expected influence spread under a diffusion model on a static network. Existing Evolu- tionary Algorithms (EA) approaches are limited by slow or inaccurate fitness approximation methods. This thesis contributes (i) ThreeHopSpread, a deter- ministic multi-hop fitness approximation that captures cascades up to three hops while remaining computationally efficient, and (ii) an island-based EA that evolves semi-isolated subpopulations with periodic best-replaces-worst migration to preserve diversity and encourage exploration of the entire search space. A node filtering pre-processing step further improves scalability by restricting the candidate pool of nodes to high-quality options. On real-world datasets, ThreeHopSpread achieves one of the lowest pairwise ranking error rates while maintaining a practical runtime, and the island EA under the Weighted Cascade (WC) model delivers superior or competitive influence spread in a practical runtime while showing low sensitivity to changes in the hyperparameter settings. Overall, the method is robust, scalable, and effective for IM.