Performance Evaluation of EvolutionaryAlgorithms on Solving the InfluenceMaximization Problem in Social Networks

Influence Maximization (IM) is an optimization problem that deals with identifying the most valuable individuals/ nodes present in the network to attain the maximal information spread when they are activated. Evolutionary Algorithms (EAs) inspired from nature are one of the most powerful methods to solve an optimization problem. This paper attempts to solve the IM problem using few of the popular EAs such as Genetic Algorithm (GA), Ant Colony Optimization (ACO), Particle Swarm Optimization (PSO), and Differential Evolution (DE). These algorithm's performance is evaluated using four comparative metrics, that deal with assessing solution quality, computational efficiency, and scalability. The experimental results of these EAs when tested on several real-world networks reveal that the GE and PSO algorithms were found to produce relatively poorer quality of seed nodes and also with higher computational costs, making it less preferrable. DE was able to obtain the best seed sets (in terms of influence spread value) than other algorithms and ACO, the fastest among all the considered algorithms in terms of execution time, was found to obtain seed set with appreciable influence spread with a slightly higher computational cost than DE.