A novel meta-heuristic approach for influence maximization in social networks

Influence maximization in a social network focuses on the task of extracting a small set of nodes from a network which can maximize the propagation in a cascade model. Though greedy methods produce good solutions to the aforementioned problem, their high computational complexity is a major drawback. Centrality-based heuristic methods often fail to overcome local optima, thereby producing sub-optimal results. To this end, in this article, a framework has been presented which involves community detection in a social network and the utilization of the Shuffled Frog Leaping algorithm, in maximizing the two-hop spread of influence under the independent cascade model. Local search strategies like the Late acceptance based hill climbing have been employed to improve the solution further. Experiments performed on three real-world datasets have shown that our method performs markedly well with respect to the comparing algorithms.