Influence Maximization in Social Networks Using Improved Genetic Algorithm

Influence maximization is one of the important problems in network science, data mining, and social media analysis. It focuses on identifying the most influential individuals (or nodes) in a social network to maximize the spread of information, ideas, or behaviors. Most existing studies have used centrality measures such as degree, closeness, or PageRank to identify the most influential individuals, but they have not obtained good results. To overcome this issue and improve the results, in this paper, an improved genetic algorithm is proposed to solve the influence maximization problem in social networks, and it is called IGAIM. In different operators of the IGAIM, a new criterion called <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">selection score</i> is employed to rank the nodes in terms of influence extent. In addition, a new local search method is presented that uses the selection score to search in the neighborhood of a given solution. By utilizing the proposed local search, the search space is efficiently explored, leading to an increase in the convergence speed of the algorithm. Experimental results on four real-world benchmark networks reveal that IGAIM considerably outperforms the compared methods in terms of influence spread and computation time. On average, IGAIM achieves a 65.89% improvement in terms of influence spread over greedy algorithms, a 37.59% improvement over metaheuristic algorithms, and a 10.94% improvement compared to the top three performing algorithms. In terms of computation time, IGAIM is significantly faster, outperforming greedy algorithms by 99.56%, metaheuristic algorithms by 34.82%, and top three performing algorithms by 14.70%.